數據結構考研真題與答案(編輯修改稿)
2025-07-20 22:44 本頁面
【文章內容簡介】 和解決沖突的方法，將關鍵字散列在連續(xù)的有限的地址空間內，并將散列函數的值解釋成關鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關鍵字隨機存取，不能順序存取，也不能折半存取。3. 數據類型和抽象數據類型是如何定義的。二者有何相同和不同之處，抽象數據類型的主要特點是什么？使用抽象數據類型的主要好處是什么？【北京郵電大學 1994 一（8分）】數據類型是程序設計語言中的一個概念，它是一個值的集合和操作的集合。如C語言中的整型、實型、字符型等。整型值的范圍（對具體機器都應有整數范圍），其操作有加、減、乘、除、求余等。實際上數據類型是廠家提供給用戶的已實現了的數據結構。“抽象數據類型（ADT）”指一個數學模型及定義在該模型上的一組操作。“抽象”的意義在于數據類型的數學抽象特性。抽象數據類型的定義僅取決于它的邏輯特性，而與其在計算機內部如何表示和實現無關。無論其內部結構如何變化，只要它的數學特性不變就不影響它的外部使用。抽象數據類型和數據類型實質上是一個概念。此外，抽象數據類型的范圍更廣，它已不再局限于機器已定義和實現的數據類型，還包括用戶在設計軟件系統時自行定義的數據類型。使用抽象數據類型定義的軟件模塊含定義、表示和實現三部分，封裝在一起，對用戶透明（提供接口），而不必了解實現細節(jié)。抽象數據類型的出現使程序設計不再是“藝術”，而是向“科學”邁進了一步。4. 回答問題（每題2分）【山東工業(yè)大學 1997 一 （8分）】（1）在數據結構課程中，數據的邏輯結構，數據的存儲結構及數據的運算之間存在著怎樣的關系？數據的邏輯結構反映數據元素之間的邏輯關系（即數據元素之間的關聯方式或“鄰接關系”），數據的存儲結構是數據結構在計算機中的表示，包括數據元素的表示及其關系的表示。數據的運算是對數據定義的一組操作，運算是定義在邏輯結構上的，和存儲結構無關，而運算的實現則是依賴于存儲結構。（2）若邏輯結構相同但存儲結構不同，則為不同的數據結構。這樣的說法對嗎？舉例說明之。邏輯結構相同但存儲不同，可以是不同的數據結構。例如，線性表的邏輯結構屬于線性結構，采用順序存儲結構為順序表，而采用鏈式存儲結構稱為線性鏈表。（3）在給定的邏輯結構及其存儲表示上可以定義不同的運算集合，從而得到不同的數據結構。這樣說法對嗎？舉例說明之。棧和隊列的邏輯結構相同，其存儲表示也可相同（順序存儲和鏈式存儲），但由于其運算集合不同而成為不同的數據結構。（4）評價各種不同數據結構的標準是什么？數據結構的評價非常復雜，可以考慮兩個方面，一是所選數據結構是否準確、完整的刻劃了問題的基本特征；二是是否容易實現（如對數據分解是否恰當；邏輯結構的選擇是否適合于運算的功能，是否有利于運算的實現；基本運算的選擇是否恰當。）5．評價一個好的算法，您是從哪幾方面來考慮的？評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時空效率（運行）。【大連海事大學 1996 二、3 （2分）】【中山大學 1998 三、1 （5分）】6．解釋和比較以下各組概念【華南師范大學 2000 一（10分）】（1）抽象數據類型及數據類型 （2）數據結構、邏輯結構、存儲結構（3）抽象數據類型【哈爾濱工業(yè)大學 2000 一、1（3分）】（4）算法的時間復雜性 【河海大學 1998 一、2（3分）】（5）算法【吉林工業(yè)大學1999 一、1（2分）】（6）頻度【吉林工業(yè)大學 1999 一、2（2分）】（1）見上面題3 （2）見上面題4 （3）見上面題3 （4）算法的時間復雜性是算法輸入規(guī)模的函數。算法的輸入規(guī)?；騿栴}的規(guī)模是作為該算法輸入的數據所含數據元素的數目，或與此數目有關的其它參數。有時考慮算法在最壞情況下的時間復雜度或平均時間復雜度。 （5）算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有五個重要特性：有窮性、確定性、可行性、輸入和輸出。 （6）頻度。在分析算法時間復雜度時，有時需要估算基本操作的原操作，它是執(zhí)行次數最多的一個操作，該操作重復執(zhí)行的次數稱為頻度。7. 根據數據元素之間的邏輯關系，一般有哪幾類基本的數據結構？集合、線性結構、樹形結構、圖形或網狀結構。 【北京科技大學 1998 一、1】【同濟大學 1998】8．對于一個數據結構，一般包括哪三個方面的討論？【北京科技大學 1999 一、1（2分）】邏輯結構、存儲結構、操作（運算）。9. 當你為解決某一問題而選擇數據結構時，應從哪些方面考慮？【西安電子北京科技大學 2000】通?？紤]算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面：程序運行時所需輸入的數據總量，對源程序進行編譯所需時間，計算機執(zhí)行每條指令所需時間和程序中指令重復執(zhí)行的次數。10. 若將數據結構定義為一個二元組（D，R）,說明符號D，R 應分別表示什么？【北京科技大學 2001 一、1（2分）】D是數據元素的有限集合，S是D上數據元素之間關系的有限集合。11．數據結構與數據類型有什么區(qū)別？【哈爾濱工業(yè)大學 2001 三、1（3分）】“數據結構”這一術語有兩種含義，一是作為一門課程的名稱；二是作為一個科學的概念。作為科學概念，目前尚無公認定義，一般認為，討論數據結構要包括三個方面，一是數據的邏輯結構，二是數據的存儲結構，三是對數據進行的操作（運算）。而數據類型是值的集合和操作的集合，可以看作是已實現了的數據結構，后者是前者的一種簡化情況。12．數據的存儲結構由哪四種基本的存儲方法實現？【山東科技大學 2001 一、1（4分）】 12．見上面題2。13．若有100個學生，每個學生有學號，姓名，平均成績，采用什么樣的數據結構最方便，寫出這些結構？【山東師范大學 1996 二、2（2分）】將學號、姓名、平均成績看成一個記錄（元素，含三個數據項），將100個這樣的記錄存于數組中。因一般無增刪操作，故宜采用順序存儲。 typedef struct {int num。//學號 char name[8]。//姓名 float score。/平均成績 }node
教學教案相關推薦
鄂ICP備17016276號-1