课程课件作业空chapter2

1复习题1.

在一个长度为n的顺序表中向第i个元素(1≤i≤n+1)之前插入一个新元素时,需要向后移动

个元素。

A.n-i

B.n-i+1

C.n-i-1

D.i2.链表不具有的特点是____。

A.可随机访问任一元素

B.插入元素不需要移动元素

C.不必事先估计存储空间

D.所需空间与线性表的长度成正比2复习题3.

在线性表的下列存储结构中,读取指定序号的元素花费时间最少的是

。

A.单链表

B.双链表

C.循环链表

D.顺序表4.若线性表中最常用的运算是存取第i个元素及其前驱的值,则采用______存储方式节省时间。

A.单链表

B.双链表

C.循环单链表

D.顺序表3复习题5.

对于用一维数组d[1..n]顺序存储的线性表，其算法时间复杂度为O(1)的操作是

。

A.将n个元素从小到大排序

B.从线性表中删除第i个元素(1≤i≤n)

C.查找第i个元素(1≤i≤n)

D.向线性表的第i个元素之后插入一个元素(0≤i≤n)4复习题6.

在单链表中，若*p结点不是终端结点，在其后插入*s结点的操作是

。

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

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

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

D.p->next=s;s->next=p;7.在一个具有n个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为______。

A.O(log2n)

B.O(1)

C.O(n2)

D.O(n)

5复习题8.

在双向链表中的*p结点之后插入一个结点*s的操作是

。

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

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

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

D.p->next->prior=s;s->next=p->next;s->prior=p;p->next=s;6复习题9.

在双向链表中删除*p结点之后的一个结点的操作是

。

A.p->next=p->next->next;p->next->next->prior=p;

B.p->next->prior=p;p->next=p->next->next;C.p->next=p->next->next;p->next->prior=p;D.p->next->next=p->next;p->next->prior=p;7复习题10.

在带头结点*head的循环链表中，至少有一个结点的条件是

，此时尾结点*p应该满足的条件是

。

A.head->next!=NULL;

B.head->next!=head;C.p==NULL;D.p->next==head;8复习题11.

对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度是

,在data值为x的结点后插入一个新结点的时间复杂度为

。

12.

在有n个元素的顺序表中任意位置插入一个元素所需移动元素的平均次数为

,删除任意一个元素所需移动元素的平均次数为

。

9复习题1)

与顺序表相比，在链表中顺序访问所有结点，其算法的效率比较低。

2)

从长度为n的线性表中删除任何一个元素，其时间复杂度均为O(n)。

3)

凡是为空的单链表都是不含任何结点的。

4)

如果单链表带有头结点，则插入操作永远不会改变头结点指针的值。

13.

判断以下说法是否正确。()()()()10复习题5)

在循环单链表中，任何一个结点的指针域都不可能为空。

6)

对于循环单链表来说，从表中任一结点出发都能扫描整个链表。

7)线性表的顺序存储结构优于链式存储结构。13.

判断以下说法是否正确。()()()11复习题14.

在线性表的如下链式结构中，若未知链表头结点的指针，仅已知p指针指向的结点，能否从中删除该结点？为什么？

A.单链表

B.双向链表

C.循环链表12复习题15.