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

(1)以下數據結構中哪一個是線性結構？()

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

(2)在一個單鏈表HL中，若要在當前由指針p指向的結點后而插入一個由q指向的結

點，則執行如下()語句序列。

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)()不是隊列的基本運算。

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

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

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

成()個不同的字符串。

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

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

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

以下6-8題基于下圖：

(6)該二叉樹結點的前序遍歷的序列為()。

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)該二叉樹結點的中序遍歷的序列為()。

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)下面關于圖的存儲的敘述中正確的是()。

A)用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關

B)用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數和結點個數都有關

C)用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結點個數和邊數都有關

D)用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關

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

結果？()

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

一、單項選擇題

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

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

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

(1)設Huffman樹的葉子結點數為m,則結點總數為()。

A)2mB)2m-1

C)2m+lD)m+1

(2)若順序存儲的循環隊列的QueueMaxSize=n,則該隊列最多可存儲()個元

素。

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

(3)下述哪一條是順序存儲方式的優點？()

A)存儲密度大B)插入和刪除運算方便

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

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

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

10

進制表示，m>3)()。

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

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

A)若一個葉子是某二叉樹的中序遍歷的最后一個結點，則它必是該二叉樹的前序遍歷最

后一個結點

B)若一個結點是某二叉樹的前序遍歷最后一個結點，則它必是該二叉樹的中序遍歷的最

后一個結點

0若一個結點是某二叉樹的中序遍歷的最后一個結點，則它必是該二叉樹的前序最后一

個結點

D)若一個樹葉是某二叉樹的前序最后一個結點，則它必是該二叉樹的中序遍歷最后一個

結點

(6)k層二叉樹的結點總數最多為()。

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

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

A)線性表以鏈接方式存儲，并且按關鍵碼值排好序

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

C)線性表以順序方式存儲，并且按關鍵碼值排好序

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

(8)對n個記錄進行堆排序，所需要的輔助存儲空間為()。

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

(9)對于線性表(7,34,77,25,64,49,20,14)進行散列存儲時，若選用H(K)

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

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

(10)下列關于數據結構的敘述中，正確的是()。

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

B)遞歸算法的程序結構比迭代算法的程序結構更為精煉

C)樹是一種線性結構

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

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

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

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

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

(1)對一個算法的評價，不包括如下()方面的內容。

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

(2)在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針p指向的結點，則執行

()。

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)對線性表，在下列哪種情況下應當采用鏈表表示？()

A)時常需要隨機地存取元素B)時常需要進行插入和刪除操

作。表中元素需要占領一片連續的存儲空間D)表中元素的個數不變

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

A)231B)3210312D)123

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

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

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

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

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

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

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

(8)在稀疏矩陣的帶行指針向量的鏈接存儲中，每一個單鏈表中的結點都具有相同

的

()。

A)行號B)列號C)元素值D)非零元素個數

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

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

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

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

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

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

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

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

(1)以下數據結構中哪一個是線性結構？()

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

(2)若某鏈表最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，

則采用()存儲方式最節省時間。

A)單鏈表B)雙鏈表C)帶頭結點的雙循環鏈表D)單循環鏈表

(3)()不是隊列的基本運算。

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

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

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

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

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

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

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

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

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

(6)則該二叉樹結點的前序遍歷的序列為()。

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)該二叉樹有()個葉子。

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)設有關鍵碼序列(q,g,m,z,a),()序列是從上述序列出發建的小根堆的結

果。

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

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

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

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

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

(1)隊列的特點是()。

A)先進后出B)先進先出

C)任意位置進出D)前面都不正確

(2)有n個記錄的文件，如關鍵字位數為d,基數為r,則基數排序共要進行()

遍分配與采集。

A)nB)dC)rD)n-d

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

()。

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

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

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

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

(5)快速排序執行一遍之后，已經到位的元素個數是()。

A)1B)3C)D)

(6)設森林F對應的二叉樹為B,它有m個結點，B的根為p,p的右子樹上的結點個數

為n,森林F中第一棵樹的結點個數是(底

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

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

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

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

A)廣義表可以是一個多層次的結構B)廣義表至少有一個元素

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

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

叉樹各有f個結點和c個結點，下列關系式不正確的是()。

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

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

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

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

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

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

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

(1)下列文件的物理結構中，不利于文件長度動態增長的文件物理結構是()。

A)順序結構B)鏈接結構C)索引結構D)Hash結構

(2)在數據結構中，數據元素可由()。

A)實體B)域C)數據項D)字段

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

的時間復雜度是()。

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

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

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

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

A)度為0的結點B)度為1的結點C)度為2的結點D)帶權的結點

(6)設D={A,B,C,D},R={<E,A>,<A,B>,<B,D>,<D,E>,<D,A>},則數據結構(D,{R})是

()?

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

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

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)假定關鍵字K=442205883,允許存儲地址為四位十進制數，并且Hash地址為6111,

則所采用的構造Hash函數的方法是()。

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

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

隨問題的規模n的增大，算法執行時間的增長率同()相同。

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

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

A)線性表以順序方式存儲，并且按關鍵碼值排好序

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

C)線性表以鏈接方式存儲，并且按關鍵碼值排好序

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

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

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

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

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

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

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

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

(2)將一個A[L.100,1..100]的三對角矩陣，按行優先存入一維數組B[298]中，A中

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

A)198B)1950197D)198

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

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

個非零元。

(3)若度為m的哈夫曼樹中，其葉結點個數為n,則非葉結點的個數為()。

A)n-1B)C)D)

(4)若一個有向圖具有拓撲排序序列，并且頂點按拓撲排序序列編號，那末它的鄰接矩

陣必然為()。

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

(5)設森林F對應的二叉樹為有m個結點，此二叉樹根的左子樹的結點個數為k,則

另一棵子樹的結點個數為()。

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

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

少要進行()次探測。

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

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

共有()個結點。

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

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

較次數較少。

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

(9)如果只考慮有序樹的情形，那末具有7個結點的不同形態的樹共有()棵。

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

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

A)只需做刪除標B)需挪移記錄

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

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

(1)參考答案：0

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

的非零元素個數是3個，所知a