數(shù)據(jù)結(jié)構(gòu)期末試題匯編

一、選擇題。

1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為。［單選題］*

A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C,線性結(jié)構(gòu)和非線性結(jié)構(gòu)（正確答案）

D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

2.數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示是指。［單選題］*

A.數(shù)據(jù)的存儲結(jié)構(gòu)（正確答案）

B.數(shù)據(jù)結(jié)構(gòu)

C.數(shù)據(jù)的邏輯結(jié)構(gòu)

D.數(shù)據(jù)元素之間的關(guān)系

3.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的結(jié)構(gòu)。［單選題］*

A.邏輯（正確答案）

B.存儲

C.邏輯和存儲

D.物理

4.在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲。［單選題］

A.數(shù)據(jù)的處理方法

B.數(shù)據(jù)元素的類型

C.數(shù)據(jù)元素之間的關(guān)系

D.數(shù)據(jù)的存儲方法

5.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮。［單選題］*

A.各結(jié)點(diǎn)的值如何

B.結(jié)點(diǎn)個數(shù)的多少

C.對數(shù)據(jù)有哪些運(yùn)算

D.所用的編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。

6.以下說法正確的是。［單選題］*

A.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位

B.數(shù)據(jù)元素是數(shù)據(jù)的最小單位

C.數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合

D.一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

7.算法分析的目的是，算法分析的兩個主要方面是。*

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性

B.研究算法中的輸入和輸出的關(guān)系

C.分析算法的效率以求改進(jìn)

D.分析算法的易讀性和文檔性

E.空間復(fù)雜度和時間復(fù)雜度（正確答案）

F.正確性和簡明性

G.可讀性和文檔性

H.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

11.在以下的敘述中，正確的是。［單選題］*

A.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)

B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表

c.棧的操作方式是先進(jìn)先出

D.隊(duì)列的操作方式是先進(jìn)后出

12.通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著。［單

選題］*

A.數(shù)據(jù)元素具有同一特點(diǎn)

B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致

（正確答案）

C.每個數(shù)據(jù)元素都一樣

D.數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相等

13.鏈表不具備的特點(diǎn)是。［單選題］*

A.可隨機(jī)訪問任一結(jié)點(diǎn),答案）

B.插入刪除不需要移動元素

C.不必事先估計存儲空間

D.所需空間與其長度成正比

14.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是。［單選題］*

A.head==NULL；正碓答案）

Bhead->next==NULL

C.head->next==head

Dhead!=NULL

15.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是。［單選題］*

A.head==NULL

Bhead->next==NULL

C.head->next==head

Dhead!=NULL

16.若某表最常用的操作是在最后一個結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)或刪除最后一個結(jié)

點(diǎn)，則采用存儲方式最節(jié)省運(yùn)算時間［單選題］*

A.單鏈表

B.給出表頭指針的單循環(huán)鏈表

C.雙鏈表

D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

17.需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是。

［單選題］*

A.單鏈表

B.靜態(tài)鏈表

C.線性鏈表

D.順序存儲結(jié)構(gòu)

18.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足。［單選題］*

A.p->next==NULL

B.p==NULL

C.p->next==head正確答案）

D.p==head

19.在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是。［單選題］*

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

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

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

D.s->next=p；s->prior=p->prior；p->prior->next=s；p->prior=s:］答案）

20.如果最常用的操作是取第i個結(jié)點(diǎn)及其前驅(qū)，則采用存儲方式最節(jié)省時間。

［單選題］*

A.單鏈表

B.雙鏈表

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

D.順序表

21.在一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然保持有序的時間復(fù)

雜度是。［單選題］*

A.O(1)

B.O(n)(正確答案)

C.O(n2)

D.O(nlog2n)

22.在一個長度為n(n>l)的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行操作與鏈表

的長度有關(guān)。［單選題］*

A.刪除單鏈表中的第一個元素

B.刪除單鏈表中的最后一個元素

C.在單鏈表第一個元素前插入一個新元素

