第一章緒論
一、填空題
1、資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。
2、資料結構被形式地定義為（d, r），其中d是資料元素的有限集合，r是d上的關係有限集合。
3、資料結構包括資料的邏輯結構 、資料的儲存結構和資料的運算這三個方面的內容。
4、資料結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構 。
5、線性結構中元素之間存在一對一關係，樹形結構中元素之間存在一對多關係，圖形結構中元素之間存在多對多關係。
6、**性結構中，第乙個結點沒有前驅結點，其餘每個結點有且只有 1個前驅結點；最後乙個結點沒有後續結點，其餘每個結點有且只有1個後續結點。
7、在樹形結構中，樹根結點沒有前驅結點，其餘每個結點有且只有 1 個前驅結點；葉子結點沒有後續結點，其餘每個結點的後續結點數可以任意多個 。
8、在圖形結構中，每個結點的前驅結點數和後續結點數可以任意多個 。
9、資料的儲存結構可用四種基本的儲存方法表示，它們分別是順序 、鏈式 、索引和雜湊。
10、資料的運算最常用的有5種，它們分別是插入 、 刪除、修改、 查詢 、排序。
11、乙個演算法的效率可分為時間效率和空間效率。
二、單項選擇題
（ 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) 易讀性、穩定性和安全性
三、分析下面各程式段的時間複雜度
四、設有資料邏輯結構s=（d,r），試按各小題所給條件畫出這些邏輯結構的圖示，並確定相對於關係r，哪些結點是開始結點，哪些結點是終端結點？
}答： d1→d2→d3→d4 d1—無直接前驅，是首結點 d4—無直接後繼是尾結點
2。d=
r=答： 此圖為樹形結構（略） d1—無直接前驅，是根結點 d2,d5,d7,d9—無直接後繼是葉子結點
3．d=
r=答： 此圖為圖形結構（略） d1，d2—無直接前驅，是開始結點 d6,d7—無直接後繼是終端結點
第2章線性表
一、填空
1、在順序表中插入或刪除乙個元素，需要平均移動表中一半元素，具體移動的元素個數與表長和該元素在表中的位置有關。
2、線性表中結點的集合是有限的，結點間的關係是一對一的。
3、向乙個長度為n的向量的第i個元素(1≤i≤n+1)之前插入乙個元素時，需向後移動 n-i+1 個元素。
4、向乙個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動 n-i 個元素。
5、在順序表中訪問任意一結點的時間複雜度均為 o(1) ，因此，順序表也稱為隨機訪問的資料結構。
6、順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。
7、在單鏈表中，除了首元結點外，任一結點的儲存位置由其直接前驅結點的指標域的值指示。
8、在n個結點的單鏈表中要刪除已知結點*p，需找到它的前驅結點的位址，其時間複雜度為o（n）。
二、判斷正誤（在正確的說法後面打勾，反之打叉）
（ × ）1、鍊錶的每個結點中都恰好包含乙個指標。
答：錯誤。鍊錶中的結點可含多個指標域，分別存放多個指標。例如，雙向鍊錶中的結點可以含有兩個指標域，分別存放指向其直接前趨和直接後繼結點的指標。
（ × ）2、鍊錶的物理儲存結構具有同煉表一樣的順序。
錯，鍊錶的儲存結構特點是無序，而鍊錶的示意圖有序。
（ × ）3、鍊錶的刪除演算法很簡單，因為當刪除鏈中某個結點後，計算機會自動地將後續的各個單元向前移動。錯，鍊錶的結點不會移動，只是指標內容改變。
（ × ）4、線性表的每個結點只能是乙個簡單型別，而鍊錶的每個結點可以是乙個複雜型別。
錯，混淆了邏輯結構與物理結構，鍊錶也是線性表！且即使是順序表，也能存放記錄型資料。
（ × ）5、順序表結構適宜於進行順序訪問，而鍊錶適宜於進行隨機訪問。
錯，正好說反了。順序表才適合隨機訪問，鍊錶恰恰適於「順藤摸瓜」
（ × ）6、順序儲存方式的優點是儲存密度大，且插入、刪除運算效率高。
錯，前一半正確，但後一半說法錯誤，那是鏈式儲存的優點。順序儲存方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除乙個資料元素，平均需移動表長一半個數的資料元素。
（ × ）7、線性表在物理儲存空間中也一定是連續的。
錯，線性表有兩種儲存方式，順序儲存和鏈式儲存。後者不要求連續存放。
（ × ）8、線性表在順序儲存時，邏輯上相鄰的元素未必在儲存的物理位置次序上相鄰。
錯誤。線性表有兩種儲存方式，在順序儲存時，邏輯上相鄰的元素在儲存的物理位置次序上也相鄰。
（ × ）9、順序儲存方式只能用於儲存線性結構。
錯誤。順序儲存方式不僅能用於儲存線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬於非線性結構，但其最佳儲存方式是順序儲存方式。（後一節介紹）
（ × ）10、線性表的邏輯順序與儲存順序總是一致的。
錯，理由同7。鏈式儲存就無需一致。
三、單項選擇題
（ c ）1、資料在計算機儲存器內表示時，實體地址與邏輯位址相同並且是連續的，稱之為：
（a）儲存結構 （b）邏輯結構 （c）順序儲存結構 （d）鏈式儲存結構
（ b ）2、乙個向量第乙個元素的儲存位址是100，每個元素的長度為2，則第5個元素的位址是
（a）110 （b）108c）100 （d）120
（ a ）3、在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 ）4、向乙個有127個元素的順序表中插入乙個新元素並保持原來順序不變，平均要移動個元素。
（a）8 （b）63.5c）63 （d）7
（ a ）5、鏈結儲存的儲存結構所佔儲存空間：
（a） 分兩部分，一部分存放結點值，另一部分存放表示結點間關係的指標
（b） 只有一部分，存放結點值
（c） 只有一部分，儲存表示結點間關係的指標
（d） 分兩部分，一部分存放結點值，另一部分存放結點所佔單元數
（ b ）6、鍊錶是一種採用儲存結構儲存的線性表。
（a）順序 （b）鏈式c）星式 （d）網狀
（ d ）7、線性表若採用鏈式儲存結構時，要求記憶體中可用儲存單元的位址:
（a）必須是連續的 （b）部分位址必須是連續的
（c）一定是不連續的 （d）連續或不連續都可以
（ b ）8、線性表ｌ在情況下適用於使用鏈式結構實現。
（a）需經常修改ｌ中的結點值 （b）需不斷對ｌ進行刪除插入
（c）ｌ中含有大量的結點d）ｌ中結點結構複雜
（ c ）9、單鏈表的儲存密度
（a）大於1； （b）等於1； （c）小於1； （d）不能確定
（ b ）10、設a1、a2、a3為3個結點，整數p0，3，4代表位址，則如下的鏈式儲存結構稱為（ ）。
（a）迴圈鍊錶 （b）單鏈表 （c）雙向迴圈鍊錶 （d）雙向鍊錶
四、簡答題
1.試比較順序儲存結構和鏈式儲存結構的優缺點。在什麼情況下用順序錶比鍊錶好？
資料結構第2章習題
一 填空 1.在順序表中插入或刪除乙個元素，需要平均移動元素，具體移動的元素個數 與有關。2.線性表中結點的集合是的，結點間的關係是的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙個元素時，需向後移動個元素。4.向乙個長度為n的向量中刪除第i個元素 1 i n 時，需向前移動個元...
資料結構習題第10章
第10章內部排序 一 選擇題 1.下列排序方法中，穩定的排序方法是 a.簡單選擇排序 b.氣泡排序 c.希爾排序 d.快速排序 2.在下列排序演算法中,哪乙個演算法的時間複雜度與初始排序無關 a.直接插入排序 b.氣泡排序 c.快速排序 d.簡單選擇排序 3.排序方法中，從未排序序列中依次取出元素與...
資料結構習題 第1章
第一章概論自測題姓名班級 一 填空題 每空1分，共33分 1.乙個計算機系統包括和兩大部分。2.一台計算機中全部程式的集合，稱為這台計算機的 3.計算機軟體可以分為軟體和軟體兩大類。科學計算程式包屬於診斷程式屬於 4.一種用助憶符號來表示機器指令的操作符和運算元的語言是 5.資料結構是一門研究非數值...