積少成多，爭取每天進步一點。
資料結構複習資料
一、填空題
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
a2a3
...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．折半查詢有序表（4612
2028
3850
7088
100）
若查詢表中元素20
它將依次與表中元素 28612
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.二叉樹中每個結點的兩棵子樹是有序的
（×）24.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹
（×）25.二叉樹中每個結點的關鍵字值大於其左非空子樹（若存在的話）所有結點的關鍵字值
且小於其右非空子樹（若存在的話）所有結點的關鍵字值
（應當是二叉排序樹的特點）
（×）26.二叉樹中所有結點個數是2k-1-1
其中k是樹的深度
（應2i-1）
（×）27.二叉樹中所有結點
如果不存在非空左子樹
則不存在非空右子樹
（×）28.對於一棵非空二叉樹
它的根結點作為第一層
則它的第i層上最多能有2i-1個結點
（應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) 找出資料結構的合理性 b) 研究演算法中的輸入和輸出的關係
c) 分析演算法的效率以求改進 d) 分析演算法的易懂性和文件性
（ a ）4. 演算法分析的兩個主要方面是：
a) 空間複雜性和時間複雜性 b) 正確性和簡明性
c) 可讀性和文件性d) 資料複雜性和程式複雜性
（ c ）5. 計算機演算法指的是：
a) 計算方法 b) 排序方法 c) 解決問題的有限運算序列 d) 排程方法
（ b ）6. 計算機演算法必須具備輸入、輸出和等5個特性
a) 可行性、可移植性和可擴充性 b) 可行性、確定性和有窮性
c) 確定性、有窮性和穩定性d) 易讀性、穩定性和安全性
（ c ）7．資料在計算機儲存器內表示時
實體地址與邏輯位址相同並且是連續的
稱之為：
（a）儲存結構（b）邏輯結構（c）順序儲存結構（d）鏈式儲存結構
（ b ）8.乙個向量第乙個元素的儲存位址是100
每個元素的長度為2
則第5個元素的位址是
（a）110 （b）108c）100 （d）120
（ a ）9. 在n個結點的順序表中
演算法的時間複雜度是o（1）的操作是：
（a）訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n）
（b）在第i個結點後插入乙個新結點（1≤i≤n）
（c）刪除第i個結點（1≤i≤n）
（d）將n個結點從小到大排序
（ b ）10. 向乙個有127個元素的順序表中插入乙個新元素並保持原來順序不變
平均要移動個元素
（a）8 （b）63.5c）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. 若已知乙個棧的入棧序列是123
...n
其輸出序列為p1
p2p3
...pn
若p1=n
則pi為
ａ．i ｂ．n=i ｃ．n-i+1 ｄ．不確定
（ b ）17. 判定乙個棧st（最多元素為m0）為空的條件是
ａ．st->top<>0 ｂ．st->top=0 ｃ．st->top<>m0 ｄ．st->top=m0
（ c ）18. 在乙個圖中
所有頂點的度數之和等於圖的邊數的倍
a．1/2b. 1c. 2d. 4
（ b ）19. 在乙個有向圖中
所有頂點的入度之和等於所有頂點的出度之和的倍
a．1/2b. 1c. 2d. 4
（ b ）20. 有8個結點的無向圖最多有條邊
a．14b. 28c. 56d. 112 （ c ）21. 有8個結點的有向完全圖有條邊
a．14b. 28c. 56d. 112 （ b ）22．在表長為ｎ的鍊錶中進行線性查詢
它的平均查詢長度為
（ a ）23．折半查詢有序表（4610
1220
3050
7088
100）
若查詢表中元素58
則它將依次與表中比較大小
查詢結果是失敗
a．20
7030
50 b．30
8870
50 c．20
50 d．30
8850
（ c ）24．對22個記錄的有序表作折半查詢
當查詢失敗時
至少需要比較次關鍵字
a．3 b．4c．5d． 6
（ a ）25. 鍊錶適用於查詢
a．順序 b．二分法 c．順序
也能二分法 d．隨機
???? ?? ??1 1
資料結構 c語言版 複習
資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是資料元素的有限集合，r是d上的關係有限集合。3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運算這三個方面的內容。4.資料...
資料結構 c語言版 複習
資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是資料元素的有限集合，r是d上的關係有限集合。3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運算這三個方面的內容。4.資料...
資料結構 C語言版
考試大綱將陸續公布 計算機應用基礎考試大綱 主要考查計算機應用基礎知識，參考參考用書課後練習內容。其它同型別的計算機應用基礎教材均可作為複習用書 高等數學考試大綱 一 函式 二 極限 1 數列極限的概念 2 數列極限的性質 3 函式極限的概念 4 函式極限的定理 5 無窮小量和無窮大量 6 兩個重要...