數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)試題

精選試題

數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)試題

編制:

審核:

出版:

《數(shù)據(jù)結(jié)構(gòu)與算法》（C語(yǔ)言版）期末考復(fù)習(xí)題

一、選擇題。

I.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為C.

A.動(dòng)態(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ì)算機(jī)內(nèi)存中的表示是指」—。

A.數(shù)據(jù)的存儲(chǔ)結(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ì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的結(jié)構(gòu)。

A.邏輯B.存儲(chǔ)C.邏輯和存儲(chǔ)D.物理

4.在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)

C。

A.數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類(lèi)型

C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲(chǔ)方法

5.在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮上_。

A.各結(jié)點(diǎn)的值如何B.結(jié)點(diǎn)個(gè)數(shù)的多少

C.對(duì)數(shù)據(jù)有哪些運(yùn)算D.所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方

便。

6.以下說(shuō)法正確的是。

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.算法分析的目的是，算法分析的兩個(gè)主要方面是A

(1)A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸

出的關(guān)系

C,分析算法的效率以求改進(jìn)C.分析算法的易讀性和文

檔性

(2)A.空間復(fù)雜度和時(shí)間復(fù)雜度B.正確性和簡(jiǎn)明性

C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜

性

8.下面程序段的時(shí)間復(fù)雜度是0(2

s=0;

for(I=0;i<n;i++)

for(j=0;j<n;j++)

s+=B[i][j];

sum=s;

9.下面程序段的時(shí)間復(fù)雜度是O(n*m)

for(i=0;i<n;i++)

for(j=0;j<m;j++)

A[i][j]=0;

10.下面程序段的時(shí)間復(fù)雜度是O(log3n)

i=0;

while(i<=n)

i=i*3;

11.在以下的敘述中，正確的是B.

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

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

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

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

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

意味著B(niǎo)。

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

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

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

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

13.鏈表不具備的特點(diǎn)是A。

A.可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.插入刪除不需要移動(dòng)元素

C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與其長(zhǎng)度成正比

14.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是A、

A.head==NULLBhead->next==NULL

C.head->next==headDhead!=NULL

15.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是B.

A.head==NULLBhead->next==NULL

C.head->next==headDhead!=NULL

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

除最后一個(gè)結(jié)點(diǎn)，則采用

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

A.單鏈表B.給出表頭指針的單循環(huán)鏈表C.雙鏈表D.帶

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

17.需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其

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

A.單鏈表B.靜態(tài)鏈表C.線性鏈表D.順序存儲(chǔ)結(jié)構(gòu)

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

A.p->next==NULLB,p==NULL

C.p->next==headD.p==head

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

Do

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個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用D存儲(chǔ)

方式最節(jié)省時(shí)間。

A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表

21.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保

持有序的時(shí)間復(fù)雜度是B_o

A.0(1)B.O(n)C.O(n2)D.O(nlog2n)

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

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

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

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

C.在單鏈表第一個(gè)元素前插入一個(gè)新元素

D.在單鏈表最后一個(gè)元素后插入一個(gè)新元素

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

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

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

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

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

24.如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，在最后一

個(gè)元素的后面插入新元素，則最好使用B°

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

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

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

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

25在長(zhǎng)度為n的順序表的第i個(gè)位置上插入一個(gè)元素l<i<n+l),

元素的移動(dòng)次數(shù)為：Ao

A.n-i+1B,n-iC.iD.i-

1

26.對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存

儲(chǔ)結(jié)構(gòu)為C。

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

表

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

27.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)C.

A插入運(yùn)算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示

C存儲(chǔ)密度大D刪除運(yùn)算方便

28.下面關(guān)于線性表的敘述中,錯(cuò)誤的是哪一個(gè)B.

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

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

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

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

29.線性表是具有n個(gè)B的有限序列。

A.字符B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.表元素

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

的操作是A0

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

(l<i<=n)

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

5刪除第1(1<+<=11)個(gè)結(jié)點(diǎn)

D.以上都不對(duì)

31.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一

個(gè)新元素的算法的時(shí)間復(fù)雜度為

A.0(0)B.0(1)C.0(n)D.0(n2)

32.對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)

雜度為C.

A.O(n)0(n)B.O(n)0(1)C.0(1)0(n)

D.0(1)0(1)

33.線性表(al,a2,...,an)以鏈?zhǔn)椒绞酱鎯?chǔ)，訪問(wèn)第i位置元素

