資料結構複習資料
一、填空題
1. 資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。
2. 資料結構被形式地定義為（d, r），其中d是資料元素的有限集合，r是d上的關係有限集合。
3. 資料結構包括資料的邏輯結構 、資料的儲存結構和資料的運算這三個方面的內容。
4. 資料結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構 。
5. 線性結構中元素之間存在一對一關係，樹形結構中元素之間存在一對多關係，圖形結構中元素之間存在多對多關係。
6． **性結構中，第乙個結點沒有前驅結點，其餘每個結點有且只有 1個前驅結點；最後乙個結點沒有後續結點，其餘每個結點有且只有1個後續結點。
7. 在樹形結構中，樹根結點沒有前驅結點，其餘每個結點有且只有 1 個前驅結點；葉子結點沒有後續結點，其餘每個結點的後續結點數可以任意多個 。
8. 在圖形結構中，每個結點的前驅結點數和後續結點數可以任意多個 。
9．資料的儲存結構可用四種基本的儲存方法表示，它們分別是順序 、 鏈式 、 索引和雜湊 。
10. 資料的運算最常用的有5種，它們分別是插入 、 刪除、修改、 查詢 、排序。
11. 乙個演算法的效率可分為時間效率和空間效率。
12. 在順序表中插入或刪除乙個元素，需要平均移動表中一半元素，具體移動的元素個數與表長和該元素在表中的位置有關。
13. 線性表中結點的集合是有限的，結點間的關係是一對一的。
14. 向乙個長度為n的向量的第i個元素(1≤i≤n+1)之前插入乙個元素時，需向後移動 n-i+1 個元素。
15. 向乙個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動 n-i 元素。
16. 在順序表中訪問任意一結點的時間複雜度均為 o(1) ，因此，順序表也稱為隨機訪問的資料結構。
17. 順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。
18．在單鏈表中，除了首元結點外，任一結點的儲存位置由其直接前驅結點的鏈域的值指示。
19． 在n個結點的單鏈表中要刪除已知結點*p，需找到它的前驅結點的位址，其時間複雜度為o（n）。
20. 向量、棧和佇列都是線性結構，可以在向量的任何位置插入和刪除元素；對於棧只能在棧頂插入和刪除元素；對於佇列只能在隊尾插入和隊首刪除元素。
21. 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂 。不允許插入和刪除運算的一端稱為棧底 。
22. 佇列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。
23. 不包含任何字元（長度為0）的串稱為空串； 由乙個或多個空格（僅由空格符）組成的串稱為空白串。
24. 子串的定位運算稱為串的模式匹配； 被匹配的主串稱為目標串， 子串稱為模式。
25. 假設有二維陣列a6×8，每個元素用相鄰的6個位元組儲存，儲存器按位元組編址。已知a的起始儲存位置（基位址）為1000，則陣列a的體積（儲存量）為 288 b ；末尾元素a57的第乙個位元組位址為 1282 ；若按行儲存時，元素a14的第乙個位元組位址為 (8+4)×6+1000=1072 ；若按列儲存時，元素a47的第乙個位元組位址為 (6×7＋4)×6＋1000）＝1276 。
26． 由３個結點所構成的二叉樹有 5 種形態。
27. 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個分支結點和 26-1 =32 個葉子。
注：滿二叉樹沒有度為1的結點，所以分支結點數就是二度結點數。
28． 一棵具有２５７個結點的完全二叉樹，它的深度為 9 。
（ 注：用 log2(n) +1= +1=9
29．設一棵完全二叉樹有700個結點，則共有 350 個葉子結點。
答：最快方法：用葉子數＝[n/2]＝350
30． 設一棵完全二叉樹具有1000個結點，則此完全二叉樹有 500 個葉子結點，有 499 個度為2的結點，有 1 個結點只有非空左子樹，有 0 個結點只有非空右子樹。
答：最快方法：用葉子數＝[n/2]＝500 ，n2=n0-1=499。
另外，最後一結點為2i屬於左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數＝0.
31．在資料的存放無規律而言的線性表中進行檢索的最佳方法是順序查詢（線性查詢） 。
32. 線性有序表（a1，a2，a3，…，a256)是從小到大排列的，對乙個給定的值k，用二分法檢索表中與k相等的元素，在查詢不成功的情況下，最多需要檢索 8 次。設有100個結點，用二分法查詢時，最大比較次數是 7 。
33. 假設在有序線性表a[20]上進行折半查詢，則比較一次查詢成功的結點數為1；比較兩次查詢成功的結點數為 2 ；比較四次查詢成功的結點數為 8 ；平均查詢長度為 3.7 。
解：顯然，平均查詢長度＝o（log2n）<5次（25）。但具體是多少次，則不應當按照公式
來計算（即（21×log221）/20＝4.6次並不正確！）。因為這是在假設n＝2m-1的情況下推導出來的公式。應當用窮舉法羅列：
全部元素的查詢次數為＝（1＋2×2＋4×3＋8×4＋5×5）＝74； asl＝74/20=3.7 ！！！
34．折半查詢有序表（4，6，12，20，28，38，50，70，88，100），若查詢表中元素20，它將依次與表中元素 28，6，12，20 比較大小。
35. 在各種查詢方法中，平均查詢長度與結點個數n無關的查詢方法是雜湊查詢 。
36. 雜湊法儲存的基本思想是由關鍵字的值決定資料的儲存位址。
二、判斷正誤（在正確的說法後面打勾，反之打叉）
（ × ）1. 鍊錶的每個結點中都恰好包含乙個指標。
答：錯誤。鍊錶中的結點可含多個指標域，分別存放多個指標。例如，雙向鍊錶中的結點可以含有兩個指標域，分別存放指向其直接前趨和直接後繼結點的指標。
（ × ）2. 鍊錶的物理儲存結構具有同煉表一樣的順序。錯，鍊錶的儲存結構特點是無序，而鍊錶的示意圖有序。
（ × ）3. 鍊錶的刪除演算法很簡單，因為當刪除鏈中某個結點後，計算機會自動地將後續的各個單元向前移動。錯，鍊錶的結點不會移動，只是指標內容改變。
（ × ）4. 線性表的每個結點只能是乙個簡單型別，而鍊錶的每個結點可以是乙個複雜型別。
錯，混淆了邏輯結構與物理結構，鍊錶也是線性表！且即使是順序表，也能存放記錄型資料。
（ × ）5. 順序表結構適宜於進行順序訪問，而鍊錶適宜於進行隨機訪問。
錯，正好說反了。順序表才適合隨機訪問，鍊錶恰恰適於「順藤摸瓜」
（ × ）6. 順序儲存方式的優點是儲存密度大，且插入、刪除運算效率高。
錯，前一半正確，但後一半說法錯誤，那是鏈式儲存的優點。順序儲存方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除乙個資料元素，平均需移動表長一半個數的資料元素。
（ × ）7. 線性表在物理儲存空間中也一定是連續的。
錯，線性表有兩種儲存方式，順序儲存和鏈式儲存。後者不要求連續存放。
（ × ）8. 線性表在順序儲存時，邏輯上相鄰的元素未必在儲存的物理位置次序上相鄰。
錯誤。線性表有兩種儲存方式，在順序儲存時，邏輯上相鄰的元素在儲存的物理位置次序上也相鄰。
（ × ）9. 順序儲存方式只能用於儲存線性結構。
錯誤。順序儲存方式不僅能用於儲存線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬於非線性結構，但其最佳儲存方式是順序儲存方式。（後一節介紹）
（ × ）10. 線性表的邏輯順序與儲存順序總是一致的。
錯，理由同7。鏈式儲存就無需一致。
（ × ）11. 線性表的每個結點只能是乙個簡單型別，而鍊錶的每個結點可以是乙個複雜型別。
錯，線性表是邏輯結構概念，可以順序儲存或鏈式儲存，與元素資料型別無關。
（ × ）12. 在表結構中最常用的是線性表，棧和佇列不太常用。
錯，不一定吧？呼叫子程式或函式常用，cpu中也用佇列。
（ √ ）13. 棧是一種對所有插入、刪除操作限於在表的一端進行的線性表，是一種後進先出型結構。
（ √ ）14. 對於不同的使用者，乙個表結構既可以是棧，也可以是佇列，也可以是線性表。
正確，都是線性邏輯結構，棧和佇列其實是特殊的線性表，對運算的定義略有不同而已。
（ × ）15. 棧和鍊錶是兩種不同的資料結構。
錯，棧是邏輯結構的概念，是特殊殊線性表，而鍊錶是儲存結構概念，二者不是同類項。
（ × ）16. 棧和佇列是一種非線性資料結構。
錯，他們都是線性邏輯結構，棧和佇列其實是特殊的線性表，對運算的定義略有不同而已。
（ √ ）17. 棧和佇列的儲存方式既可是順序方式，也可是鏈結方式。
（ √ ）18. 兩個棧共享一片連續記憶體空間時，為提高記憶體利用率，減少溢位機會，應把兩個棧的棧底分別設在這片記憶體空間的兩端
（ × ）19. 隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進後出型結構。
錯，後半句不對。
（ × ）20. 乙個棧的輸入序列是12345，則棧的輸出序列不可能是12345。
錯，有可能。
（ √ ）21. 若二叉樹用二叉鍊錶作存貯結構，則在n個結點的二叉樹鍊錶中只有n—1個非空指標域。
（ × ）22.二叉樹中每個結點的兩棵子樹的高度差等於1。
（ √ ）23.二叉樹中每個結點的兩棵子樹是有序的。
資料結構 c語言版 複習
積少成多，爭取每天進步一點。資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科 2.資料結構被形式地定義為 d r 其中d是資料元素的有限集合 r是d上的關係有限集合 3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運...
資料結構 c語言版 複習
資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是資料元素的有限集合，r是d上的關係有限集合。3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運算這三個方面的內容。4.資料...
資料結構 C語言版
考試大綱將陸續公布 計算機應用基礎考試大綱 主要考查計算機應用基礎知識，參考參考用書課後練習內容。其它同型別的計算機應用基礎教材均可作為複習用書 高等數學考試大綱 一 函式 二 極限 1 數列極限的概念 2 數列極限的性質 3 函式極限的概念 4 函式極限的定理 5 無窮小量和無窮大量 6 兩個重要...