數(shù)據(jù)結(jié)構(gòu)（線性表）習(xí)題與答案

一、單選題

1、線性表是具有n個(gè)的有限序列。

A.數(shù)據(jù)項(xiàng)

B.胡

C.數(shù)據(jù)元素

D.表元素

正確答案：C

2、線性表是。

A.一個(gè)無(wú)限序列，可以為空

B.一個(gè)有限序列不可以為空

C.一個(gè)無(wú)限序列，不可以為空

D.一個(gè)有限序列，可以為空

正確答案：D

3、關(guān)于線性表的正確說(shuō)法是。

A.每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼元素

B.除第一個(gè)元素和最后一個(gè)元素外，其余元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼元素

C.表中元素的排序順序必須是由小到大或由大到小

D.線性表中至少有一個(gè)元素

正確答案：B

4、線性表采用鏈表存儲(chǔ)時(shí),其存放各個(gè)元素的單元地址是。

A.連續(xù)與否均可以

B.部分地址必須是連續(xù)的

C.一定是不連續(xù)的

D.必須是連續(xù)的

正確答案：A

5、鏈表不具備的特點(diǎn)是o

A.插入刪除不需要移動(dòng)元素

B.所需空間與其長(zhǎng)度成正比

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

D.可隨機(jī)訪問(wèn)任一節(jié)點(diǎn)

正確答案：D

6、線性表的靜態(tài)鏈表存儲(chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比，優(yōu)點(diǎn)是<,

A.所有的操作算法實(shí)現(xiàn)簡(jiǎn)單

B.便于利用零散的存儲(chǔ)器空間

C.便于隨機(jī)存取

D.便于插入和刪除

正確答案：D

7、線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)相比，優(yōu)點(diǎn)是。

A.便于隨機(jī)存取

B.便于插入和刪除

C.所有的操作算法實(shí)現(xiàn)簡(jiǎn)單

D.節(jié)省存儲(chǔ)空間

正確答案：A

8、設(shè)線性表有n個(gè)元素，以下操作中________在J順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率

A.交換第1個(gè)元素第2個(gè)元素的值

B.輸出與給定值x相等的元素在線性表中的符號(hào)

C.輸入第i(l<=i<=n)個(gè)元素值

D.順序輸出這n個(gè)元素的值

正確答案：C

9、對(duì)于一個(gè)線性表，既要求能夠較快地進(jìn)行插入和刪除操作，又要求存儲(chǔ)結(jié)構(gòu)能夠反

映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)采用存儲(chǔ)結(jié)構(gòu)。

A.順序

B.鏈?zhǔn)?/p>

C.散列

D.索引

正確答案：B

10、設(shè)線性表中有n個(gè)元素，以下操作在單鏈表上實(shí)現(xiàn)要比在頁(yè)序表上實(shí)

現(xiàn)效率高。

A.交換第i個(gè)元素和第n-i+1個(gè)元素的值

B.在第n個(gè)元素的后面插入一個(gè)新元素

C.順序輸出前k個(gè)元素

D.刪除指定位置元素的后一個(gè)元素

正確答案：D

11、以下屬于順序表的優(yōu)點(diǎn)是

A.插入元素方便

B.刪除元素方便

C.以上都不對(duì)

D.存儲(chǔ)密度大

正確答案：D

12、要求線性表采用靜態(tài)空間分配方式，且插入和刪除操作時(shí)不需要移動(dòng)元素，采用

的存儲(chǔ)結(jié)構(gòu)是。

A.靜態(tài)鏈表

B.單鏈表

C.雙鏈表

D.順序表

正確答案：A

13、如果最常用的操作時(shí)取第i個(gè)元素及前驅(qū)元素，則采用存儲(chǔ)方式最節(jié)省

時(shí)間。

A.單鏈表

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

C.順序表

D.雙鏈表

正確答案：C

14、與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是。

A.插入、刪除操作更簡(jiǎn)單

B,可以省略表頭指針或表尾指針

C.可以進(jìn)行隨機(jī)訪問(wèn)

D.訪問(wèn)前后相鄰節(jié)點(diǎn)更方便

正確答案：D

15、在長(zhǎng)度為n的順序表中插入一個(gè)元素的時(shí)間復(fù)雜度為o

A.0(n2)

