2012年考研數據結構精選試題（三）

　　一 選擇題

　　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.若某表比較常用的操作是在比較后一個結點之后插入一個結點或刪除比較后一個結點。則采用( )存儲方式比較節省運算時間�！颈本├砉ご髮W 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指向起始表元。

　　表元編號貨號數量表元間聯系

　　1 618 40 2

　　2 205 2 3

　　3 103 15 4

　　4 501 20 5

　　5 781 17 6

　　6 910 24 0

　　表1

　　s→

　　表元編號貨號數量表元間聯系

　　1 618 40 5

　　2 205 2 1

　　3 103 15 4

　　4 501 20 2

　　5 781 17 6

　　6 910 24 3

　　表2

　　s→

　　表元編號貨號數量表元間聯系

　　1 618 40 5

　　2 205 2 1

　　3 103 15 4

　　4 501 20 0

　　5 781 17 6

　　6 910 24 3

　　表3

　　s→

　　表元編號貨號數量表元間聯系

　　1 2

　　1 618 40 5 2

　　2 205 2 1 0

　　3 103 15 4 6

　　4 501 20 0 3

　　5 781 17 6 1

　　6 910 24 3 5

　　表4

　　s→

　　供選擇的答案：

　　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(1) C. O(n) D. 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↑滿足( )�！疚錆h大學 2000 二、10】

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

　　17.循環鏈表H的尾結點P的特點是( )�！局猩酱髮W 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：=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.在非空雙向循環鏈表中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;

　　B. q^.llink:=p^.llink; p^.llink^.rlink:=q; q^.rlink:=p; p^.llink:=q^.rlink;

　　C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p;

　　D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q;

　　23.在雙向鏈表指針p的結點前插入一個指針q的結點操作是( )�！厩鄭u大學 2000 五、2(2分)】

　　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=q;p->Llink=q;p->Llink=q;

　　24.在單鏈表指針為p的結點之后插入指針為s的結點，正確的操作是：( )。

　　A.p->next=s;s->next=p->next; B. s->next=p->next;p->next=s;

　　C.p->next=s;p->next=s->next; D. p->next=s->next;p->next=s;

　　【青島大學 2001 五、3(2分)】

　　25.對于一個頭指針為head的帶頭結點的單鏈表，判定該表為空表的條件是( )

　　A.head==NULL B.head→next==NULL C.head→next==head D.head!=NULL

　　【北京工商大學 2001 一、5(3分)】

　　26. 在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針( )。

　　A. (p^.llink)^.rlink:=p^.rlink (p^.rlink)^.llink:=p^.llink;

　　B. p^.llink:=(p^.llink)^.llink (p^.llink)^.rlink:=p;

　　C. (p^.rlink)^.llink:=p p^.rlink:=(p^.rlink)^.rlink

　　D. p^.rlink:=(p^.llink)^.llink p^.llink:=(p^.rlink)^.rlink;

　　【西安電子科技大學 1998 一、1(2分)】

　　27. 雙向鏈表中有兩個指針域，llink和rlink分別指向前趨及后繼，設p指向鏈表中的一個結點，現要求刪去p所指結點，則正確的刪除是( )(鏈中結點數大于2，p不是第一個結點)

　　A.p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink; dispose(p);

　　B.dispose(p); p^.llink^.rlink:=p^.llink; p^.llink^,rlink:=p^.rlink;

　　C.p^.llink^.rlink:=p^.llink; dispose(p); p^.llink^.rlink:=p^.rlink;

　　D.以上A，B，C都不對。 【南京理工大學 1997 一、1(2分)】