1、數據結構復習資料 一、填空題1. 數據結構是一門研究非數值計算的程序設計問題中計算機的 操作對象 以及它們之間的 關系 和運算等的學科。2. 數據結構被形式地定義為（D, R），其中D是 數據元素 的有限集合，R是D上的 關系 有限集合。3. 數據結構包括數據的 邏輯結構 、數據的 存儲結構 和數據的 運算 這三個方面的內容。4. 數據結構按邏輯結構可分為兩大類，它們分別是 線性結構 和 非線性結構 。5. 線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。6 在線性結構中，第一個結點 沒有 前驅結點，其余每個結點有且只有 1個前驅結點；最后

2、一個結點 沒有 后續結點，其余每個結點有且只有1個后續結點。7. 在樹形結構中，樹根結點沒有 前驅 結點，其余每個結點有且只有 1 個前驅結點；葉子結點沒有 后續 結點，其余每個結點的后續結點數可以任意多個 。8. 在圖形結構中，每個結點的前驅結點數和后續結點數可以 任意多個 。9數據的存儲結構可用四種基本的存儲方法表示，它們分別是順序 、 鏈式 、 索引 和 散列 。10. 數據的運算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。11. 一個算法的效率可分為 時間 效率和 空間 效率。12. 在順序表中插入或刪除一個元素，需要平均移動 表中一半元素，具體移動的元素個數與 表

3、長和該元素在表中的位置 有關。13. 線性表中結點的集合是 有限 的，結點間的關系是 一對一 的。14. 向一個長度為n的向量的第i個元素(1in+1)之前插入一個元素時，需向后移動 n-i+1 個元素。15. 向一個長度為n的向量中刪除第i個元素(1in)時，需向前移動 n-i 個元素。16. 在順序表中訪問任意一結點的時間復雜度均為 O(1) ，因此，順序表也稱為 隨機存取 的數據結構。17. 順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。18在單鏈表中，除了首元結點外，任一結點的存儲位置由 其直接前驅結點的鏈域的值 指示。19 在n個結點

4、的單鏈表中要刪除已知結點*p，需找到它的前驅結點的地址，其時間復雜度為O（n）。20. 向量、棧和隊列都是 線性 結構，可以在向量的 任何 位置插入和刪除元素；對于棧只能在 棧頂 插入和刪除元素；對于隊列只能在 隊尾 插入和 隊首 刪除元素。21. 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為 棧頂 。不允許插入和刪除運算的一端稱為 棧底 。22. 隊列 是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。23. 不包含任何字符（長度為0）的串 稱為空串； 由一個或多個空格（僅由空格符）組成的串 稱為空白串。24. 子串的定位運算稱為串的模式匹配； 被匹配的主串 稱為

5、目標串， 子串 稱為模式。25. 假設有二維數組A6×8，每個元素用相鄰的6個字節存儲，存儲器按字節編址。已知A的起始存儲位置（基地址）為1000，則數組A的體積（存儲量）為 288 B ；末尾元素A57的第一個字節地址為 1282 ；若按行存儲時，元素A14的第一個字節地址為 (8+4)×6+1000=1072 ；若按列存儲時，元素A47的第一個字節地址為 (6×74)×61000）1276 。26 由個結點所構成的二叉樹有 5 種形態。 27. 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個分支結點和 26-1 =32 個葉子

6、。注：滿二叉樹沒有度為1的結點，所以分支結點數就是二度結點數。28 一棵具有個結點的完全二叉樹，它的深度為 9 。（ 注：用ë log2(n) û+1= ë 8.xx û+1=929設一棵完全二叉樹有700個結點，則共有 350 個葉子結點。答：最快方法：用葉子數n/2350 30 設一棵完全二叉樹具有1000個結點，則此完全二叉樹有 500 個葉子結點，有 499 個度為2的結點，有 1 個結點只有非空左子樹，有 0 個結點只有非空右子樹。答：最快方法：用葉子數n/2500 ，n2=n0-1=499。 另外，最后一結點為2i屬于左葉子，右葉子是空的，所

7、以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數0.31在數據的存放無規律而言的線性表中進行檢索的最佳方法是 順序查找（線性查找） 。32. 線性有序表（a1，a2，a3，a256)是從小到大排列的，對一個給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索 8 次。設有100個結點，用二分法查找時，最大比較次數是 7 。33. 假設在有序線性表a20上進行折半查找，則比較一次查找成功的結點數為1；比較兩次查找成功的結點數為 2 ；比較四次查找成功的結點數為 8 ；平均查找長度為 3.7 。解：顯然，平均查找長度O（log2n）<

8、;5次（25）。但具體是多少次，則不應當按照公式來計算（即（21×log221）/204.6次并不正確！）。因為這是在假設n2m-1的情況下推導出來的公式。應當用窮舉法羅列：全部元素的查找次數為（12×24×38×45×5）74； ASL74/20=3.7 ！34折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素 28，6，12，20 比較大小。35. 在各種查找方法中，平均查找長度與結點個數n無關的查找方法是 散列查找 。36. 散列法存儲的基本思想是由 關鍵字的值 決定數據的存

9、儲地址。二、判斷正誤（在正確的說法后面打勾，反之打叉）（ × ）1. 鏈表的每個結點中都恰好包含一個指針。 答：錯誤。鏈表中的結點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結點的指針。（ × ）2. 鏈表的物理存儲結構具有同鏈表一樣的順序。錯，鏈表的存儲結構特點是無序，而鏈表的示意圖有序。（ × ）3. 鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續的各個單元向前移動。錯，鏈表的結點不會移動，只是指針內容改變。（ × ）4. 線性表的每個結點只能是一個簡單類型，而鏈表