D.在單鏈表最后一個元素后插入一個新元素

23.與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是。［單選題］*

A.插入、刪除操作更簡單

B.可以進(jìn)行隨機(jī)訪問

C.可以省略表頭指針或表尾指針

D.順序訪問相鄰結(jié)點(diǎn)更靈活

24.如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插

入新元素，則最好使用。［單選題］*

A.只有表頭指針沒有表尾指針的循環(huán)單鏈表

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

C.非循環(huán)雙鏈表

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

25.在長度為n的順序表的第i個位置上插入一個元素(l<i<n+l),元素的移動

次數(shù)為：。［單選題］*

A.n-i+l(正確答案)

B.n-i

C.i

D.i-1

26.對于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為。

［單選題］*

A.順序表

B.用頭指針表示的循環(huán)單鏈表

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

D.單鏈表

27.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)？。［單選題］*

A插入運(yùn)算方便

B可方便地用于各種邏輯結(jié)構(gòu)的存儲表示

C存儲密度大

D刪除運(yùn)算方便

28.下面關(guān)于線性表的敘述中，錯誤的是哪一個？。［單選題］*

A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元

B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。

C線性表采用鏈?zhǔn)酱鎯Γ槐卣加靡黄B續(xù)的存儲單元

D線性表采用鏈?zhǔn)酱鎯?，便于進(jìn)行插入和刪除操作。

29.線性表是具有n個的有限序列。［單選題］*

A.字符

B.數(shù)據(jù)元素(正確答案)

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

D.表元素

3().在n個結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時間復(fù)雜度是O(1)的操作是。

［單選題］*

A.訪問第i(l<=i<=n)個結(jié)點(diǎn)和求第i個結(jié)點(diǎn)的直接前驅(qū)(1

B.在第i(l<=i<=n)個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)

C.刪除第i(l<=i<=n)個結(jié)點(diǎn)

D,以上都不對

31.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算

法的時間復(fù)雜度為。［單選題］*

A.0(0)

B.0(1)

C.0(n)(正確答案)

D.O(n2)

32.對于順序存儲的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時間復(fù)雜度為。［單

選題］*

A.0(n)0(n)

B.0(n)0(1)

C.0(l)0(n)正確答案)

D.0(1)0(1)

33.線性表(al,a2,…,an)以鏈?zhǔn)椒绞酱鎯?，訪問第i位置元素的時間復(fù)雜度

為。［單選題］*

A.0(0)

B.0(1)

C.0(n)(正確答案)

D.0(n2)

34.單鏈表中，增加一個頭結(jié)點(diǎn)的目的是為了。［單選題］*

A.使單鏈表至少有一個結(jié)點(diǎn)

B.標(biāo)識表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置

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

D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?/p>

35.在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是。［單選題］

*

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

B.s->next=p->next；p->next=s;正確答案)

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

D.p->next=s->next；p->next=s

36.線性表的順序存儲結(jié)構(gòu)是一種。［單選題］*

A.隨機(jī)存取的存儲結(jié)構(gòu)

B.順序存取的存儲結(jié)構(gòu)

c.索引存取的存儲結(jié)構(gòu)

D.Hash存取的存儲結(jié)構(gòu)

37.棧的特點(diǎn)是B,隊(duì)列的特點(diǎn)是A。*

A.先進(jìn)先出E確答案）

B.先進(jìn)后出（正確答案）

38.棧和隊(duì)列的共同點(diǎn)是。［單選題］*

A.都是先進(jìn)后出

B.都是先進(jìn)先出

C.只允許在端點(diǎn)處插入和刪除元素

D.沒有共同點(diǎn)

39.一個棧的進(jìn)棧序列是a,b,c,d,e,則棧的不可能的輸出序列是。［單選題］

*

A.edcba

B.decba

C.dceab（正確答案）

D.abcde

4（）.設(shè)有一個棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、Eo下列是不可能的出

棧序列。［單選題］*

A.A,B,C,D,E

B.B,C,D,E,A

C.E,A,B,C,D（正確答案）

