第2章線性表
一選擇題
1．下述哪一條是順序儲存結構的優點？（ ）【北方交通大學 2001 一、4（2分）】
a．儲存密度大 b．插入運算方便 c．刪除運算方便 d．可方便地用於各種邏輯結構的儲存表示
2．下面關於線性表的敘述中，錯誤的是哪乙個？（ ）【北方交通大學 2001 一、14（2分）】
a．線性表採用順序儲存，必須占用一片連續的儲存單元。
b．線性表採用順序儲存，便於進行插入和刪除操作。
c．線性表採用鏈結儲存，不必占用一片連續的儲存單元。
d．線性表採用鏈結儲存，便於插入和刪除操作。
3．線性表是具有n個（ ）的有限序列（n>0）。 【清華大學 1998 一、4（2分）】
a．表元素 b．字元 c．資料元素 d．資料項 e．資訊項
4．若某線性表最常用的操作是訪問任一指定序號的元素和在最後進行插入和刪除運算，則利用（ ）儲存方式最節省時間。【哈爾濱工業大學 2001 二、1（2分）】
a．順序表 b．雙鏈表 c．帶頭結點的雙迴圈鍊錶 d．單迴圈鍊錶
5．某線性表中最常用的操作是在最後乙個元素之後插入乙個元素和刪除第乙個元素，則採用（ ）儲存方式最節省運算時間。【南開大學 2000 一、3】
a．單鏈表 b．僅有頭指標的單迴圈鍊錶 c．雙鏈表 d．僅有尾指標的單迴圈鍊錶
6．設乙個鍊錶最常用的操作是在末尾插入結點和刪除尾結點，則選用( )最節省時間。
a. 單鏈表 b.單迴圈鍊錶 c. 帶尾指標的單迴圈鍊錶 d.帶頭結點的雙迴圈鍊錶
【合肥工業大學 2000 一、1（2分）】
7．若某錶最常用的操作是在最後乙個結點之後插入乙個結點或刪除最後乙個結點。則採用（ ）儲存方式最節省運算時間。【北京理工大學 2000 一、1（2分）】
a．單鏈表 b．雙鏈表 c．單迴圈鍊錶 d．帶頭結點的雙迴圈鍊錶
8. 靜態鍊錶中指標表示的是（ ）. 【北京理工大學 2001 六、2（2分）】
a． 記憶體位址 b．陣列下標 c．下一元素位址 d．左、右孩子位址
9. 鍊錶不具有的特點是（ ） 【福州大學 1998 一、8 (2分)】
a．插入、刪除不需要移動元素 b．可隨機訪問任一元素
c．不必事先估計儲存空間 d．所需空間與線性長度成正比
10. 下面的敘述不正確的是（ ）【南京理工大學 1996 一、10（2分）】
a．線性表在鏈式儲存時，查詢第i個元素的時間同i的值成正比
b. 線性表在鏈式儲存時，查詢第i個元素的時間同i的值無關
c. 線性表在順序儲存時，查詢第i個元素的時間同i 的值成正比
d. 線性表在順序儲存時，查詢第i個元素的時間同i的值無關
11. 線性表的表元儲存方式有(（1）)和鏈結兩種。試指出下列各表中使用的是何種儲存方式：
表1是(（2）)儲存方式；表2是(（3）)儲存方式；表3是(（4）)儲存方式；表4是(（5）)儲存方式。表左的s指向起始表元
表1s→
表2s→表3s
表4s→
供選擇的答案：
a.連續 b.單向鏈結 c.雙向鏈結 d.不連線 e.迴圈鏈結
f.樹狀 g.網狀 h.隨機 i.順序 j.順序迴圈
【上海海運學院 1995 二、1（5分）】
12.(1) 靜態鍊錶既有順序儲存的優點，又有動態鍊錶的優點。所以，它訪問表中第i個元素的時間與i無關。
(2) 靜態鍊錶中能容納的元素個數的最大數在表定義時就確定了，以後不能增加。
(3) 靜態鍊錶與動態鍊錶在元素的插入、刪除上類似，不需做元素的移動。
以上錯誤的是（ ）【南京理工大學 2000 一、3（1.5分）】
a．（1），（2） b．（1） c．（1），（2）,(3) d.（2）
13. 若長度為n的線性表採用順序儲存結構，在其第i個位置插入乙個新元素的演算法的時間複雜度為（ ）(1<=i<=n+1)。【北京航空航天大學 1999 一、1（2分）】
a. o(0) b. o(1c. o(nd. o(n2)
14. 對於順序儲存的線性表，訪問結點和增加、刪除結點的時間複雜度為（ ）。
a．o(n) o(n) b. o(n) o(1) c. o(1) o(n) d. o(1) o(1)
【青島大學 2000 五、1（2分）】
15．線性表（ a1,a2,…,an）以鏈結方式儲存時，訪問第i位置元素的時間複雜性為（ ）
a．o（i） b．o（1） c．o（n） d．o（i-1）【中山大學 1999 一、2】
16．非空的迴圈單鏈表head的尾結點p↑滿足（ ）。【武漢大學 2000 二、10】
a．p↑.link=head b．p↑.link=nil c．p=nil d．p= head
17．迴圈鍊錶h的尾結點p的特點是（ ）。【中山大學 1998 二、2（2分）】
a．p^.next:=h b．p^.next:= h^.next c．p:=h d．p:=h^.next
18．在乙個以 h 為頭的單迴圈鏈中，p 指標指向鏈尾的條件是（）【南京理工大學1998 一、15（2分）】
a. p＾.next=h b. p＾.next=nil c. p＾.next.＾next=h d. p＾.data=-1
19．完成在雙迴圈鍊錶結點p之後插入s的操作是（ ）；【北方交通大學 1999 一、4（3分）】
a． p^.next:=s ; s^.priou:=p; p^.next^.priou:=s ; s^.next:=p^.next;
b． p^.next^.priou:=s; p^.next:=s; s^.priou:=p; s^.next:=p^.next;
c． s^.priou:=p; s^.next:=p^.next; p^.next:=s; p^.next^.priou:=s ;
d． s^.priou:=p; s^.next:=p^.next; p^.next^.priou:=s ; p^.next:=s;
20．在雙向迴圈鍊錶中,在p指標所指向的結點前插入乙個指標q所指向的新結點,其修改指標的操作是( )。【北京郵電大學 1998 二、2（2分）】
注:雙向鍊錶的結點結構為(llink,data,rlink)。 供選擇的答案：
a． p↑.llink：=q； q↑.rlink：=pp↑.llink↑.rlink：=q； q↑.llink：=q；
b． p↑.llink：=q； p↑.
llink↑.rlink：=q ； q↑.
rlink：= p； q↑.llink:
=p↑.llink；
c． q↑.rlink：=p； q↑.llink：=p↑.llink； p↑.llink↑.rlink：=q; p↑.llink：=q;
d． q↑.llink:=p↑.llink；q↑.rlink:=p； p↑.llink：=q；p↑.llink：=q；（編者按：原題如此）
21．在非空雙向迴圈鍊錶中q所指的結點前插入乙個由p所指的鏈結點的過程依次為:
rlink(p) ← q; llink(p) ← llink(q); llink(q) ← p; （ ）
a．rlink(q) ← p b．rlink(llink(q)) ← p c．rlink(llink(p)) ← p d．rlink(rlink(p)) ← p
【北京航空航天大學 2000 一、1（2分）】
22． 雙向鍊錶中有兩個指標域，llink和rlink，分別指回前驅及後繼，設p指向鍊錶中的乙個結點，q指向一待插入結點，現要求在p前插入q，則正確的插入為（ ）【南京理工大學1996 一、1（2分）】
a. p＾.llink:
=q; q＾.rlink:=p; p＾.
llink＾.rlink:=q; q^.
llink:=p^.llink;
《資料結構》第二章線性表習題
資料結構 一 單項選擇題 1.線性表是 a 乙個有限序列，可以為空 b 乙個有限序列，不可以為空 c 乙個無限序列，可以為空 d 乙個無限序列，不可以為空 2.在乙個長度為n的順序表中刪除第i個元素 0 i n 時，需向前移動個元素。a n i b n i l c n i 1 d i 3.線性表採用...
資料結構習題第二章線性表答案
第2章線性表 一 選擇題 二 判斷題 部分答案解釋如下。1 頭結點並不 僅起 標識作用，並且使操作統一。另外，頭結點資料域可寫入鍊錶長度，或作監視哨。4 兩種儲存結構各有優缺點，應根據實際情況選用，不能籠統說哪乙個好。7 集合中元素無邏輯關係。9 非空線性表第乙個元素無前驅，最後乙個元素無後繼。13...
資料結構及應用演算法教程習題第二章線性表
10.若長度為n的線性表採用順序儲存結構，在其第i個位置插入乙個新元素的演算法的時間複雜度為 1 i n 1 a.o 0 b.o 1c.o nd.o n2 11.對於順序儲存的線性表，訪問結點和增加 刪除結點的時間複雜度為 c a o n o n b.o n o 1 c.o 1 o n d.o 1 ...