第二章線性表習題請依據各人的時間和需求選作至少一半習題，答案僅供參考，如果直接抄就太對不起自己了。

一、填空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）108（C）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.5（C）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；（Ｄ）不