數(shù)據(jù)結(jié)構(gòu)期末考試題及答案

數(shù)據(jù)結(jié)構(gòu)期末考試題及答案

一、選擇題

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

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)在計算機內(nèi)存中的表示是指A。

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)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)。

A.邏輯B.存儲C.邏輯和存儲D.物理

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

CO

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

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

5.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮Ao

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

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

6.以下說法正確的是Do

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

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

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

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

7.算法分析的目的是C,算法分析的兩個主要方面是Ao

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

系

C.分析算法的效率以求改進C.分析算法的易讀性和文檔性

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

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

8.下面程序段的時間復(fù)雜度是O(n2)

s=0；

for（1=0；i<n；i++）for（j

—0；j<n；j++）

S+=B[i][j];

sum=s；

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

for（i=0；i<n；i++）

for（j=0；j<m；j++）

=0；

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

i=0；while

（i<=n）i=

i*3；

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

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

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

C.棧的操作方式是先進先出

D.隊列的操作方式是先進后出

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

Bo

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

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

要一致

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

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

13.鏈表不具備的特點是Ao

A.可隨機訪問任一結(jié)點B.插入刪除不需要移動元素

C.不必事先估計存儲空間D.所需空間與其長度成正比

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

next==NULL

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

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

next==NULL

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

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

一個結(jié)點，則采用

D存儲方式最節(jié)省運算時間。

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

點的雙循環(huán)鏈表

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

Bo

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

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

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

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

B在循環(huán)雙鏈表的p所指的結(jié)點之前插入s所指結(jié)點的操作是D。

A.p—>

prior—>

prior

B.p—>

prior—>

priorC.s

—>

prior—>next=s

D.s->

prior—>

prior=s

2）如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用D存儲方式最

節(jié)省時間。

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

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

的時間復(fù)雜度是Bo

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

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

操作與鏈表的長度有關(guān)。

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

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

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

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

23.與單鏈表相比，雙鏈表的優(yōu)點之一是Do

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

B.可以進行隨機訪問

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

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

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

的后面插入新元素，則最好使用B。

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

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

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

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

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

的移動次數(shù)為：Ao

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

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

CO

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

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

27.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？Co

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

C存儲密度大D刪除運算方便

28.下面關(guān)于線性表的敘述中，錯誤的是哪一個？Bo

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

B線性表采用順序存儲，便于進行插入和刪除操作。C

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

線性表采用鏈?zhǔn)酱鎯Γ阌谶M行插入和刪除操作。

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

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

3Q在n個結(jié)點的線性表的數(shù)組實現(xiàn)中，算法的時間復(fù)雜度是0(1)的操

作是Ao

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

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

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

D.以上都不對

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

素的算法的時間復(fù)雜度為Co

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

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

CO

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

D.O(1)O(1)

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

時間復(fù)雜度為C。

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

34.單鏈表中，增加一個頭結(jié)點的目的是為了Co

A.使單鏈表至少有一個結(jié)點B.標(biāo)識表結(jié)點中首結(jié)點的位置

C.方面運算的實現(xiàn)D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?/p>

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

BoA.p-

>next=p

—>next=

p->next

—s；C.p

—>next=

s—>

next=s—>next；p—>next=s

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

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

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

37.棧的特點是B,隊列的特點是Ao

A.先進先出B.先進后出

38.棧和隊列的共同點是Co

A.都是先進后出B.都是先進先出

C.只允許在端點處插入和刪除元素D.沒有共同點

39.一個棧的進棧序列是a,b,c,d,e,則棧的不可能的輸出序列是C。

A.edcbaB.decbaC.dceabD.abcde

40.設(shè)有一個棧，元素依次進棧的順序為A、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不是隊列的基本運算？

A.從隊尾插入一個新元素B.從隊列中刪除第i個元素

C.判斷一個隊列是否為空D.讀取隊頭元素的值

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

pn,若pl=n,則pi為Co

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

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

A.st—>top!

top==-1

C.st—>top!

top==MaxSize

44.判定一個順序棧st（最多元素為MaxSize）為滿的條件是D。

A.st—>top!

top==-1

C.st—>top!

top==MaxSize

45.一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是Bo

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

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

名判定一個循環(huán)隊列qu（最多元素為MaxSize）為空的條件是C。

A.qu—>rear-qu—>

rear-qu—>front-1==MaxSize

C.qu—>

front—1

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

則判斷循環(huán)隊列空的條件是C。

A.front==rear+1B.rear==front+1C.front==rear

D.front==0

反向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針s所指的結(jié)點時，應(yīng)

執(zhí)行D操作。

