1、第 2 章自測卷答案一、填空1. 在順序表中插入或刪除一個元素，需要平均移動_表中一半 元素，具體移動的元素個數與 表長和該元素在表中的位置 _ 有關。2. 線性表中結點的集合是 有限的，結點間的關系是 一對一的。3. 向一個長度為n的向量的第i個元素(1 < i< n+1)之前插入一個元素時，需向后移動一n-i+1 _個元素。4. 向一個長度為n的向量中刪除第i個元素(1w i < n)時，需向前移動 _n-i 個元素。5. 在順序表中訪問任意一結點的時間復雜度均為0(1)_ ，因此，順序表也稱為 _隨機存取 _的數據結構。6?順序表中邏輯上相鄰的元素的物理位置必定相鄰。單

2、鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。7.在單鏈表中，除了首元結點外，任一結點的存儲位置由_其直接前驅結點的鏈域的值 _ 指示。&在n個結點的單鏈表中要刪除結點*p，需找到它的 前驅結點的地址，其時間復雜度為 0 (n)。、判斷正誤 ( 在正確的說法后面打勾，反之打叉 )(x ) 1.鏈表的每個結點中都恰好包含一個指針。答：錯誤。鏈表中的結點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結點可 以含有兩個指針域，分別存放指向其直接前趨和直接后繼結點的指針。(x ) 2.鏈表的物理存儲結構具有同鏈表一樣的順序。錯，鏈表的存儲結構特點是無序，而鏈表的示意圖有序。(x ) 3.鏈

3、表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算時機自動地將后續的各個單元向 前移動。錯，鏈表的結點不會移動，只是指針內容改變。(X ) 4.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。 錯，混淆了邏輯結構與物理結構，鏈表也是線性表！且即使是順序表，也能存放記錄型數據。(X ) 5.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。 錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜(X ) 6. 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。 錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優點。順序存儲方式插入、刪除運算效率較低，在表

4、長為 n 的順序表中，插入和刪除一個數據元素，平均需移動表長一半個數的數據(X ) 7.線性表在物理存儲空間中也一定是連續的。 錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。后者不要求連續存放。(X ) 8 .線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。 錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。(X ) 9.順序存儲方式只能用于存儲線性結構。性結構，但其最正確存儲方式是順序存儲方式。(后一節介紹)是屬于非線錯誤。順序存儲方式不僅能用于存儲線性結構，還可以用來存放非線性結構，例如完全二叉樹(X ) 10.線性表的邏輯順序與存

5、儲順序總是一致的。錯，理由同7。鏈式存儲就無需一致。三、單項選擇題(C ) 1.數據在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續的，稱之為：(A )存儲結構(B )邏輯結構(C)順序存儲結構(D)鏈式存儲結構(B ) 2?個向量第一個元素的存儲地址是100，每個元素的長度為 2,那么第5個元素的地址是 (A) 110( B) 108( C) 100( D) 120(A ) 3.在n個結點的順序表中，算法的時間復雜度是0 ( 1)的操作是：(A) 訪問第i個結點(1 < i< n)和求第i個結點的直接前驅(2< i < n)(B) 在第i個結點后插入一個新結點

6、(1 < i< n)(C) 刪除第i個結點(1 w i w 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)網狀A3

7、a1 3(D ) 7.線性表假設采用鏈式存儲結構時，要求內存中可用存儲單兀的地址(A )必須是連續的(B)局部地址必須是連續的4P0a2C 一定是不連續的D連續或不連續都可以B 8. 線性表L在情況下適用于使用鏈式結構實現。(C)L中含有大量的結點(C)9.單鏈表的存儲密度(A )大于1 ;( B)等于1;(B)10.設a1、a2、a3為3個結點，PoA 循環鏈表B單鏈表A需經常修改L中的結點值B需不斷對L進行刪除插入DL中結點結構復雜C小于1； D不能確定整數Po, 3, 4代表地址，那么如下的鏈式存儲結構稱為C雙向循環鏈表D雙向鏈表四、簡答題1?試比擬順序存儲結構和鏈式存儲結構的優缺點。在

8、什么情況下用順序表比鏈表好?答： 順序存儲時，相鄰數據元素的存放地址也相鄰邏輯與物理統一；要求內存中可用存儲單元的地址必須是連續的。優點：存儲密度大=1?,存儲空間利用率高。缺點：插入或刪除元素時不方便。鏈式存儲時，相鄰數據元素可隨意存放，但所占存儲空間分兩局部，一局部存放結點值，另一局部存放表示結點間關系的指針優點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度小<1,存儲空間利用率低。順序表適宜于做查找這樣的靜態操作；鏈表宜于做插入、刪除這樣的動態操作。假設線性表的長度變化不大，且其主要操作是查找，那么采用順序表；假設線性表的長度變化較大，且其主要操作是插入、刪除操作，那么采用鏈表

9、。2描述以下三個概念的區別：頭指針、頭結點、首元結點第一個元素結點。在單鏈表中設置頭結點的作用是什么？答：首元結點是指鏈表中存儲線性表中第一個數據元素ai的結點。為了操作方便，通常在鏈表的首元結點之前附設一個結點，稱為頭結點，該結點的數據域中不存儲線性表的數據元素，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結點進行統一處理。頭指針是指向鏈表中第一個結點或為頭結點或為首元結點的指針。假設鏈表中附設頭結點，那么不管線性表是否為空表，頭指針均不為空。否那么表示空表的鏈表的頭指針為空。這三個概念對單鏈表、雙向鏈表和循環鏈表均適用。是否設置頭結點，是不同的存儲結構表示同一邏輯結構的問題。head頭結點頭指針首datali nk元占八、簡而言之，頭指針是指向鏈表中第一個結點或為頭結點或為首元結點的指針;頭結點是在鏈表的首元結點之前附設的一個結點;數