課程課件作業(yè)空chapter2

1復(fù)習(xí)題1.

在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)新元素時(shí),需要向后移動(dòng)

個(gè)元素。

A.n-i

B.n-i+1

C.n-i-1

D.i2.鏈表不具有的特點(diǎn)是____。

A.可隨機(jī)訪問(wèn)任一元素

B.插入元素不需要移動(dòng)元素

C.不必事先估計(jì)存儲(chǔ)空間

D.所需空間與線性表的長(zhǎng)度成正比2復(fù)習(xí)題3.

在線性表的下列存儲(chǔ)結(jié)構(gòu)中,讀取指定序號(hào)的元素花費(fèi)時(shí)間最少的是

。

A.單鏈表

B.雙鏈表

C.循環(huán)鏈表

D.順序表4.若線性表中最常用的運(yùn)算是存取第i個(gè)元素及其前驅(qū)的值,則采用______存儲(chǔ)方式節(jié)省時(shí)間。

A.單鏈表

B.雙鏈表

C.循環(huán)單鏈表

D.順序表3復(fù)習(xí)題5.

對(duì)于用一維數(shù)組d[1..n]順序存儲(chǔ)的線性表，其算法時(shí)間復(fù)雜度為O(1)的操作是

。

A.將n個(gè)元素從小到大排序

B.從線性表中刪除第i個(gè)元素(1≤i≤n)

C.查找第i個(gè)元素(1≤i≤n)

D.向線性表的第i個(gè)元素之后插入一個(gè)元素(0≤i≤n)4復(fù)習(xí)題6.

在單鏈表中，若*p結(jié)點(diǎn)不是終端結(jié)點(diǎn)，在其后插入*s結(jié)點(diǎn)的操作是

。

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.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)使得仍然有序，其算法的時(shí)間復(fù)雜度為_(kāi)_____。

A.O(log2n)

B.O(1)

C.O(n2)

D.O(n)

5復(fù)習(xí)題8.

在雙向鏈表中的*p結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)*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復(fù)習(xí)題9.

在雙向鏈表中刪除*p結(jié)點(diǎn)之后的一個(gè)結(jié)點(diǎn)的操作是

。

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復(fù)習(xí)題10.

在帶頭結(jié)點(diǎn)*head的循環(huán)鏈表中，至少有一個(gè)結(jié)點(diǎn)的條件是

，此時(shí)尾結(jié)點(diǎn)*p應(yīng)該滿足的條件是

。

A.head->next!=NULL;

B.head->next!=head;C.p==NULL;D.p->next==head;8復(fù)習(xí)題11.

對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是

,在data值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為

。

12.

在有n個(gè)元素的順序表中任意位置插入一個(gè)元素所需移動(dòng)元素的平均次數(shù)為

,刪除任意一個(gè)元素所需移動(dòng)元素的平均次數(shù)為

。

9復(fù)習(xí)題1)

與順序表相比，在鏈表中順序訪問(wèn)所有結(jié)點(diǎn)，其算法的效率比較低。

2)

從長(zhǎng)度為n的線性表中刪除任何一個(gè)元素，其時(shí)間復(fù)雜度均為O(n)。

3)

凡是為空的單鏈表都是不含任何結(jié)點(diǎn)的。

4)

如果單鏈表帶有頭結(jié)點(diǎn)，則插入操作永遠(yuǎn)不會(huì)改變頭結(jié)點(diǎn)指針的值。

13.

判斷以下說(shuō)法是否正確。()()()()10復(fù)習(xí)題5)

在循環(huán)單鏈表中，任何一個(gè)結(jié)點(diǎn)的指針域都不可能為空。

6)

對(duì)于循環(huán)單鏈表來(lái)說(shuō)，從表中任一結(jié)點(diǎn)出發(fā)都能掃描整個(gè)鏈表。

7)線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。13.

判斷以下說(shuō)法是否正確。()()()11復(fù)習(xí)題14.

在線性表的如下鏈?zhǔn)浇Y(jié)構(gòu)中，若未知鏈表頭結(jié)點(diǎn)的指針，僅已知p指針指向的結(jié)點(diǎn)，能否從中刪除該結(jié)點(diǎn)？為什么？

A.單鏈表

B.雙向鏈表

C.循環(huán)鏈表12復(fù)習(xí)題15.