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.