数据结构1800题（答案全）(7)

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↑满足（ ）。【武汉大学 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：=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的结点操作是（ ）。【青岛大学 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分）】

二、判断

1. 链表中的头结点仅起到标识的作用。( )【南京航空航天大学 1997 一、1（1分）】

2. 顺序存储结构的主要缺点是不利于插入或删除操作。( )【南京航空航天大学1997 一、2（1分）】

3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )

【北京邮电大学 1998 一、2（2分）】

4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )

【北京邮电大学 2002 一、2（1分）】

5. 对任何数据结构链式存储结构一定优于顺序存储结构。( 【南京航空航天大学) 1997 一、3（1分）】

6．顺序存储方式只能用于存储线性结构。( )

【中科院软件所 1999 六、1-2（2分）】【上海海运学院 1997 一、1（1分）】

7．集合与线性表的区别在于是否按关键字排序。( )【大连海事大学 2001 一、5 ( 1分)】

8. 所谓静态链表就是一直不发生变化的链表。( )【合肥工业大学 2000 二、1（1分）】

9. 线性表的特点是每个元素都有一个前驱和一个后继。( )【合肥工业大学2001 二、1（1分）】

10. 取线性表的第i个元素的时间同i的大小有关. ( 【)南京理工大学 1997 二、9（2分）】

11. 循环链表不是线性表. ( )【南京理工大学 1998 二、1（2分）】

12. 线性表只能用顺序存储结构实现。( )【青岛大学 2001 四、2（1分）】

13. 线性表就是顺序存储的表。( )【青岛大学 2002 一、1（1分）】

14．为了很方便的插入和删除数据，可以使用双向链表存放数据。( )