数据结构习题11级用(3)

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表

6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省

时间。 A. 单链表

B.单循环链表

C. 带尾指针的单循环链表 D.带头结点的双循环链表

7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。 A．单链表 B．双链表

C．单循环链表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ ）.

A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址

6

9. 链表不具有的特点是（ ）

A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（ ）

A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关

11． 双向链表中有两个指针域，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都不对。

12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第

i个元素的时间与i无关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（ ）

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

13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法

的时间复杂度为（ ）(1<=i<=n+1)。

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) 15．线性表（ a1,a2,?,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）

A．O（i） B．O（1） C．O（n） D．O（i-1） 16．非空的循环单链表head的尾结点p↑满足（ ）。

A．p↑.link=head B．p↑.link=NIL C．p=NIL D．p= head 17．循环链表H的尾结点P的特点是（ ）。

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

7