的時(shí)間復(fù)雜度為C.

A.0(0)B.0(1)C.0(n)D.0(n2)

34.單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了工—o

A.使單鏈表至少有一個(gè)結(jié)點(diǎn)B.標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位

置

C.方面運(yùn)算的實(shí)現(xiàn)D.說(shuō)明單鏈表是線性表的

鏈?zhǔn)酱鎯?chǔ)

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

作是B。

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

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

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

p->next=s

36.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種A

A.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B.順序存取的存儲(chǔ)結(jié)構(gòu)

C.索引存取的存儲(chǔ)結(jié)構(gòu)D.Hash存取的存儲(chǔ)結(jié)構(gòu)

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

A.先進(jìn)先出B.先進(jìn)后出

38.棧和隊(duì)列的共同點(diǎn)是—o

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

C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)

.一個(gè)棧的進(jìn)棧序列是則棧的不可能的輸出序

39a,b,c,d,ez

列是C。

A.edcbaB.decbaC.dceabD.abcde

40.設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E。下列C

是不可能的出棧序列。

A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.E,D,C,B,A

41.以下B不是隊(duì)列的基本運(yùn)算

A.從隊(duì)尾插入一個(gè)新元素B.從隊(duì)列中刪除第i個(gè)元素

C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值

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

p2,p3,…，pn,若pl=n，貝[]pi為C。

A.iB.n-iC.n-i+1D.不確定

43判定一個(gè)順序棧st（最多元素為MaxSize）為空的條件是B。

A.st->top!=-1B.st->top==-1

C.st->top!=MaxSizeD.st->top==MaxSize

44判定一個(gè)III頁(yè)序棧s<最多元素為MaxSize為滿的條件是“。

A.st->top!=-1B.st->top==-1

C.st->top!=MaxSizeD.st->top==MaxSize

45.一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4，則隊(duì)列的輸出序列是」o

A.4,3,2,1B.1,2,3,4

C.1,4,3,2D.3,2,4,1

46.判定一個(gè)循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是

C。

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

qu->front-l==MaxSize

C.qu->rear==qu->frontD.qu->rear

=qu->front-1

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

的位置，則判斷循環(huán)隊(duì)列空的條件是C0

A.front==rear+lB.rear==front+lC.front==rear

D.front==0

48.向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)

點(diǎn)時(shí)，應(yīng)執(zhí)行D操作。

A.h->next=s;B.s->next=h;

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

.輸入序列為,可以變?yōu)闀r(shí)，經(jīng)過(guò)的棧操作為

49ABCCBABo

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

push,pop,pop,pop

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

push,push,pop,pop

50.若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V[1m],top[l].

top[2]分別代表第1和第2個(gè)棧的棧頂，棧1的底在V[l],棧2的

底在則棧滿的條件是—

V[m],Bo

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

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

51.設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用」

數(shù)據(jù)結(jié)構(gòu)最佳。

A.線性表的順序存儲(chǔ)結(jié)構(gòu)B.隊(duì)列C.線性表的鏈?zhǔn)酱?/p>

儲(chǔ)結(jié)構(gòu)D.棧

.允許對(duì)隊(duì)列進(jìn)行的操作有

52D0

A.對(duì)隊(duì)列中的元素排序B.取出最近進(jìn)隊(duì)的元素

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

53.對(duì)于循環(huán)隊(duì)列D.

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

C.隊(duì)列不可能滿D.以上說(shuō)法都不對(duì)

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

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

rear和front的值分別為Bo

A.l和5B.2和4C.4和2D,51

55.隊(duì)列的"先進(jìn)先出"特性是指D。

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

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

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

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

56.和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是A.

A.通常不會(huì)出現(xiàn)棧滿的情況B.通常不會(huì)出現(xiàn)?？盏那闆r

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

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

指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作時(shí)C。

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

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

要修改

58.若串S='software',其子串的數(shù)目是B。

A.8B,37C.36D.9

59.串的長(zhǎng)度是指B.

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

C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的

個(gè)數(shù)

60.串是一種特殊的線性表，其特殊性體現(xiàn)在」o

A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符

C.可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符

61.設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為

B。

A.連接B.模式匹配C.求子串D.求串長(zhǎng)

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

下標(biāo)j從1到10,從首地址SA開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按

行存放，元素的起始地址為