A.h->

next=h；

C.s—>

next=h—>

next=s；

以輸入序列為ABC,可以變?yōu)镃BA時，經(jīng)過的棧操作為B

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

5）若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1m],top[lbtop[2]

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

的條件是Bo

A.|top[2]—top[ll|=0B.top[l]+1=top[2]C.top[l]+top[2]=m

D.top[l]=top[2]

51設(shè)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用D數(shù)

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

A.線性表的順序存儲結(jié)構(gòu)B.隊列C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

D.棧

2允許對隊列進行的操作有Do

A.對隊列中的元素排序B.取出最近進隊的元素

C.在隊頭元素之前插入元素D.刪除隊頭元素

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

A.無法判斷隊列是否為空B.無法判斷隊列是否為滿

C.隊列不可能滿D.以上說法都不對

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

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

別為B。

A.1和5B.2和4C.4和2D.5和1

55.隊列的“先進先出”特性是指D。

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

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

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

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

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

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

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

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

向隊尾結(jié)點，則在進行出隊操作時C。

A.僅修改隊頭指針B.僅修改隊尾指針

C.隊頭、隊尾指針都可能要修改D.隊頭、隊尾指針都要修改

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

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

59.串的長度是指Bo

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

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

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

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

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

d設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱為Bo

A.連接B.模式匹配C.求子串D.求串長

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

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

的起始地址為CO

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

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

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

的起始地址為C0

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

61若聲明一個浮點數(shù)數(shù)組如下：froataverage]]=newfloat[30]；

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

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

6設(shè)二維數(shù)組人口...01,匕.川按行存儲在數(shù)組8中，則二維數(shù)組元素A[i,

j］在一維數(shù)組B中的下標(biāo)為Ao

A.n*(i—1)+jB.n*(i—1)+j—1C.i*(j—1)D.j*m+i

-1

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

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

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

67.數(shù)組A［0…4,-1...—3,5…7］中含有的元素個數(shù)是A。

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

68.對矩陣進行壓縮存儲是為了D。

A.方便運算B.方便存儲C.提高運算速度D.減少存儲空間

69.設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，

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

地址為Bo

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

70.稀疏矩陣一般的壓縮存儲方式有兩種，即Co

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

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

71.樹最適合用來表示Co

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

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

72.深度為5的二叉樹至多有C個結(jié)點。

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

73.對一個滿二叉樹，m個葉子，n個結(jié)點，深度為h,則D。

A.n=h+mBh+m=2nCm=h—1Dn=2h~1

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

Ao

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

對

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

是樹結(jié)構(gòu)信息，還是線索化信息，若0標(biāo)識樹結(jié)構(gòu)信息，1標(biāo)識線索，對應(yīng)葉結(jié)

點的左右鏈域，應(yīng)標(biāo)識為—D_o

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

K在下述論述中，正確的是Do

①只有一個結(jié)點的二叉樹的度為0；②二叉樹的度為2；③二叉樹的左右子

樹可任意交換；

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

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

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

的結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點的個數(shù)是Ao

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

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

的結(jié)點的個數(shù)是Bo

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

力具有10個葉子結(jié)點的二叉樹中有B個度為2的結(jié)點。

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

?在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的C倍。

A.1/2B1C2D4

&在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的B

倍。

A.1/2B1C2D4

2某二叉樹結(jié)點的中序序列為ABCDEFG,后序序歹U為BDCAFGE,則

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

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

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

DE/-,其前綴形式為Do

A.-A+B*C/DEB.-A+B*CD/EC-+*ABC/DED.-

+A*BC/DE

S4.已知一個圖，如圖所示，若從頂點a出發(fā)按深度搜索法進行遍歷，則可

能得到的一種頂點序列為—D—；按廣度搜索法進行遍歷，則可能得到的一

種頂點序列為—A—；

(DA.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.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的—A.

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

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

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

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

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

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

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

89.廣義表((a))的表頭是C表尾是Bo

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

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

A散列存儲B順序存儲或鏈?zhǔn)酱鎯壓縮存儲D索

引存儲

91.對線性表進行折半查找時，要求線性表必須B

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

序排列

C以鏈?zhǔn)椒绞酱鎯以鏈?zhǔn)椒绞酱鎯?，且結(jié)點按關(guān)鍵字有

序排列

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

Do

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é)點時，C次比較后查找成功。

A.11B5C4D8

4二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩

子的值、小于其右孩子的值。這種說法Bo

A正確B錯誤

§下面關(guān)于B樹和B+樹的敘述中，不正確的結(jié)論是Ao

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

效的支持隨機查找

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

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