10、的每個結點可以是一個復雜類型。錯，混淆了邏輯結構與物理結構，鏈表也是線性表！且即使是順序表，也能存放記錄型數據。（ × ）5. 順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。 錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜”（ × ）6. 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優點。順序存儲方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除一個數據元素，平均需移動表長一半個數的數據元素。（ × ）7. 線性表在物理存儲空間中也一定是連續的。錯，線性表有兩種存儲方式，

11、順序存儲和鏈式存儲。后者不要求連續存放。（ × ）8. 線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。（ × ）9. 順序存儲方式只能用于存儲線性結構。錯誤。順序存儲方式不僅能用于存儲線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬于非線性結構，但其最佳存儲方式是順序存儲方式。（后一節介紹）（ × ）10. 線性表的邏輯順序與存儲順序總是一致的。錯，理由同7。鏈式存儲就無需一致。（ × ）11. 線性表的每個結點只能是一個簡單類型，而鏈表的

12、每個結點可以是一個復雜類型。 錯，線性表是邏輯結構概念，可以順序存儲或鏈式存儲，與元素數據類型無關。（ × ）12. 在表結構中最常用的是線性表，棧和隊列不太常用。 錯，不一定吧？調用子程序或函數常用，CPU中也用隊列。（ ）13. 棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。（ ）14. 對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。 正確，都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（ × ）15. 棧和鏈表是兩種不同的數據結構。 錯，棧是邏輯結構的概念，是特殊殊線性表，而鏈表是存儲結

13、構概念，二者不是同類項。（ × ）16. 棧和隊列是一種非線性數據結構。 錯，他們都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（ ）17. 棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。 （ ）18. 兩個棧共享一片連續內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。 （ × ）19. 隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。 錯，后半句不對。（ × ）20. 一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。 錯，有可能。（ ）21. 若二叉樹用

14、二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n1個非空指針域。（ × ）22.二叉樹中每個結點的兩棵子樹的高度差等于1。 （ ）23.二叉樹中每個結點的兩棵子樹是有序的。 （ × ）24.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。 （ × ）25.二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。 （應當是二叉排序樹的特點）（ × ）26.二叉樹中所有結點個數是2k-1-1，其中k是樹的深度。（應2i-1） （ × ）27.二叉樹中所有結點，如果不存在非空左

15、子樹，則不存在非空右子樹。 （ × ）28.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2i1個結點。（應2i-1）（ ）29.用二叉鏈表法（link-rlink）存儲包含n個結點的二叉樹，結點的2n個指針區域中有n+1個為空指針。（ ）30.具有12個結點的完全二叉樹有5個度為2的結點。三、單項選擇題（ B ）1. 非線性結構是數據元素之間存在一種：A）一對多關系 B）多對多關系 C）多對一關系 D）一對一關系（ C ）2. 數據結構中，與所使用的計算機無關的是數據的 結構；A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲（ C ）3. 算法分析的目的是：A

16、) 找出數據結構的合理性 B) 研究算法中的輸入和輸出的關系C) 分析算法的效率以求改進 D) 分析算法的易懂性和文檔性（ A ）4. 算法分析的兩個主要方面是：A) 空間復雜性和時間復雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數據復雜性和程序復雜性（ C ）5. 計算機算法指的是：A) 計算方法 B) 排序方法 C) 解決問題的有限運算序列 D) 調度方法（ B ）6. 計算機算法必須具備輸入、輸出和 等5個特性。A) 可行性、可移植性和可擴充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩定性 D) 易讀性、穩定性和安全性（ C ）7數據在計算機存儲器內表示時，物理地址

17、與邏輯地址相同并且是連續的，稱之為：（A）存儲結構 （B）邏輯結構 （C）順序存儲結構 （D）鏈式存儲結構（ B ）8.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是 （A）110 （B）108 （C）100 （D）120（ A ）9. 在n個結點的順序表中，算法的時間復雜度是O（1）的操作是：（A） 訪問第i個結點（1in）和求第i個結點的直接前驅（2in） （B） 在第i個結點后插入一個新結點（1in）（C） 刪除第i個結點（1in）（D） 將n個結點從小到大排序（ B ）10. 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 個

18、元素（A）8 （B）63.5 （C）63 （D）7（ A ）11. 鏈接存儲的存儲結構所占存儲空間：（A） 分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針（B） 只有一部分，存放結點值(C） 只有一部分，存儲表示結點間關系的指針（D） 分兩部分，一部分存放結點值，另一部分存放結點所占單元數（ B ）12. 鏈表是一種采用 存儲結構存儲的線性表；（A）順序 （B）鏈式 （C）星式 （D）網狀（ D ）13. 線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址:（A）必須是連續的 （B）部分地址必須是連續的（C）一定是不連續的 （D）連續或不連續都可以（ B ）14 線性表在 情況下適用于使用鏈式結構實現。（）需經常修改中的結點值 （）需不斷對進行刪除插入 （）中含有大量的結點 （）中結點結構復雜（ B ）15.棧中元素的進出原則是 先進先出 后進先出 棧空則進 棧滿則出（ C ）16. 若已知一個棧的入棧序列是1，2，3，n，其輸出序列為