數(shù)據(jù)結(jié)構(gòu)練習(xí)

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？()

A)有向圖B)隊(duì)列C)線索二叉樹D)B樹

(2)在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后而插入一個(gè)由q指向的結(jié)

點(diǎn)，則執(zhí)行如下()語(yǔ)句序列。

A)p=q;p->next=q;B)p->next=q;q->next=p;

C)p->next=q->next;p=q;D)q->next=p->next;p->next=q;

(3)()不是隊(duì)列的基本運(yùn)算。

A)在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B)從隊(duì)頭刪除一個(gè)元素

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

(4)字符A、B、C挨次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組

成()個(gè)不同的字符串。

A)14B)5C)6D)8

(5)由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為()。

A)11B)35C)19D)53

以下6-8題基于下圖：

(6)該二叉樹結(jié)點(diǎn)的前序遍歷的序列為()。

A)E、G、F、A、C、D、BB)E、A、G、C、F、B、D

C)E、A、C、B、D、G、FD)E、G、A、C、D、F、B

(7)該二叉樹結(jié)點(diǎn)的中序遍歷的序列為()。

A)A、B、C、D、E、G,FB)E、A、G、C、F、B、D

C)E、A、C、B、D、G、FD)B、D、C、A、F、G、E

(8)該二叉樹的按層遍歷的序列為()?

A)E、G、F、A、C、D、BB)E、A、C、B、D、G、F

0E、A、G、C、F、B、DD)E、G、A、C、D、F、B

(9)下面關(guān)于圖的存儲(chǔ)的敘述中正確的是()。

A)用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)

B)用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān)

C)用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)

D)用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)

(10)設(shè)有關(guān)鍵碼序列(q,g,m,z,a,n,p,x,h),下面哪一個(gè)序列是從上述序列出發(fā)建堆的

結(jié)果？()

A)a,g,h,m,n,p,q,x,zB)a,g,m,h,q,n,p,x,zC)g,in,q,a,n,p,x,h,zD)

h,g,m,p,a,n,q,x,z

一、單項(xiàng)選擇題

(1)B(2)D(3)A(4)B(5)B

(6)C(7)A(8)C(9)B(10)B

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)設(shè)Huffman樹的葉子結(jié)點(diǎn)數(shù)為m,則結(jié)點(diǎn)總數(shù)為()。

A)2mB)2m-1

C)2m+lD)m+1

(2)若順序存儲(chǔ)的循環(huán)隊(duì)列的QueueMaxSize=n,則該隊(duì)列最多可存儲(chǔ)()個(gè)元

素。

A)nB)n-lC)n+1D)不確定

(3)下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？()

A)存儲(chǔ)密度大B)插入和刪除運(yùn)算方便

C)獲取符合某種條件的元素方便D)查找運(yùn)算速度快

(4)設(shè)有一個(gè)二維數(shù)組A[m][n],假設(shè)A[0][0]存放位置在600(10),A[3][3]存放位置

在678(10),每一個(gè)元素占一個(gè)空間，問A[2][3](10)存放在什么位置？(腳注(10)表示用

10

進(jìn)制表示，m>3)()。

A)658B)648C)633D)653

(5)下列關(guān)于二叉樹遍歷的敘述中，正確的是()。

A)若一個(gè)葉子是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷最

后一個(gè)結(jié)點(diǎn)

B)若一個(gè)結(jié)點(diǎn)是某二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷的最

后一個(gè)結(jié)點(diǎn)

0若一個(gè)結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序最后一

個(gè)結(jié)點(diǎn)

D)若一個(gè)樹葉是某二叉樹的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個(gè)

結(jié)點(diǎn)

(6)k層二叉樹的結(jié)點(diǎn)總數(shù)最多為()。

A)2k-1B)2k+lC)2K-1D)2kT

(7)對(duì)線性表進(jìn)行二分法查找，其前提條件是()。

A)線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序

B)線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序

C)線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序

D)線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序

(8)對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為()。

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

(9)對(duì)于線性表(7,34,77,25,64,49,20,14)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)

=K%7作為散列函數(shù)，則散列地址為0的元素有()個(gè)。

A)1B)2C)3D)4

(10)下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是()。

A)數(shù)組是不同類型值的集合

B)遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉

C)樹是一種線性結(jié)構(gòu)

D)用一維數(shù)組存儲(chǔ)一棵徹底二叉樹是有效的存儲(chǔ)方法

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)B(2)B(3)A(4)D(5)A

(6)A(7)C(8)C(9)D(10)D

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下()方面的內(nèi)容。

A)茁壯性和可讀性B)并行性C)正確性D)時(shí)空復(fù)雜度

(2)在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行

()。

A)p->next=HL->next;HL->next=pB)p->next=HL;HL=p

C)p->next=HL;p=HLD)HL=p;p->next=HL

(3)對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？()

A)時(shí)常需要隨機(jī)地存取元素B)時(shí)常需要進(jìn)行插入和刪除操

