數(shù)據(jù)結(jié)構(gòu)試題精選（2）-選擇題_跨考網(wǎng)

11. 線性表的表元存儲方式有(（1）)和鏈接兩種。試指出下列各表中使用的是何種存儲方式：表1是(（2）)存儲方式；表2是(（3）)存儲方式；表3是(（4）)存儲方式

12.(1) 靜態(tài)鏈表既有順序存儲的優(yōu)點(diǎn)，又有動態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i個元素的時(shí)間與i無關(guān)。

?? (2) 靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時(shí)就確定了，以后不能增加。

?? (3) 靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。

以上錯誤的是（??? ）【南京理工大學(xué) 2000 一、3（1.5分）】

?A．（1），（2）????? B．（1）?????? C．（1），（2）,(3)????? D.（2）

13. 若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時(shí)間復(fù)雜度為（??? ）(1<=i<=n+1)。【北京航空航天大學(xué) 1999 一、1（2分）】

A. O(0)????? B. O(1)???????? C. O(n)????????? D. O(n2)

14. 對于順序存儲的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（??? ）。

A．O(n)? O(n)????? B. O(n)? O(1)?????? C. O(1)? O(n)??????? D. O(1) O(1)

【青島大學(xué) 2000 五、1（2分）】

15．線性表（ a1,a2,…,an）以鏈接方式存儲時(shí)，訪問第i位置元素的時(shí)間復(fù)雜性為（??? ）

A．O（i）????? B．O（1）????? C．O（n）?????? D．O（i-1）【中山大學(xué) 1999 一、2】

16．非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p↑滿足（??? ）。【武漢大學(xué) 2000 二、10】

A．p↑.link=head?????? B．p↑.link=NIL???????? C．p=NIL???? D．p= head

17．循環(huán)鏈表H的尾結(jié)點(diǎn)P的特點(diǎn)是（??? ）?！局猩酱髮W(xué) 1998 二、2（2分）】

??? A．P^.NEXT:=H???????? B．P^.NEXT:= H^.NEXT??????? C．P:=H????? D．P:=H^.NEXT

18．在一個以 h 為頭的單循環(huán)鏈中，p 指針指向鏈尾的條件是（）【南京理工大學(xué)1998 一、15（2分）】

?A. p＾.next=h??? B. p＾.next=NIL? C. p＾.next.＾next=h?? D. p＾.data=-1

19．完成在雙循環(huán)鏈表結(jié)點(diǎn)p之后插入s的操作是（??? ）；【北方交通大學(xué) 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．在雙向循環(huán)鏈表中,在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個指針q所指向的新結(jié)點(diǎn),其修改指針的操作是(??? )。【北京郵電大學(xué) 1998 二、2（2分）】

注:雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(llink,data,rlink)。 供選擇的答案：

A． p↑.llink：=q； q↑.rlink：=p；???????? p↑.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．在非空雙向循環(huán)鏈表中q所指的結(jié)點(diǎn)前插入一個由p所指的鏈結(jié)點(diǎn)的過程依次為:

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