數(shù)據(jù)結(jié)構(gòu)（查找）練習(xí)題與答案

1、靜態(tài)查找表和動態(tài)查找表的區(qū)別是（）。

A.所包含的數(shù)據(jù)元素的類型不同

B.施加其上的操作不同

C.它們的邏輯結(jié)構(gòu)相同

D.以上都不對

正確答案：B

解析：B、若在查找的同時對表做修改操作（如插入和刪除），則相應(yīng)的查找表稱之

為動態(tài)查找表。若在查找中不涉及表的修改操作，則相應(yīng)的查找表稱之為靜態(tài)查找表。

2、順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。

A.索引存儲

B.壓縮存儲

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

D.哈希存儲

正確答案：C

解析：C、順序查找可以從前向后或從后向前依次查找，既適合于順序存儲結(jié)構(gòu)也適

合于鏈?zhǔn)酱鎯Y(jié)構(gòu)。

3、采用順序查找方法查找長度為n的順序表時，在等概率時成功查找的平均查找長度

為（）。

A.（n-l）/2

B.n

C.n/2

D.（n+l）/2

正確答案：D

解析：D、順序查找時，元素ai需i次比較，成功查找的平均查找長度=（1+2+...

+n）/n=（n+l）/2.

4、采用JI順序查找方法查找長度為n的順序表時，在等概率時不成功查找的平均查找長

度為（）。

A.(n-l)/2

B.n

C.n/2

D.(n+l)/2

正確答案：B

解析：B、當(dāng)查找的元素不在線性表中時，均需要n次元素之間的比較。

5、適合于折半查找的數(shù)據(jù)組織方式是()。

A.以鏈表存儲的有序線性表

B.以順序表存儲的有序線性表

C.以鏈表存儲的線性表

D.以順序表存儲的線性表

正確答案：B

解析：B、折半查找的數(shù)據(jù)必須是有序的。另外，折半查找中需要確定查找區(qū)間，這

要求存儲結(jié)構(gòu)最好具有隨機存取特性，而順序表滿足這個特性。

6、采用折半查找方法查找長度為n的線性表，當(dāng)n很大時，在等概率時不成功查找的

平均查找長度為()o

A.O(nlog2n)

B.0(n2)

C.0(n)

D.O(log2n)

正確答案：D

解析：D、采用折半查找時，若n很大，對應(yīng)的判定樹可以看成是一棵滿二叉樹，失

敗節(jié)點(外部節(jié)點)集中在最下一層，落在每個失敗節(jié)點時比較的次都均為log2n0

7、設(shè)有100個元素的有序表，采用折半查找方法，在等概率時成功時最大的比較次數(shù)

是()。

A.50

B.25

C.10

D.7

正確答案：D

解析：D、成功時最大比較次數(shù)為log2（n+l）（取上界）=log2（101）（取上界）=7。

8、已知一個長度為16的順序表，其元素按關(guān)鍵字有序排序，若采用折半查找法查找

一個存在的元素，則比較的次數(shù)最多是（）。

A.6

B.5

C.4

D.7

正確答案：B

解析：B、n=16,采用折半查找法查找一個存在的元素，即為成功查找。成功查找的

最多比較次數(shù)=log2（n+l）（取上界）=log2（17）（取上界）=5。

9、一個遞增有序表為R[O..ll],采用折半查找方法進(jìn)行查找，在一次不成功查找中，

以下（）是不可能的記錄比較序列。

A.R[5],R[8]、R[6]、R[7]

B.R[5]、R[8]、R[10]

C.R[5],R[2]、R[3]

D.R[5],R[8]sR[6]

正確答案：B

解析：B、畫出遞增有序表采用折半查找對應(yīng)的判定樹，一次失敗的查找必

須到達(dá)某個外部節(jié)點，而R[5]、R[8]、R[10]序列沒有到達(dá)任何外部節(jié)點。

10、對有3600個記錄的索引順序表（分塊表）進(jìn)行分塊查找，最理想的塊長是（）

A.[log23600]

B.1800

C.60

D.1200

正確答案：C

解析：C、n=3600,分塊查找最理想的塊長=$440=54匕（3600）=60。

11、二叉排序中，按（）遍歷二叉排序得到的序列是一個有序序列。

A后序

B.先序

C.中序

D層次

正確答案：C

解析：C、二叉排序的中序遍歷序列恰好是一個遞增有序序列。