D.E,D,C,B,A

41.以下不是隊(duì)列的基本運(yùn)算？［單選題］*

A.從隊(duì)尾插入一個新元素

B.從隊(duì)列中刪除第i個元素

C.判斷一個隊(duì)列是否為空

D.讀取隊(duì)頭元素的值

42.若已知一個棧的進(jìn)棧序列是1,2,3,,n,其輸出序列為pl,p2,p3,

pn,若pl=n,則pi為。［單選題］*

A.i

B.n-i

C.n-i+1（正確答案）

D.不確定

43.判定一個順序棧st（最多元素為MaxSize）為空的條件是。［單選題］*

A.st->top!=-1

B.st->top==-1（正確答案）

C.st->top!=MaxSize

D.st->top==MaxSize

44.判定一個順序棧st（最多元素為MaxSize）為滿的條件是。［單選題］*

A.st->top!=-1

B.st->top==-1

C.st->top!=MaxSize

D.st->top==MaxSize確答案）

45.一個隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的輸出序列是。［單選題］*

A.4,3,2,1

B.1,2,3,4（正確答案）

c.1,4,3,2

D.3,2,4,1

46.判定一個循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是。［單選題］*

A.qu->rear-qu->front==MaxSize

B.qu->rear-qu->front-l==MaxSize

C.qu->rear==qu->front（正確答罡）

D.qu->rear=qu->front-1

47.在循環(huán)隊(duì)列中，若front與rear分別表示對頭元素和隊(duì)尾元素的位置，則判斷

循環(huán)隊(duì)列空的條件是。［單選題］*

A.front==rear+l

B.rear==front+1

C.front==rearE確答案）

D.front==0

48.向一個棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時，應(yīng)執(zhí)

行操作。［單選題］*

A.h->next=s;

B.s->next=h;

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

D.s->next=h->next;h->next=s;（確答案）

49.輸入序列為ABC,可以變?yōu)镃BA時，經(jīng)過的棧操作為。［單選題］*

A.push,pop,push,pop,push,pop

B.push,push,push,pop,pop,pop彳答案）

C.push,push,pop,pop,push,pop

D.push,pop,push,push,pop,pop

50.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V"m],top"]、top[2]分別代

表第1和第2個棧的棧頂，棧1的底在V[l],棧2的底在V[m],則棧滿的條件

是。[單選題]*

A.|top[2]-top[l]|=0

B.top[l]+l=top⑵（正確答案）

C.top[l]+top[2]=m

D.top[l]=top[2]

51.設(shè)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用數(shù)據(jù)結(jié)構(gòu)最

佳。[單選題]*

A.線性表的順序存儲結(jié)構(gòu)

B.隊(duì)列

C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

D.棧（正確答案）

52.允許對隊(duì)列進(jìn)行的操作有。[單選題]*

A.對隊(duì)列中的元素排序

B.取出最近進(jìn)隊(duì)的元素

C.在隊(duì)頭元素之前插入元素

D.刪除隊(duì)頭元素（正確答案）

53.對于循環(huán)隊(duì)列。[單選題]*

A.無法判斷隊(duì)列是否為空

B.無法判斷隊(duì)列是否為滿

C.隊(duì)列不可能滿

D.以上說法都不對

54.若用一個大小為6的數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0

和3,當(dāng)從隊(duì)列中刪除一個元素，再加入兩個元素后，rear和front的值分別為。

［單選題］*

A.1和5

B.2和4（正確答案）

C.4和2

D.5和1

55.隊(duì)列的“先進(jìn)先出”特性是指。［單選題］*

A.最早插入隊(duì)列中的元素總是最后被刪除

B.當(dāng)同時進(jìn)行插入、刪除操作時，總是插入操作優(yōu)先

C.每當(dāng)有刪除操作時，總是要先做一次插入操作

D.每次從隊(duì)列中刪除的總是最早插入的元素

56.和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是。［單選題］*

A.通常不會出現(xiàn)棧滿的情況（正確答案）