i以下說法錯誤的是Bo

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

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

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

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

的方法。

9查找效率最高的二叉排序樹是Co

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

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

C.平衡二叉樹。

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

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

行比較，將其放入已排序序列的正確位置上的方法，稱為C0

A.希爾排序Bo冒泡排序C插入排序Do選擇排序

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

是D。

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

擇排序

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

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

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

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

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

102.D在鏈表中進行操作比在順序表中進行操作效率高。

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

103.直接選擇排序的時間復(fù)雜度為D°（n為元素個數(shù)）A.O

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

二、填空題。

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

型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu)

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

狀結(jié)構(gòu)4種。

3在線性結(jié)構(gòu)中，第一個結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1

個前驅(qū)結(jié)點；最后一個結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)

結(jié)點0

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

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

5在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個

前驅(qū)結(jié)點；葉子結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點可以任意多

個。

6數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是順序、鏈?zhǔn)?、索引和散列?/p>

儲。

7衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時間復(fù)雜度與

空間復(fù)雜度。

8評估一個算法的優(yōu)劣，通常從時間復(fù)雜度和空間復(fù)雜度兩個

方面考察。

9算法的5個重要特性是有窮性、確定性、可行性、輸入和輸

出。

IQ在一個長度為n的順序表中刪除第i個元素時，需向前移動n-i-1個

元素。

11在單鏈表中，要刪除某一指定的結(jié)點，必須找到該結(jié)點的前驅(qū)結(jié)點。

12在雙鏈表中，每個結(jié)點有兩個指針域，一個指向前驅(qū)結(jié)點，另一個指

向后繼結(jié)點。

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

移動數(shù)據(jù)元素的個數(shù)與位置有關(guān)。

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

以最快的速度存取線性表的元素是，應(yīng)采用順序存儲結(jié)構(gòu)。

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

表分成單鏈表和雙鏈表。

K順序存儲結(jié)構(gòu)是通過下標(biāo)表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是

通過指針表示元素之間的關(guān)系的。

17帶頭結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是L—>next—>

next=Lo

18棧是限定僅在表尾進行插入或刪除操作的線性表，其運算遵循后

進先出的原則。

B空串是零個字符的串，其長度等于零?？瞻状怯梢粋€或多個空格

字符組成的串，其長度等于其包含的空格個數(shù)。

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

2L一個字符串中任意個連續(xù)字符構(gòu)成的部分稱為該串的子串。

22子串“str"在主串"datastructure”中的位置是5。

3二維數(shù)組M的每個元素是6個字符組成的串，行下標(biāo)i的范圍從0到8,

列下標(biāo)j的范圍從1至打0,則存放M至少需要540個字節(jié)；M的第8列和第5

行共占108個字節(jié)。

21稀疏矩陣一般的壓縮存儲方法有兩種，即三元組表和十字鏈表。

25.廣義表((a),((b),c),(((d))))的長度是3,深度是4。

否在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0,度為2的結(jié)點的個數(shù)為

n2,則有n0=

n2+1o

27在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為n+10

S一棵有n個葉子結(jié)點的哈夫曼樹共有2n—l_個結(jié)點。

2深度為5的二叉樹至多有31個結(jié)點。

30若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹

的總結(jié)點個數(shù)為69。

31.某二叉樹的前序遍歷序列是abdgcefh,中序序列是dgbaechf,其后序序列

為gdbehfca。

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

遍歷序列中的后繼。

3在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是散

列查找法。

，在分塊索引查找方法中，首先查找索引表，然后查找相應(yīng)的

塊表。

玉一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列，

構(gòu)造樹的過程即為對無序序列進行排序的過程。

35具有10個頂點的無向圖，邊的總數(shù)最多為45o

3Z已知圖G的鄰接表如圖所示，其從頂點vl出發(fā)的深度優(yōu)先搜索序列為

_vlv2v3v6v5v4_,其從頂點vl出發(fā)的廣度優(yōu)先搜索序列為_vlv2V5V4V3V6一。

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

數(shù)據(jù)記錄集，它由若干索引項組成，索引項的結(jié)構(gòu)為關(guān)鍵字和關(guān)鍵字對應(yīng)記錄

的地址。

30Prim算法生成一個最小生成樹每一步選擇都要滿足邊的總數(shù)不超過n

-1,

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

項原則。

4）在一棵m階B樹中，除根結(jié)點外，每個結(jié)點最多有m棵子樹，最少

有m/2棵子樹。

三、判斷題。

J在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何。（4）

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

的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現(xiàn)。（V）

3抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關(guān)。N）

4順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶?。（x）

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

的。（x）

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