A[8][5]Co

A.SA+141B.SA+144C.SA+222D,SA+225

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

下標(biāo)j從1到10,從首地址SA開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按

行存放，元素A[5]⑻的起始地址為C。

A,SA+141B.SA+180C.SA+222D.SA+225

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

假設(shè)該數(shù)組的內(nèi)存起始位置為200,average[15]的內(nèi)存地址是

Co

A.214B,215C.260D.256

65.設(shè)二維數(shù)組A[l...m,l…可按行存儲(chǔ)在數(shù)組B中，則二維數(shù)組

元素A[i,j]在一維數(shù)組B中的下標(biāo)為A。

A.n*(i-l)+jB.n*(i-l)+j-lC.i*(j-l)D,j*m+i-l

66.有一個(gè)100x90的稀疏矩陣，非0元素有10,設(shè)每個(gè)整型數(shù)占

2個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是B。

A.20B.66C.18000D.33

67.數(shù)組A[0...4,-1...-3,5…刀中含有的元素個(gè)數(shù)是

Ao

A.55B.45C.36D.16

68.對(duì)矩陣進(jìn)行壓縮存儲(chǔ)是為了D。

A.方便運(yùn)算B.方便存儲(chǔ)C.提高運(yùn)算速度D.減少存儲(chǔ)

空間

69.設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹?/p>

存儲(chǔ)，ai,1為第一個(gè)元素，其存儲(chǔ)地址為1,每個(gè)元素占1個(gè)地址空

間，則a8,5的地址為B。

A.13B.33C.18D.40

70.稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即/o

A.二維數(shù)組和三維數(shù)組B.三元組和散列

C,三元組和十字鏈表D.散列和十字鏈表

71.樹(shù)最適合用來(lái)表示J。

A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的

數(shù)據(jù)

72.深度為5的二叉樹(shù)至多有C個(gè)結(jié)點(diǎn)。

A.16B.32C.31C.10

73.對(duì)一個(gè)滿二叉樹(shù)，m個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h,則D.

A.n=h+mBh+m=2nCm=h-1Dn=2h-l

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

相對(duì)次序A。

A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以

上都不對(duì)

75.在線索化樹(shù)中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來(lái)說(shuō)明它的左、右

鏈指向的是樹(shù)結(jié)構(gòu)信息，還是線索化信息，若0標(biāo)識(shí)樹(shù)結(jié)構(gòu)信息,

1標(biāo)識(shí)線索，對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)為_(kāi)D

A.00B.01C.10D.11

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

①只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0；②二叉樹(shù)的度為2;③二叉樹(shù)的

左右子樹(shù)可任意交換；

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

樹(shù)。

A.①②③B.②③④C.②④D.①④

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

的右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)是

A。

A.m-nB.m-n-1C.n+1D.不能確定

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

度為0的結(jié)點(diǎn)的個(gè)數(shù)是B。

A.9B.11C.15D.不能確定

79.具有10個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)中有B個(gè)度為2的結(jié)點(diǎn)。

A.8B.9C.10D.11

80.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的」

倍。

A.1/2B1C2D4

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

和的B倍。

A.1/2B1C2D4

（左中右）我按我做的題目舉例吧：后序序列為：bfegcda,中序序列為：

badefcg,求前序序列。

這里會(huì)用：后序列序列最后一個(gè)值即樹(shù)（或子樹(shù)）的根。

由后序"bfegcda"知a為根，由中序"badefcg"知a的左子樹(shù)僅有b一個(gè)節(jié)點(diǎn)。即圖:L

去除序列中的b和a得后序"fegcd"和中序"defcg"，可知，d為a的右子樹(shù)樹(shù)根（后序最后一個(gè)值）且d的左子樹(shù)為空（d

前面無(wú)值），同理再去掉d得至!）,"fegc"和"efcg",可知c為d的右子樹(shù)樹(shù)根，如圖2.

由中序"efcg"知c的右子樹(shù)為g,左子樹(shù)為e,f,同理得最后結(jié)果樹(shù)為圖3.

于是得出前序列為：

abdcefg

82.某二叉樹(shù)結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE,

則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：C

A.3B.2C.4D.5

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

其前綴形式為O將算術(shù)表達(dá)式的中綴形式作為一棵二叉樹(shù)的中序遍

ABC*+DE/-fD

歷序列，將后綴形式作為