B.通常不會出現(xiàn)?？盏那闆r

C.插入操作更容易實(shí)現(xiàn)

D.刪除操作更容易實(shí)現(xiàn)

57.用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)

點(diǎn)，則在進(jìn)行出隊(duì)操作時。［單選題］*

A.僅修改隊(duì)頭指針

B.僅修改隊(duì)尾指針

C.隊(duì)頭、隊(duì)尾指針都可能要修改

D.隊(duì)頭、隊(duì)尾指針都要修改

58.若串S=，software,,其子串的數(shù)目是。［單選題］*

A.8

B.375確答案）

C.36

D.9

59.串的長度是指。［單選題］*

A.串中所含不同字母的個數(shù)

B.串中所含字符的個數(shù)

C.串中所含不同字符的個數(shù)

D.串中所含非空格字符的個數(shù)

60.串是一種特殊的線性表，其特殊性體現(xiàn)在。［單選題］*

A.可以順序存儲

B.數(shù)據(jù)元素是一個字符

C.可以鏈?zhǔn)酱鎯?/p>

D.數(shù)據(jù)元素可以是多個字符

61.設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱為。［單選題］*

A.連接

B.模式匹配（正確答案）

C.求子串

D.求串長

62.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到

10,從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A［8］［5］的起

始地址為。［單選題］*

A.SA+141

B.SA+144

C.SA+222（正確答案）

D.SA+225

63.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1至U8,歹IJ下標(biāo)j從1至U

10,從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A［5］⑻的起

始地址為。［單選題］*

A.SA+141

B.SA+18（）

C.SA+222（正確答案）

D.SA+225

64.若聲明一個浮點(diǎn)數(shù)數(shù)組如下：froataverage［］=newfloat［30］;

假設(shè)該數(shù)組的內(nèi)存起始位置為200,average［15］的內(nèi)存地址是。［單選題］*

A.214

B.215

C.260（正確答案）

D.256

65.設(shè)二維數(shù)組n］按行存儲在數(shù)組B中，則二維數(shù)組元素人［討］在一

維數(shù)組B中的下標(biāo)為。［單選題］*

A.n*（i-l）+j正確答案）

B.n*（i-l）+j-l

c.

D.j*m+i-l

66.有一個100x90的稀疏矩陣，非0元素有10,設(shè)每個整型數(shù)占2個字節(jié)，則用

三元組表示該矩陣時，所需的字節(jié)數(shù)是。［單選題］*

A.20

B.66正確答案）

C.18000

D.33

67.數(shù)組A［（）…4,-1...-3,5...7］中含有的元素個數(shù)是。［單選題］*

A.55（正確答案）

B.45

C.36

D.16

68.對矩陣進(jìn)行壓縮存儲是為了。［單選題］*

A.方便運(yùn)算

B.方便存儲

C.提高運(yùn)算速度

D.減少存儲空間（正確答案）

69.設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序?yàn)橹鞔鎯Γ琣l,1

為第一個元素，其存儲地址為1,每個元素占1個地址空間，則a8,5的地址

為。［單選題］*

A.13

B.33正確答案）

C.18

D.40

70.稀疏矩陣一般的壓縮存儲方式有兩種，即。［單選題］*

A.二維數(shù)組和三維數(shù)組

B.三元組和散列

C.三元組和十字鏈表

D.散列和十字鏈表

71.樹最適合用來表示。［單選題］*

A.有序數(shù)據(jù)元素

B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)

D.元素之間無聯(lián)系的數(shù)據(jù)

72.深度為5的二叉樹至多有個結(jié)點(diǎn)。［單選題］*

A.16

B.32

C.31（正確答案）

d.10

73.對一個滿二叉樹，m個葉子，n個結(jié)點(diǎn)，深度為h,則。［單選題］*

A.n=h+m

Bh+m=2n

Cm=h-1

Dn=2h-1；正確答案）

74.任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序。

［單選題］*

A.不發(fā)生改變［答至?

B.發(fā)生改變