B.O(l)

C.O(n)

D.O(log2n)

正確答案：C

16、在長(zhǎng)度為n的順序表中刪除一個(gè)元素的時(shí)間復(fù)雜度為.

A.O(log2n)

B.0(1)

C.O(n)

D.O(n2)

正確答案：C

17、在兩個(gè)各有n個(gè)元素的遞增有序順序表歸并成一個(gè)有序順序表，其最少的比較次

數(shù)為?

A.2n

B.2n-1

C.n

D.n-1

正確答案：C

18、將兩個(gè)長(zhǎng)度為n、m的遞增有序表歸并成一個(gè)有序順序表，其最少的比較次數(shù)是

o(MIN表示取最小值)

A.n

B.m

C.不確定

D.MIN(m,n)

正確答案：D

19、在帶頭節(jié)點(diǎn)的單鏈表L為空的判定條件是。

A.L==NULL

B.L->NEXT==NULL

C.L!=NULL

D.L->NEXT==L

正確答案：B

20、對(duì)于一個(gè)具有n個(gè)元素的線性表，建立其單鏈表的時(shí)間復(fù)雜度為

A.0(n)

B.0(n2)

C.O(l)

D.O(log2n)

正確答案：A

21、在單鏈表中查找指定值的節(jié)點(diǎn)的時(shí)間復(fù)雜度是。

A.O(n2)

B.O(n)

C.O(log2n)

D.O(l)

正確答案：B

22、以下關(guān)于單鏈表的敘述中，不正確的是?

A.邏輯上相鄰的元素物理上不必相鄰

B.可以通過(guò)頭節(jié)點(diǎn)直接計(jì)算第i個(gè)節(jié)點(diǎn)的存儲(chǔ)地址

C.插入、刪除運(yùn)算操作簡(jiǎn)單，不必移動(dòng)節(jié)點(diǎn)

D.節(jié)點(diǎn)除自身信息外還包括指針域，因此存儲(chǔ)密度小于順序存儲(chǔ)結(jié)構(gòu)

正確答案：B

23、在單鏈表中，增加一個(gè)頭節(jié)點(diǎn)的目的是為了。

A.說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

B.使單鏈表至少有一個(gè)節(jié)點(diǎn)

C.方便運(yùn)算的實(shí)現(xiàn)

D.標(biāo)識(shí)鏈表中重要節(jié)點(diǎn)的位置

正確答案：C

