數據結構復習題及答案

1、1數據結構習題數據結構習題一、一、名詞解釋名詞解釋1.數據、數據元素、數據項、數據結構、數據的邏輯結構、數據物理結構、順序存儲、鏈式存儲、算法、時間復雜度、空間復雜度。2.線性表、順序表、單鏈表、雙向鏈表、循環(huán)鏈表、雙向循環(huán)鏈表、三個概念的區(qū)別：頭指針、頭結點、首元結點(第1個元素結點)。3.棧（順序棧、鏈棧）、隊列（順序隊、鏈隊）、循環(huán)隊列、遞歸、稀疏矩陣、三元組。4.樹、葉子結點、結點的度、樹的度、樹的高(深)度、二叉樹、遍歷、滿二

2、叉樹、完全二叉樹、哈夫曼樹、WPL、哈夫曼編碼。5.圖（有向、無向）、網、邊、弧、度、入度、出度、完全圖（有向、無向）、（強）連通圖（分量）、（最?。┥蓸洹⑧徑泳仃?、鄰接表、DFS、BFS。6.查找表、關鍵字、靜態(tài)查找、動態(tài)查找、ASL、順序查找、折半查找、分塊查找、二叉排序樹。7、排序、內（外）排序、穩(wěn)定性、插入（直接、希爾），交換（起泡、快速），選擇（直接、堆），2路歸并。一、一、填空題填空題1.數據結構是研究數據的_邏輯結構__

3、和___物理結構__，并在這種結構上定義相關的運算，設計實現這些運算的算法，分析算法的效率。算法的效率包括時間和空間兩個方面，分別稱為___時間復雜度____和__空間復雜度___。2.數據的基本單位是__數據元素__，數據的最小單位是__數據項_。3.算法是對特定問題求解___步驟___的一種描述，是指令的有限序列。4.一個算法的時間復雜度為(3n32n—7)，其數量級表示為O（n3）_。5.一個算法具有5個特性：確定性、可行性、有窮

4、性、輸入和輸出。6.算法性能的分析和度量，可以從算法的時間復雜度和空間復雜度來評價算法的優(yōu)劣。7.數據的邏輯結構包括集合結構、線性結構、樹形結構和圖型結構四種類型。8.數據結構在計算機中的表示稱為數據的物理結構，它可以采用__順序存儲___或__鏈式存儲_兩種存儲方法。9.線性表有兩種存儲結構，分別為順序存儲和鏈式存儲。10.鏈式存儲的特點是利用指針來表示數據元素之間的邏輯關系。11.若頻繁地對線性表進行插入和刪除操作，該線性表宜采用_

5、鏈式存儲__存儲結構。12.線性表中的數據元素之間具有一對一的線性關系，除第一個和最后一個元素外，其他數據元素有且只有一個直接后繼和直接前趨。13.在一個單鏈表中p所指結點之后插入一個s所指結點時，應執(zhí)行snext=__pnext______和pnext=__s______的操作。14.在一個單鏈表中刪除p的后繼結點q時，應執(zhí)行以下操作pnext=qnext。15.對帶頭結點head的單鏈表，則判斷其為空的條件為headnext=NUL

6、L。學號姓名學號339.若深度為6的完全二叉樹的第6層有3個葉結點，則該二叉樹一共有34個結點。40.深度為15的滿二叉樹上，第11層有_2^(111)=1024個結點。41.一棵具有100個結點的完全二叉樹，它的深度為7，其中度為1的結點有1個。42.某二叉樹的后根遍歷序列為abd，中根遍歷序列為adb，則它的先根遍歷序列為dab。43.哈夫曼樹是指對于一組帶有確定權值的葉子結點構造的具有最小帶權路徑長度的二叉樹。44.具有m個葉子結

7、點的哈夫曼樹共有2m1個結點。45.已知一棵哈夫曼樹含有60個葉子結點，則該樹中共有59個非葉子結點。46.在一個具有n個頂點無向完全圖中，含有n(n1)2邊；在一個具有n個頂點有向完全圖中，含有n(n1)邊。一個具有4個頂點的無向完全圖有6條邊。47.具有n個頂點的連通圖至少需有n1條邊。48.一個連通圖的生成樹是該圖的極小連通子圖。若這個連通圖有n個頂點，則它的生成樹有n1條邊。49.在有向圖的鄰接矩陣中，第i行中非零元素的個數正好

8、是第i個頂點的出度；第i列中非零元素的個數正好是第i個頂點的入度。50.在一個圖中，所有頂點的度數之和等于所有邊數的2倍。51.在無向圖G的鄰接矩陣A中，若A［i］［j］等于1，則A［j］［i］等于1。52.對二叉排序樹進行中序遍歷，可以得到按關鍵字從小到大排列的結點序列。53.一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當折半查找值為82的結點時，經過4次比較后查找成功。54.在線性表中采用折

9、半查找法查找一個數據元素，線性表中元素應該按值有序，并且采用___順序存儲__存儲方法。55.在簡單選擇排序、堆排序、快速排列、歸并排序四種排序方法中，排序方法穩(wěn)定的是__歸并排序。56.冒泡排序是一種穩(wěn)定的排序方法，對n個元素的序列進行冒泡排序時，最多需進行n1趟。該排序方法的時間復雜度為O(n2)。57.給定序列100，86，48，73，35，39，42，57，66，21，按堆的定義，則它一定大根堆。58.數據結構是指數據及其相互之