第一章概論習題
一、填空題
1. 資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。
2. 資料結構被形式地定義為（d, r），其中d是資料元素的有限集合，r是d上的關係有限集合。
3. 資料結構包括資料的邏輯結構 、資料的儲存結構和資料的運算這三個方面的內容。
4. 資料結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構 。
5. 線性結構中元素之間存在一對一關係，樹形結構中元素之間存在一對多關係，圖形結構中元素之間存在多對多關係。
6． **性結構中，第乙個結點沒有前驅結點，其餘每個結點有且只有 1個前驅結點；最後乙個結點沒有後續結點，其餘每個結點有且只有1個後續結點。
7. 在樹形結構中，樹根結點沒有前驅結點，其餘每個結點有且只有 1 個前驅結點；葉子結點沒有後續結點，其餘每個結點的後續結點數可以任意多個 。
8. 在圖形結構中，每個結點的前驅結點數和後續結點數可以任意多個 。
9. 資料的運算最常用的有5種，它們分別是插入 、 刪除、修改、 查詢 、排序。
10. 乙個演算法的效率可分為時間效率和空間效率。
二、單項選擇題
（ 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) 易讀性、穩定性和安全性
三、簡答題
2.【嚴題集1.2②】資料結構和資料型別兩個概念之間有區別嗎？
答：簡單地說，資料結構定義了一組按某些關係結合在一起的陣列元素。資料型別不僅定義了一組帶結構的資料元素，而且還在其上定義了一組操作。
3. 簡述線性結構與非線性結構的不同點。
答：線性結構反映結點間的邏輯關係是一對一的，非線性結構反映結點間的邏輯關係是多對多的。
四、【嚴題集1.8④】分析下面各程式段的時間複雜度
一、 選擇題
1、若最常用的操作是讀取線性表中元素的值，則採用_______儲存方式最節省時間。
a 帶尾指標的單鏈表b 順序表
c 帶尾指標的單迴圈鍊錶 d 單鏈表
2、若某線性表中最常用的操作是在最後乙個元素之後插入乙個元素和刪除第乙個元素，則採用________儲存方式最節省運算時間。
a 不帶頭結點的單鏈表
b 不帶頭結點雙鏈表
c 帶頭結點的雙迴圈鍊錶
d 帶頭結點的單迴圈鍊錶
3、鍊錶不具有的特點是_______。
a 可隨機訪問任一元素
b 插入刪除不需要移動元素
c 不必事先估計儲存空間
d 所需空間與線性表長度成正比
4、串是
a 有限個字元的序列
b 任意個字母的序列
c 不少於乙個字元的序列
d 不少於乙個字母的序列
5、串是任意有限個______。
a 符號構成的集合
b 符號構成的序列
c 字元構成的集合
d 字元構成的序列
二、 判斷題
1、邏輯結構相同的資料其儲存結構一定相同。 （ ）
2、線性表採用鍊錶儲存後，線性表長度一定等於鍊錶所有結點的個數。（ ）
3、雙迴圈鍊錶中，任一結點的前趨指標均不空。（ ）
4、對鍊錶進行插入和刪除操作時，不必移動結點。（ ）
（ × ）1. 鍊錶的每個結點中都恰好包含乙個指標。
答：錯誤。鍊錶中的結點可含多個指標域，分別存放多個指標。例如，雙向鍊錶中的結點可以含有兩個指標域，分別存放指向其直接前趨和直接後繼結點的指標。
（ × ）2. 鍊錶的物理儲存結構具有同煉表一樣的順序。錯，鍊錶的儲存結構特點是無序，而鍊錶的示意圖有序。
（ × ）3. 鍊錶的刪除演算法很簡單，因為當刪除鏈中某個結點後，計算機會自動地將後續的各個單元向前移動。錯，鍊錶的結點不會移動，只是指標內容改變。
（ × ）4. 線性表的每個結點只能是乙個簡單型別，而鍊錶的每個結點可以是乙個複雜型別。
錯，混淆了邏輯結構與物理結構，鍊錶也是線性表！且即使是順序表，也能存放記錄型資料。
（ × ）5. 順序表結構適宜於進行順序訪問，而鍊錶適宜於進行隨機訪問。
錯，正好說反了。順序表才適合隨機訪問，鍊錶恰恰適於「順藤摸瓜」
（ × ）6. 順序儲存方式的優點是儲存密度大，且插入、刪除運算效率高。
錯，前一半正確，但後一半說法錯誤，那是鏈式儲存的優點。順序儲存方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除乙個資料元素，平均需移動表長一半個數的資料元素。
（ × ）7. 線性表在物理儲存空間中也一定是連續的。
錯，線性表有兩種儲存方式，順序儲存和鏈式儲存。後者不要求連續存放。
（ × ）8. 線性表在順序儲存時，邏輯上相鄰的元素未必在儲存的物理位置次序上相鄰。
錯誤。線性表有兩種儲存方式，在順序儲存時，邏輯上相鄰的元素在儲存的物理位置次序上也相鄰。
（ × ）9. 順序儲存方式只能用於儲存線性結構。
錯誤。順序儲存方式不僅能用於儲存線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬於非線性結構，但其最佳儲存方式是順序儲存方式。（後一節介紹）
（ × ）10. 線性表的邏輯順序與儲存順序總是一致的。
錯，理由同7。鏈式儲存就無需一致。
三、 填空題
1、在帶頭結點的單鏈表l中，若要刪除第乙個元素，則需要執行下列三條語句l→next＝u→next；free（u）。
2、在單鏈表l中，若要在指標p所指結點之後插入由指標s所指的結點，則需執行下列語句：s->next=p->next
3、在帶有頭結點的單鏈表l中，第乙個元素結點的指標是
4、雙迴圈鍊錶l中由指標p所指向的某結點為尾結點的條件是
1. 【嚴題集2.2①】在順序表中插入或刪除乙個元素，需要平均移動表中一半元素，具體移動的元素個數與表長和該元素在表中的位置有關。
2. 線性表中結點的集合是有限的，結點間的關係是一對一的。
3. 向乙個長度為n的向量的第i個元素(1≤i≤n+1)之前插入乙個元素時，需向後移動 n-i+1 個元素。
4. 向乙個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動 n-i 個元素。
5. 在順序表中訪問任意一結點的時間複雜度均為 o(1) ，因此，順序表也稱為隨機訪問的資料結構。
6. 【嚴題集2.2①】順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。
7. 【嚴題集2.2①】在單鏈表中，除了首元結點外，任一結點的儲存位置由其直接前驅結點的鏈域的值指示。
8． 在n個結點的單鏈表中要刪除已知結點*p，需找到它的前驅結點的位址，其時間複雜度為o（n）。
四、 演算法設計題
1、設有兩個單鏈表l和l1，各結點結構如下：
試畫出該鍊錶的結構圖，並編寫演算法，判斷單鏈表l1是否與單鏈表l相同，相同返回1，不同返回0。
五、簡答題
1. 【嚴題集2.3②】試比較順序儲存結構和鏈式儲存結構的優缺點。在什麼情況下用順序錶比鍊錶好？
答：① 順序儲存時，相鄰資料元素的存放位址也相鄰（邏輯與物理統一）；要求記憶體中可用儲存單元的位址必須是連續的。
優點：儲存密度大（＝1？），儲存空間利用率高。缺點：插入或刪除元素時不方便。
②鏈式儲存時，相鄰資料元素可隨意存放，但所佔儲存空間分兩部分，一部分存放結點值，另一部分存放表示結點間關係的指標
優點：插入或刪除元素時很方便，使用靈活。缺點：儲存密度小（<1），儲存空間利用率低。
順序表適宜於做查詢這樣的靜態操作；鍊錶宜於做插入、刪除這樣的動態操作。
若線性表的長度變化不大，且其主要操作是查詢，則採用順序表；
若線性表的長度變化較大，且其主要操作是插入、刪除操作，則採用鍊錶。
2 .【嚴題集2.1①】描述以下三個概念的區別：頭指標、頭結點、首元結點（第乙個元素結點）。在單鏈表中設定頭結點的作用是什麼？
資料結構習題庫
知識點 01 緒論 02 順序表 03 鍊錶 04 棧 05 鏈佇列 06 迴圈佇列 07 串 08 陣列的順序表示 09 稀疏矩陣 10 廣義表 11 二叉樹的基本概念 12 二叉樹遍歷 二叉樹性質 13 樹 樹與二叉樹的轉換 14 赫夫曼樹 15 圖的定義 圖的儲存 16 圖的遍歷 17 圖的生...
資料結構填空題題庫
1.線性結構中元素之間存在著 一對一 關係，樹型結構中元素之間存在著 一對多 關係。2.評價資料結構的兩條基本標準是 儲存需要量 和 運算的時間效率 3.演算法的五個特性是指 有窮性 確定性 可行性 輸入和輸出 4.資料的邏輯結構是從邏輯關係上描述資料，它與資料的 儲存結構 無關，是獨立於計算機的。...
資料結構與演算法習題庫重點
第一章緒論 一 選擇題 1 資料結構被形式地定義為 k，r 其中k是 b 的有限集合，r是k上的 d 的有限集合。a 演算法 b 資料元素 c 資料操作 d 邏輯結構 a 操作 b 映象 c 儲存 d 關係 2 演算法分析的目的是 c，演算法分析的兩個主要方面是 a。a 找出資料結構的合理性 b 研...