24、在一個(gè)具有n個(gè)節(jié)點(diǎn)的有序單鏈表中插入一個(gè)新節(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜

度是0

A.0(n)

B.O(n2)

C.O(nlog2n)

D.O(l)

正確答案：A

25、將長(zhǎng)度為m的單鏈表鏈接在長(zhǎng)度為n的單鏈表之后的算法時(shí)間復(fù)雜度為。

A.O(l)

B.O(m)

C.O(n)

D.O(m+n)

正確答案：C

26、已知一個(gè)長(zhǎng)度為n的單鏈表中所有節(jié)點(diǎn)是遞增有序的，以下敘述中正確的是

_______O

A插入一個(gè)節(jié)點(diǎn)使之有序的算法的時(shí)間復(fù)雜度為。(1)

B.找最小值節(jié)點(diǎn)的算法的時(shí)間復(fù)雜度為0(1)

C.刪除最大值節(jié)點(diǎn)使之有序的算法的時(shí)間復(fù)雜度為0(1)

D.以上都不對(duì)

正確答案：B

27、在一個(gè)長(zhǎng)度為n(n>l)的帶頭節(jié)點(diǎn)的單鏈表上，另設(shè)有尾指針r(指向尾節(jié)點(diǎn))，

執(zhí)行_______操作與鏈表的長(zhǎng)度有關(guān)。

A.在單鏈表最后一個(gè)元素后插入一個(gè)新節(jié)點(diǎn)

B.刪除單鏈表中的第一個(gè)元素

C.在單鏈表中第一個(gè)元素前插入一個(gè)新節(jié)點(diǎn)

D.刪除單鏈表的尾節(jié)點(diǎn)

正確答案：D

28、在一個(gè)雙鏈表中，在*p節(jié)點(diǎn)之后插入節(jié)點(diǎn)*q的操作是o

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

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

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

D.q->prior=p;p->next=q;p->next->prior=q;q->next=p->next;

正確答案：A

29、在一個(gè)雙鏈表中，在*p節(jié)點(diǎn)之前插入節(jié)點(diǎn)*q的操作是?

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

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

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

D.q->prior=p->prior;p->prior->next=q;q->next=p;p->prior=q->next;

正確答案：C

30、在一個(gè)雙鏈表中，刪除*p節(jié)點(diǎn)的操作是.

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

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

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

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

正確答案：D

31、在一個(gè)雙鏈表中，刪除*p節(jié)點(diǎn)之后的一個(gè)節(jié)點(diǎn)，其時(shí)間復(fù)雜度為。

A.O(nlog2n)

B.O(n2)

C.O(l)

D.O(n)

正確答案：C

32、非空的循環(huán)單鏈表L的尾節(jié)點(diǎn)(由p所指向)滿足.

A.p->next==NULL

B.p==NULL

C.p->next==L

D.p==L

正確答案：C

33、帶表頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是

A.L->next==L

B.L==NULL

C.L->prior==NULL

D.L->next->prior==NULL

正確答案：A

34、某線性表最常用的操作是在尾元素之后插入一個(gè)元素和刪除尾元素,則采用

存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A.單鏈表

B.雙鏈表

J循環(huán)雙鏈表

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

正確答案：C

35、如果對(duì)含有n(n>l)個(gè)元素的線性表的運(yùn)算只有4種，即刪除第一個(gè)元素、刪除

尾元素、在第一個(gè)元素前面插入新元素、在尾元素的后面插入新元素，則最好使用

___________________O

A.只有尾節(jié)點(diǎn)指針沒(méi)有頭節(jié)點(diǎn)的非循環(huán)雙鏈表

B.既有表頭指針也有表尾指針的循環(huán)單鏈表

C.只有尾節(jié)點(diǎn)指針沒(méi)有頭節(jié)點(diǎn)的循環(huán)單鏈表

D.只有開始數(shù)據(jù)節(jié)點(diǎn)指針沒(méi)有尾節(jié)點(diǎn)指針的循環(huán)雙鏈表

正確答案：D

36、在某線性表最常用的操作是在尾元素之后插入一個(gè)元素和刪除第一個(gè)元素。故采

用存儲(chǔ)方式最節(jié)省時(shí)間。

A.單鏈表

B.雙鏈表

C.僅有尾指針的循環(huán)單鏈表

D.僅有頭節(jié)點(diǎn)指針的循環(huán)單鏈表

正確答案：C

37、兩個(gè)表長(zhǎng)都為n、不帶表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)類型都相同，頭指針?lè)謩e為hl與

h2,且前者是循環(huán)鏈表,后者是非循環(huán)鏈表，則。

A.hl和h2是不同類型的變量

B彳盾環(huán)鏈表要比非循環(huán)鏈表占用更多的內(nèi)存空間

C.對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除尾節(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是0(n)

D.對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除首節(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是0(1)

正確答案：C

38、在長(zhǎng)度為n的上，刪除第一個(gè)元素，其算法的時(shí)間復(fù)雜度為0(n)。

A.只有表尾指針的帶表頭節(jié)點(diǎn)的循環(huán)單鏈表

B,只有表頭指針的不帶表頭節(jié)點(diǎn)的循環(huán)單鏈表

C.只有表頭指針的帶表頭節(jié)點(diǎn)的循環(huán)單鏈表

D.只有表尾指針的不帶表頭節(jié)點(diǎn)的循環(huán)單鏈表

正確答案：B

39、下面關(guān)于線性表的敘述錯(cuò)誤的是。

A.線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)

B.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間

C.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間

D.線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)

正確答案：A

40、對(duì)于雙鏈表，在兩個(gè)節(jié)點(diǎn)之間插入一個(gè)新節(jié)點(diǎn)是,需要修改個(gè)指針域。

A.3

B.1

C.4

D.2

正確答案：C

41、在單鏈表中，要?jiǎng)h除某一指定的節(jié)點(diǎn)，必須找到該節(jié)點(diǎn)的節(jié)點(diǎn)。

A.前驅(qū)

B.頭節(jié)點(diǎn)

C.后繼

D.尾節(jié)點(diǎn)

正確答案：A

42、求一