第2章線性表參***
一、填空
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. 鍊錶的每個結點中都恰好包含乙個指標。
答：錯誤。鍊錶中的結點可含多個指標域，分別存放多個指標。例如，雙向鍊錶中的結點可以含有兩個指標域，分別存放指向其直接前趨和直接後繼結點的指標。
（ × ）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． 線性表ｌ在情況下適用於使用鏈式結構實現。
（ａ）需經常修改ｌ中的結點值 （ｂ）需不斷對ｌ進行刪除插入
（ｃ）ｌ中含有大量的結點中結點結構複雜
（ c ）9． 單鏈表的儲存密度
（ａ）大於1； （ｂ）等於1； （ｃ）小於1； （ｄ）不能確定
（ b ）10． 設a1、a2、a3為3個結點，整數p0，3，4代表位址，則如下的鏈式儲存結構稱為
（ａ）迴圈鍊錶 （ｂ）單鏈表 （ｃ）雙向迴圈鍊錶 （ｄ）雙向鍊錶
四、簡答題
1. 【嚴題集2.3②】試比較順序儲存結構和鏈式儲存結構的優缺點。在什麼情況下用順序錶比鍊錶好？
答：① 順序儲存時，相鄰資料元素的存放位址也相鄰（邏輯與物理統一）；要求記憶體中可用儲存單元的位址必須是連續的。
優點：儲存密度大（＝1？），儲存空間利用率高。缺點：插入或刪除元素時不方便。
②鏈式儲存時，相鄰資料元素可隨意存放，但所佔儲存空間分兩部分，一部分存放結點值，另一部分存放表示結點間關係的指標
優點：插入或刪除元素時很方便，使用靈活。缺點：儲存密度小（<1），儲存空間利用率低。
順序表適宜於做查詢這樣的靜態操作；鍊錶宜於做插入、刪除這樣的動態操作。
若線性表的長度變化不大，且其主要操作是查詢，則採用順序表；
若線性表的長度變化較大，且其主要操作是插入、刪除操作，則採用鍊錶。
2 .【嚴題集2.1①】描述以下三個概念的區別：頭指標、頭結點、首元結點（第乙個元素結點）。在單鏈表中設定頭結點的作用是什麼？
答：首元結點是指煉表中儲存線性表中第乙個資料元素a1的結點。為了操作方便，通常在鍊錶的首元結點之前附設乙個結點，稱為頭結點，該結點的資料域中不儲存線性表的資料元素，其作用是為了對鍊錶進行操作時，可以對空表、非空表的情況以及對首元結點進行統一處理。
頭指標是指向鍊錶中第乙個結點（或為頭結點或為首元結點）的指標。若煉表中附設頭結點，則不管線性表是否為空表，頭指標均不為空。否則表示空表的鍊錶的頭指標為空。
這三個概念對單鏈表、雙向鍊錶和迴圈鍊錶均適用。是否設定頭結點，是不同的儲存結構表示同一邏輯結構的問題。
頭結點頭指標首元結點
簡而言之，
頭指標是指向鍊錶中第乙個結點（或為頭結點或為首元結點）的指標；
頭結點是在鍊錶的首元結點之前附設的乙個結點；資料域內只放空表標誌和表長等資訊（內放頭指標？那還得另配乙個頭指標！！！）
首元素結點是指煉表中儲存線性表中第乙個資料元素a1的結點。
資料結構第2章線性表答案
第2章自測卷答案姓名班級 一 填空 每空1分，共13分 1.嚴題集2.2 在順序表中插入或刪除乙個元素，需要平均移動表中一半元素，具體移動的元素個數與表長和該元素在表中的位置有關。2.線性表中結點的集合是有限的，結點間的關係是一對一的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙...
資料結構 第2章線性表
第2章線性表 一選擇題 1 下述哪一條是順序儲存結構的優點？北方交通大學 2001 一 4 2分 a 儲存密度大 b 插入運算方便 c 刪除運算方便 d 可方便地用於各種邏輯結構的儲存表示 2 下面關於線性表的敘述中，錯誤的是哪乙個？北方交通大學 2001 一 14 2分 a 線性表採用順序儲存，必...
資料結構第2章線性表
第2章線性表自測卷 一 填空 1.在順序表中插入或刪除乙個元素，需要平均移動元素，具體移動的元素個數 與有關。2.線性表中結點的集合是的，結點間的關係是的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙個元素時，需向後移動個元素。4.向乙個長度為n的向量中刪除第i個元素 1 i n...