C.不能確定

D.以上都不對

75.在線索化樹中，每個結(jié)點(diǎn)必須設(shè)置一個標(biāo)志來說明它的左、右鏈指向的是樹結(jié)

構(gòu)信息，還是線索化信息，若（）標(biāo)識樹結(jié)構(gòu)信息，1標(biāo)識線索，對應(yīng)葉結(jié)點(diǎn)的左右

鏈域，應(yīng)標(biāo)識為。［單選題］*

A.00

B.01

C.1（）

D.11（正確答案）

76.在下述論述中，正確的是。

①只有一個結(jié)點(diǎn)的二叉樹的度為（）；②二叉樹的度為2；③二叉樹的左右子樹可任

意交換；

④深度為K的順序二叉樹的結(jié)點(diǎn)個數(shù)小于或等于深度相同的滿二叉樹。

［單選題】*

A.①②③

B.②③④

C.②④

D.①④（正確答案）

77.設(shè)森林F對應(yīng)的二叉樹為B,它有m個結(jié)點(diǎn)，B的根為p,p的右子樹的結(jié)點(diǎn)

個數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)的個數(shù)是。［單選題］*

A.m-n三確答案）

B.m-n-1

C.n+1

D.不能確定

78.若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)

的個數(shù)是。［單選題］*

A.9

B.11（正確答案）

C.15

D.不能確定

79.具有1（）個葉子結(jié)點(diǎn)的二叉樹中有個度為2的結(jié)點(diǎn)。［單選題］*

A.8

B.9（正確答案）

C.10

D.11

80.在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的倍。［單選題］*

A.1/2

B1

C2（正確答案）

D4

81.在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。［單

選題］*

A.1/2

11（正確答既

C2

D4

82.某二叉樹結(jié)點(diǎn)的中序序列為ABCDEFG,后序序列為BDCAFGE,則其左子樹

中結(jié)點(diǎn)數(shù)目為：［單選題］*

A.3

B.2

C.4(Z

D.5

83.已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其

前綴形式為。［單選題］*

A.-A+B*C/DE

B.-A+B*CD/E

C-+*ABC/DE

D.-+A*BC/DEE確答案）

84.已知一個圖，如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到

的一種頂點(diǎn)序列為一D—；按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序

B.a,c,f,e,b,d

C.a,e,b,c,f,d,

D.a,e,d,f,c,b（正確答案）

E.a,b,c,e,d,f

F.a,b,c,e,f,d

G.a,e,b,c,f,d,

H.a,c,f,d,e,b

85.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的o［單選題］

*

A.先序遍歷（正確答案）

B.中序遍歷

C后序遍歷

D.按層遍歷

86.采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的o［單選題］

*

A.先序遍歷

B.中序遍歷

C后序遍歷

D.按層遍歷（正確答案）

87.具有n個結(jié)點(diǎn)的連通圖至少有條邊。［單選題］*

A.n-1（正確答案）

B.n

C.n（n-l）/2

D.2n

88.廣義表（（a）,a）的表頭是C,表尾是C。［單選題］*

A.a

B()

C(a)(正確答案)

D((a))

89.廣義表((a))的表頭是C,表尾是B。*

A.a

B()(正確答案)

C(a)(正確答案)

D((a))

90.順序查找法適合于存儲結(jié)構(gòu)為的線性表。［單選題］*

A散列存儲

B順序存儲或鏈?zhǔn)酱鎯?/p>

C壓縮存儲

D索引存儲

91.對線性表進(jìn)行折半查找時，要求線性表必須。［單選題］*

A以順序方式存儲

B以順序方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有序排列

C以鏈?zhǔn)椒绞酱鎯?/p>

D以鏈?zhǔn)椒绞酱鎯?，且結(jié)點(diǎn)按關(guān)鍵字有序排列

92.采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為。

［單選題］*

AO(n2)

BO(nlog2n)

CO（n）

DO（log2n）（正確答案）

93.有一個有序表為｛1,3,9,12,32,41,45,62,75,77,82,95,100）,