這棵二叉樹(shù)的后序遍歷序列，再由二叉樹(shù)的中序遍歷序列和后序遍歷序列唯一的確定這棵

二叉樹(shù)，在對(duì)其進(jìn)行先序遍歷，就可得出算術(shù)表達(dá)式的前綴形式。

A.—A+B*C/DEB.—A+B*CD/EC—+*ABC/DE

D.—+A*BC/DE

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

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

則可能得到的一種頂點(diǎn)序列為A.

①A.a,b,e,c,d,fB.a,c,f,e,b,d

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

②A.a,b,c,e,d,fB.a,b,c,e,f,d

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

85.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的

_=A_。

A.先序遍歷B.中序遍歷C.后序遍歷D.按層

遍歷

86.采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的

_Do

A.先序遍歷B.中序遍歷C.后序遍歷D.按層

遍歷

87.具有n個(gè)結(jié)點(diǎn)的連通圖至少有A條邊。

A.n-1B.nC.n(n-l)/2D.2n

88.廣義表((a),a)的表頭是C,表尾是C.

A.aB()C(a)D((a))

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

A.aB()C(a)D((a))

90.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為匕的線性表。

A散列存儲(chǔ)B順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C壓縮存儲(chǔ)

D索引存儲(chǔ)

91.對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須」o

A以順序方式存儲(chǔ)B以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)

鍵字有序排列

C以鏈?zhǔn)椒绞酱鎯?chǔ)D以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)

鍵字有序排列

92.采用折半查找法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查

找長(zhǎng)度為Do

2

A0(n)BO(nlog2n)C0(n)D

O(log2n)

93.有一個(gè)有序表為｛1,3,9,12,32,41,45,62,75,77,

82,95,100),當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí)，C次比較后查

找成功。

A.11B5C4D8

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

其左孩子的值、小于其右孩子的值。這種說(shuō)法B.

A正確B錯(cuò)誤

95.下面關(guān)于B樹(shù)和B+樹(shù)的敘述中，不正確的結(jié)論是A。

AB樹(shù)和B+樹(shù)都能有效的支持順序查找BB樹(shù)和B+樹(shù)都

能有效的支持隨機(jī)查找

CB樹(shù)和B+樹(shù)都是平衡的多叉樹(shù)DB樹(shù)和B+樹(shù)都

可用于文件索引結(jié)構(gòu)

96.以下說(shuō)法錯(cuò)誤的是B。

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

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

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

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

理沖突的方法。

97.查找效率最高的二叉排序樹(shù)是工o

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

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

C.平衡二叉樹(shù)。

D.沒(méi)有左子樹(shù)的二叉排序樹(shù)。

98.排序方法中，從未排序序列中依次取出元素與已排序序列中的

元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為

Co

.希爾排序。冒泡排序插入排序選擇排

ABCDo

序

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

序無(wú)關(guān)的是O

A.希爾排序B.冒泡排序C.直接插入排序D.直

接選擇排序

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

A.94,31,53,23,16,72B.94,53,31,72,16,23將所有數(shù)據(jù)

序列按完全二叉樹(shù)從根開(kāi)始放，如果所有分支都小于或者等于孩子結(jié)點(diǎn)關(guān)鍵碼，就是小頂堆，反之，如果所有分支結(jié)點(diǎn)的關(guān)鍵碼大于

或者等于孩子結(jié)點(diǎn)關(guān)鍵碼，則為大頂堆

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

101.堆排序是一種B排序。

A.插入B.選擇C.交換D.歸并

102.在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。

A.順序查找B.折半查找C.分塊查找D.插入

103.直接選擇排序的時(shí)間復(fù)雜度為D。(n為元素個(gè)數(shù))

2

A.O(n)B.O(log2n)C.O(nlog2n)D.O(n)

二、填空題。

1.數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)

三種類(lèi)型，樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱(chēng)非線性結(jié)構(gòu).

2.數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)

和圖狀結(jié)構(gòu)4種.

3.在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且

只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒(méi)魚(yú)后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)

點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。

4.線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存

在一對(duì)多關(guān)系,圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。

5.在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只

有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后

續(xù)結(jié)點(diǎn)可以任意多個(gè)°

6.數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是」啦_、鏈?zhǔn)?、索引?/p>

散列存儲(chǔ)。

7.衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時(shí)間

復(fù)雜度與空間復(fù)雜度。