12、在含有27個節(jié)點的二叉排序樹上，查找關(guān)鍵字為35的節(jié)點，則依次比較的關(guān)鍵

字有可能是（）.

A.46,36,18,28,35

B.18,36,28,46,35

C.28,36,18,46,35

D.46,28,18,36,35

正確答案：A

解析：A、畫出各選項對應(yīng)的查找樹,從中看到只有選項D對應(yīng)的查找樹構(gòu)成一棵二

叉排序樹，可以作為一棵二叉排序樹的一部分，其他查找樹均不構(gòu)成一棵二叉排序樹。

13、以下關(guān)于二叉排序樹的敘述中正確的是（）。

A.二叉排序樹是動態(tài)樹表，在插入新節(jié)點時會引起樹的重新分裂和合并

B.在二叉排序樹中進(jìn)行查找，關(guān)鍵字的比較次數(shù)不超過節(jié)點數(shù)的一半

C.對二叉排序樹進(jìn)行層次遍歷可以得到一個有序序列

D.在構(gòu)造二叉排序樹時，若關(guān)鍵字序列有序，則二叉排序樹的高度最大

正確答案：D

14、有一棵含有8個節(jié)點的二叉排序樹，其節(jié)點值為A~H,以下（）是其后序遍歷

結(jié)果。

A.BCAGEHFD

B.BDACEFHG

C.BCAEFDHG

D.ADBCEGFH

正確答案：C

解析：C、該二叉排序樹的中序序列為ABCDEFGH,后序序列應(yīng)是A-H的出棧序列，

其中選項A、B和D都不是合法的出棧序列，只有選項C是合法的出棧序列。

15、具有5層節(jié)點的AVL樹至少有（）個節(jié)點。

A.10

B.17

C.15

D.12

正確答案：D

解析：D、設(shè)Nh表示高度為h的平衡二叉樹中含有的最少節(jié)點數(shù)，有：

Nl=l,N2=2,Nh=Nh-l+Nh-2+l

由此，求出N5=12O

16、以下關(guān)于m階B-樹的敘述中正確的是（）。

A才對中每個節(jié)點至多有個關(guān)鍵字

B.所有葉子節(jié)點均在同一層上

C.當(dāng)插入一個關(guān)鍵字引起B(yǎng)-樹節(jié)點分裂時，樹增高一層

D.每個節(jié)點至少有兩棵非空子樹

正確答案：B

解析：B、選項A錯誤，因為m階B-樹可能只有一個根節(jié)點。選項B錯誤，在m階

B-樹中，除根節(jié)點外，每個節(jié)點至少有m/2（取上界）-1個關(guān)鍵字。選項D錯誤，當(dāng)

插入一個關(guān)鍵字引起B(yǎng)-樹節(jié)點分裂時，樹不一定會增高一層，只有節(jié)點分裂延續(xù)到根

節(jié)點，根節(jié)點也分裂后，樹才會增高一層。

17、在一棵m階B-樹中刪除一個關(guān)鍵字會引起合并，則該節(jié)點原有（）個關(guān)鍵字。

A.\m/2]

B.[m/2]-l

C.l

D.[m/2]+l

正確答案：B

解析：B、引起合并的節(jié)點應(yīng)為關(guān)鍵字個數(shù)的下限。

18、以下關(guān)于哈希查找的敘述中錯誤的是（）0

A.哈希函數(shù)選得好可以減少沖突現(xiàn)象

B.哈希函數(shù)H（k）=kMODp,p通常取小于等于表長的素數(shù)

C.用拉鏈法解決沖突易引起堆積現(xiàn)象

D.用線性探測法解決沖突易引起堆積現(xiàn)象

正確答案：C

解析：C、用拉鏈法解決沖突時不存在堆積現(xiàn)象，只有用線性探測法解決沖突時易引

起堆積現(xiàn)象。

19、以下關(guān)于哈希查找的敘述中正確的是（）。

A.哈希表的裝填因子等于表中填入的記錄數(shù)除以哈希表的長度

B.采用拉鏈法解決沖突時，查找一個元素的時間是相同的

C.哈希表在查找成功時的平均查找長度僅僅與表長有關(guān)

D.哈希查找中不需要任何關(guān)鍵字的比較

正確答案：A

20、為提高哈希（Hash）表的查找效率，可以采取的正確措施是（）。

I.增大裝填（載）因子

D,設(shè)計沖突（碰撞）少的哈希函數(shù)

m.處理沖突（碰撞）時避免產(chǎn)生堆積（