當(dāng)折半查找值為82的結(jié)點(diǎn)時，次比較后查找成功。［單選題］*

A.11

B5

C4（正確答案）

D8

94.二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、

小于其右孩子的值。這種說法。［單選題］*

A正確

B錯誤

95.下面關(guān)于B樹和B+樹的敘述中，不正確的結(jié)論是。［單選題］*

A（正確答案）

B樹和B+樹都能有效的支持順序查找BB樹和B+樹都能有效的支持隨機(jī)查找

CB樹和B+樹都是平衡的多叉樹

DB樹和B+樹都可用于文件索引結(jié)構(gòu)

96.以下說法錯誤的是。［單選題］*

A.散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址

B.散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針」正確答案）

C.負(fù)載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度。

D.散列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處理沖突的方

法。

97.查找效率最高的二叉排序樹是。［單選題］*

A.所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹。

B.所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹。

C.平衡二叉樹。

D.沒有左子樹的二叉排序樹。

98.排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較,

將其放入已排序序列的正確位置上的方法，稱為。［單選題］*

A.希爾排序

Bo冒泡排序

C插入排序

Do選擇排序

99.在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是。

［單選題］*

A.希爾排序

B.冒泡排序

C,直接插入排序

D,直接選擇排序（正確答案）

100.堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列是一個堆。［單選題］*

A.94,31,53,23,16,72

B.94,53,31,72,16,23

C.16,53,23,94,31,72

D.16,31,23,94,53,72

101.堆排序是一種排序。［單選題］*

A.插入

B.選擇

C.交換

D.歸并

102.在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。［單選題］*

A.順序查找

B.折半查找

C.分塊查找

D.插入

103.直接選擇排序的時間復(fù)雜度為。(n為元素個數(shù))［單選題］*

A.O(n)

B.O(log2n)

C.O(nlog2n)

D.O(n2)正確答案)

三、判斷題。

1.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點(diǎn)的值如何。［判斷題］*

對(正確答案)

錯

2.抽象數(shù)據(jù)類型(ADT)包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定

義僅給出一個ADT的邏輯特性，不必考慮如何在計算機(jī)中實(shí)現(xiàn)。［判斷題］*

對

錯

3.抽象數(shù)據(jù)類型與計算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)。［判斷題］*

對

錯

4.順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩＃叟袛囝}］

*

對

錯（正確答案）

5.線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。

［判斷題］*

對

錯（正確答案）

6.對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。［判斷題］*

對

錯

7.順序存儲方式只能用于存儲線性結(jié)構(gòu)。［判斷題］*

對

錯（正確答案）

8.集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。［判斷題］*

對

錯（正確答案）

9.線性表中每個元素都有一個直接前驅(qū)和一個直接后繼。［判斷題］*

對

錯（正確答案）

10.線性表就是順序存儲的表。［判斷題］*

對

錯（正確答案）

11.取線性表的第i個元素的時間同i的大小有關(guān)。［判斷題］*

對

錯（正確答案）

12.循環(huán)鏈表不是線性表。［判斷題］*

對

錯

13.鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表，進(jìn)行插入、刪除操作時，在鏈表中比在順

序表中效率高。［判斷題］*

對（正確答案）

錯

14.雙向鏈表可隨機(jī)訪問任一結(jié)點(diǎn)。［判斷題］*

對

錯（正確答案）

15.在單鏈表中，給定任一結(jié)點(diǎn)的地址p,則可用下述語句將新結(jié)點(diǎn)s插入結(jié)點(diǎn)p

的后面：p->next=s;s->next=p->next;［判斷題］*

對

錯（正確答案）

16.隊(duì)列是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出的

結(jié)構(gòu)。［判斷題］*

對

錯（正確答案）

17.串是一種特殊的線性表，其特殊性體現(xiàn)在可以順序存儲。［判斷題］*

對

錯（正確答案）

18.長度為1的串等價于一個字符型常量。［判斷題］*

對

錯（正確