8.評(píng)估一個(gè)算法的優(yōu)劣，通常從時(shí)間復(fù)雜度和空間復(fù)雜度

兩個(gè)方面考察。

9.算法的5個(gè)重要特性是有窮性、確定性、可行性、

輸入和輸出。

10.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素時(shí)，需向前移動(dòng)

n-i-1個(gè)元素。

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

驅(qū)結(jié)點(diǎn)。

12.在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向前驅(qū)結(jié)點(diǎn),

另一個(gè)指向后繼結(jié)點(diǎn)。

13.在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，需要平均移動(dòng)n個(gè)數(shù)

據(jù)元素，移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與也量有關(guān)。

14.當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，

但要求以最快的速度存取線性表的元素是，應(yīng)采用順序存儲(chǔ)結(jié)

構(gòu)。

15.根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將

線性鏈表分成單鏈表和雙鏈表。

16.順序存儲(chǔ)結(jié)構(gòu)是通過(guò)下標(biāo)表示元素之間的關(guān)系的；鏈?zhǔn)酱?/p>

儲(chǔ)結(jié)構(gòu)是通過(guò)*表示元素之間的關(guān)系的。

17.帶頭結(jié)點(diǎn)的循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是

L->next->next=L。

18.工是限定僅在表尾進(jìn)行插入或刪除操作的線性表，其運(yùn)算

遵循后進(jìn)先出的原則。

19.空串是零個(gè)字符的串,其長(zhǎng)度等于垂。空白串是由一個(gè)或

多個(gè)空格字符組成的串,其長(zhǎng)度等于其包含的空格個(gè)數(shù)。

20.組成串的數(shù)據(jù)元素只能是單個(gè)字符。

21.一個(gè)字符串中任意個(gè)連續(xù)字符構(gòu)成的部分稱(chēng)為該串的子串。

22.子串"str"在主串"datastructurez/中的位置是

5。

23.二維數(shù)組M的每個(gè)元素是6個(gè)字符組成的串，行下標(biāo)i的范圍

從。到8,列下標(biāo)j的范圍從1到10,則存放M至少需要540個(gè)

字節(jié)；M的第8列和第5行共占108個(gè)字節(jié)。

24.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即三元組表和十字

鏈表.

25.廣義表((a)((b),c)(((d))))的長(zhǎng)度是3，深度是40

26.在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的

個(gè)數(shù)為n2,則有n0=

n2+l。

27.在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為_(kāi)m￡一

28.一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有_互工個(gè)結(jié)點(diǎn)。

29.深度為5的二叉樹(shù)至多有31個(gè)結(jié)點(diǎn)。

30.若某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則

該二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為69。

31.某二叉樹(shù)的前序遍歷序列是abdgcefh,中序序列是dgbaechf,

其后序序列為gdbehfca。

32.線索二叉樹(shù)的左線索指向其遍歷序列中的前驅(qū),右線

索指向其遍歷序列中的后繼。

33.在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方

法是散列查找法.

34.在分塊索引查找方法中，首先查找索引表,然后查找

相應(yīng)的塊表。

35.一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二樹(shù)而變成一個(gè)有序

序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。

36.具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為—也一

37.已知圖G的鄰接表如圖所示，其從頂點(diǎn)vl出發(fā)的深度優(yōu)先搜索

序列為_(kāi)vlv2V3V6V5V4,其從頂點(diǎn)vl出發(fā)的廣度優(yōu)先搜索序列為

_vlv2V5V4V3V6_。

38.索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)索引隸

屬于某個(gè)數(shù)據(jù)記錄集，它由若干索引項(xiàng)組成,索引項(xiàng)的結(jié)構(gòu)為關(guān)鍵

字和關(guān)鍵字對(duì)應(yīng)記錄的地址.

39.Prim算法生成一個(gè)最小生成樹(shù)每一步選擇都要滿足用或數(shù)

不超過(guò)n-1,

當(dāng)前選擇的邊的權(quán)值是候選邊中最小的，選中的邊加入樹(shù)中不產(chǎn)

生回路三項(xiàng)原則。

40.在一棵m階B樹(shù)中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)最多有m棵子

樹(shù)，最少有m/2棵子樹(shù)。

三、判斷題。

1.在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮各結(jié)點(diǎn)的值如何。（V）

2.抽象數(shù)據(jù)類(lèi)型