作。表中元素需要占領(lǐng)一片連續(xù)的存儲(chǔ)空間D)表中元素的個(gè)數(shù)不變

(4)一個(gè)棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是()。

A)231B)3210312D)123

(5)每一趟都能選出一個(gè)元素放在其最終位置上，并且不穩(wěn)定的排序算法是()。

A)冒泡排序B)簡(jiǎn)單選擇排序C)希爾排序D)直接插入排序

(6)采用開放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度()?

A)低于鏈接法處理沖突B)高于鏈接法處理沖突

C)與鏈接法處理沖突相同D)高于二分查找

(7)若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為()參數(shù)。

A)值B)函數(shù)C)指針D)引用

(8)在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每一個(gè)單鏈表中的結(jié)點(diǎn)都具有相同

的

()。

A)行號(hào)B)列號(hào)C)元素值D)非零元素個(gè)數(shù)

(9)快速排序在最壞情況下的時(shí)間復(fù)雜度為()。

A)0(log2n)B)0(nlog2n)C)0(n)D)0(n2)

(10)從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為()。

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

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)B(2)A(3)B(4)C⑸B

(6)B(7)D(8)A(9)D(10)C

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？()

A)有向圖B)棧C)二叉樹D)B樹

(2)若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，

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

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

(3)()不是隊(duì)列的基本運(yùn)算。

A)在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B)從隊(duì)頭刪除一個(gè)元素

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

(4)字符A、B、C、D挨次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可

以組成()個(gè)不同的字符串？

A)15B)14C)16D)21

(5)由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為()。

A)11B)37C)19D)53

以下6-8題基于下面的敘述：若某二叉樹結(jié)點(diǎn)的中序遍歷的序列為A、B、C、D、E、F、

G,后序遍歷的序列為B、D、C、A、F、G、E。

(6)則該二叉樹結(jié)點(diǎn)的前序遍歷的序列為()。

A)E、G、F、A、C、D、BB)E、A、G、C、F、B、D

C)E、A、C、B、D、G、FD)E、G、A、C、D、F、B

(7)該二叉樹有()個(gè)葉子。

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

(8)該二叉樹的按層遍歷的序列為()。

A)E、G、F、A、C、D、BB)E、A、C、B、D、G,F

C)E、A、G、C、F、B、DD)E、G、A、C、D、F、B

(9)下面的二叉樹中，()不是徹底二叉樹。

(10)設(shè)有關(guān)鍵碼序列(q,g,m,z,a),()序列是從上述序列出發(fā)建的小根堆的結(jié)

果。

A)a,g,m,q,zB)a,g,m,z,qC)g,m,q,a,zD)g,m,a,q,z

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)B(2)C(3)A(4)B(5)B

(6)C(7)A(8)C(9)C(10)B

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)隊(duì)列的特點(diǎn)是()。

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

C)任意位置進(jìn)出D)前面都不正確

(2)有n個(gè)記錄的文件，如關(guān)鍵字位數(shù)為d,基數(shù)為r,則基數(shù)排序共要進(jìn)行()

遍分配與采集。

A)nB)dC)rD)n-d

(3)在二叉樹結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序

()。

A)都不相同B)徹底相同

C)先序和中序相同，而與后序不同D)中序和后序相同，而與先序不同

(4)限定在一端加入和刪除元素的線性表稱為()o

A)雙向鏈表B)單向鏈表C)棧D)隊(duì)列

(5)快速排序執(zhí)行一遍之后，已經(jīng)到位的元素個(gè)數(shù)是()。

A)1B)3C)D)

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

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

A)m-n-1B)n+1C)m-n+1D)m-n

⑺設(shè)有198個(gè)初始?xì)w并段，如采用K-路平衡歸并三遍完成排序，則K值最大為()。

A)12B)13C)14D)15

(8)下面關(guān)于廣義表的敘述中，不正確的是()。

A)廣義表可以是一個(gè)多層次的結(jié)構(gòu)B)廣義表至少有一個(gè)元素

C)廣義表可以被其他廣義表所共享D)廣義表可以是一個(gè)遞歸表

(9)設(shè)二叉樹根結(jié)點(diǎn)的層次為0,一棵深度(高度)為k的滿二叉樹和同樣深度徹底二

叉樹各有f個(gè)結(jié)點(diǎn)和c個(gè)結(jié)點(diǎn)，下列關(guān)系式不正確的是()。

A)f>=cB)c>fC)f=2k+l-aD)c>sk-l

(10)從L=((apple,pear),(orange,banana)),取出banana元素的表達(dá)式為()。

A)head(tail(L))B)head(head(tai1(L)))

C)tail(head(tai1(L)))D)head(tai1(head(tail(L))))

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)B(2)B(3)B(4)C(5)A

(6)D(7)C(8)B(9)B(10)D

(1)下列文件的物理結(jié)構(gòu)中，不利于文件長(zhǎng)度動(dòng)態(tài)增長(zhǎng)的文件物理結(jié)構(gòu)是()。

A)順序結(jié)構(gòu)B)鏈接結(jié)構(gòu)C)索引結(jié)構(gòu)D)Hash結(jié)構(gòu)

(2)在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素可由()。

A)實(shí)體B)域C)數(shù)據(jù)項(xiàng)D)字段

(3)對(duì)于有n個(gè)頂點(diǎn)的有向圖，由弗洛伊德(Floyd)算法求每一對(duì)頂之間的最短路徑

的時(shí)間復(fù)雜度是()。

A)0(1)B)0(n)C)0(n)D)0(n3)

(4)對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間為()。

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

(5)哈夫曼樹中一定不存在()。

A)度為0的結(jié)點(diǎn)B)度為1的結(jié)點(diǎn)C)度為2的結(jié)點(diǎn)D)帶權(quán)的結(jié)點(diǎn)

(6)設(shè)D={A,B,C,D},R={<E,A>,<A,B>,<B,D>,<D,E>,<D,A>},則數(shù)據(jù)結(jié)構(gòu)(D,{R})是

()?

A)樹B)圖B)線性表D)前面都正確

(7)()關(guān)鍵碼序列不符合堆的定義。

A)A、C、D、G、H、M、P、Q、R、X

B)A、C、M、D、H、P、X、G、Q、R

C)A、D、P、R、C、Q、X、M、H、G

D)A、D、C、M、P、G、H、X、R、Q

(8)假定關(guān)鍵字K=442205883,允許存儲(chǔ)地址為四位十進(jìn)制數(shù)，并且Hash地址為6111,

則所采用的構(gòu)造Hash函數(shù)的方法是()。

A)直接定址法B)平方取中法C)除留余數(shù)法，模為97D)折疊法

(9)在算法的時(shí)間復(fù)雜度中，n表示問題規(guī)模，f(n)表示基本操作重復(fù)執(zhí)行的次數(shù)，則

隨問題的規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率同()相同。

A)f(n)B)nC)0(n)D)前面都不正確

(10)對(duì)線性表進(jìn)行二分法查找，其前提條件是()。

A)線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序

B)線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序

C)線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序

D)線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)A(2)C(3)D(4)B(5)B

(6)B(7)C(8)D(9)A(10)A

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限雙端隊(duì)列得到，也不能

由輸出受限雙端隊(duì)列得到的輸出序列是()。

A)1234B)4132C)4231D)4213

(2)將一個(gè)A[L.100,1..100]的三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組B[298]中，A中

元素a66,65(即該元素下標(biāo))在B數(shù)組中的位置k為()(假設(shè)B[0]的位置是1)。

A)198B)1950197D)198

【分析】如下所示，三對(duì)角矩陣第1行和最后1行非零元素個(gè)數(shù)為2個(gè)，其余各行的非

零元素個(gè)數(shù)是3個(gè)，所知a66,65前面共有2+3*64=194個(gè)非零元素，a66,65本身是第195

個(gè)非零元。

(3)若度為m的哈夫曼樹中，其葉結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù)為()。

A)n-1B)C)D)

(4)若一個(gè)有向圖具有拓?fù)渑判蛐蛄?，并且頂點(diǎn)按拓?fù)渑判蛐蛄芯幪?hào)，那末它的鄰接矩

陣必然為()。

A)對(duì)稱矩陣B)稀疏矩陣C)三角矩陣D)普通矩陣

(5)設(shè)森林F對(duì)應(yīng)的二叉樹為有m個(gè)結(jié)點(diǎn)，此二叉樹根的左子樹的結(jié)點(diǎn)個(gè)數(shù)為k,則

另一棵子樹的結(jié)點(diǎn)個(gè)數(shù)為()。

A)m-k+1B)k+1C)m-k-1D)m-k

(6)假定有K個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這K個(gè)關(guān)鍵字存入散列表中，至

少要進(jìn)行()次探測(cè)。

A)K-1次B)K次C)K+1次D)K(K+l)/2次

(7)一棵深度為k的平衡二叉樹，其每一個(gè)非終端結(jié)點(diǎn)的平衡因子均為0,則該樹

共有()個(gè)結(jié)點(diǎn)。

A)2k-l-lB)2k-1C)2k-l+lD)2k-1

(8)如表r有100000個(gè)元素，前99999個(gè)元素遞增有序，則采用()方法比

較次數(shù)較少。

A)直接插入排序B)快速排序C)歸并排序D)選擇排序

(9)如果只考慮有序樹的情形，那末具有7個(gè)結(jié)點(diǎn)的不同形態(tài)的樹共有()棵。

A)132B)154C)429D)前面均不正確

(10)對(duì)ISAM文件的刪除記錄時(shí)，普通()

A)只需做刪除標(biāo)B)需挪移記錄

C)需改變指針D)一旦刪除就要做整理

一、單項(xiàng)選擇題(每小題2分，共20分)

(1)參考答案：0

(2)【分析】如下所示，三對(duì)角矩陣第1行和最后1行非零元素個(gè)數(shù)為2個(gè)，其余各行

的非零元素個(gè)數(shù)是3個(gè)，所知a