數(shù)據(jù)結(jié)構(查找)練習題與答案

1、1、靜態(tài)查找表和動態(tài)查找表的區(qū)別是（）。A.所包含的數(shù)據(jù)元素的類型不同B.施加其上的操作不同C.它們的邏輯結(jié)構相同D.以上都不對正確答案：B解析：B、若在查找的同時對表做修改操作（如插入和刪除），則相應的查找表稱之為動態(tài)查找表。若在查找中不涉及表的修改操作，則相應的查找表稱之為靜態(tài)查找表。2、順序查找法適合于存儲結(jié)構為（）的線性表。A.索引存儲B.壓縮存儲加11順序存儲或鏈式存儲D.哈希存儲正確答案：C解析：匚“順序查找可以從前向后或從后向前依次查找，既適合于“順序存儲結(jié)構也適合于鏈式存儲結(jié)構。3、采用“順序查找方法查找長度為n的”頁序表時，在等概率時成功查找的平均查找長度為（）。A.（n-1

2、）/2B.nC.n/2D.（n+1）/2正確答案：D解析：）|順序查找時，元素ai需i次比較，成功查找的平均查找長度=（1+2+.+n）/n=（n+1）/2。4、采用“順序查找方法查找長度為n的”頁序表時，在等概率時不成功查找的平均查找長度為（）。A.(n-1)/2B.nC.n/2D.(n+1)/2正確答案：B解析：B、當查找的元素不在線性表中時，均需要n次元素之間的比較。5、適合于折半查找的數(shù)據(jù)組織方式是()。A.以鏈表存儲的有序線性表B.以順序表存儲的有序線性表C.以鏈表存儲的線性表D.以順序表存儲的線性表正確答案：B解析：B、折半查找的數(shù)據(jù)必須是有序的。另外，折半查找中需要確定查找區(qū)間，

3、這要求存儲結(jié)構最好具有隨機存取特性，而順序表滿足這個特性。6、采用折半查找方法查找長度為n的線性表，當n很大時，在等概率時不成功查找的平均查找長度為()。O(nlog2n)O(n2)O(n)O(log2n)正確答案：D解析：采用折半查找時，若n很大，對應的判定樹可以看成是一棵滿二叉樹，失敗節(jié)點(外部節(jié)點)集中在最下一層，落在每個失敗節(jié)點時比較的次都均為10g2n。7、設有100個元素的有序表，采用折半查找方法，在等概率時成功時最大的比較次數(shù)是()。A.50B.25C.10D.7正確答案：D解析：成功時最大比較次數(shù)為10g2(n+1)(取上界)=log2(101)(取上界)=7。8、已知一個長度

4、為16的順序表，其元素按關鍵字有序排序，若采用折半查找法查找一個存在的元素，則比較的次數(shù)最多是()。A.6B.5C.4D.7正確答案：B解析：B、n=16，采用折半查找法查找一個存在的元素，即為成功查找。成功查找的最多比較次數(shù)=1嗎(n+1)(取上界)=1og2a7)(取上界)=5。9、一個遞增有序表為R0.11，采用折半查找方法進行查找，在一次不成功查找中，以下()是不可能的記錄比較序列。A.R5、R8、R6、R7B.R5、R8、R10C.R5、R2、R3D.R5、R8、R6正確答案：B解析：B、畫出遞增有序表咫0.11采用折半查找對應的判定樹，一次失敗的查找必須到達某個外部節(jié)點，而R5、R

5、8、R10序列沒有到達任何外部節(jié)點。10、對有3600個記錄的索引順序表(分塊表)進行分塊查找，最理想的塊長是()Alog23600B.1800C.60D.1200正確答案：C解析：C、n=3600，分塊查找最理想的塊長=sqrt（n）=sqrt（3600）=60。11、二叉排序中，按（）遍歷二叉排序得到的序列是一個有序序列。A后序B.先序C.中序D.層次正確答案：C解析：C、二叉排序的中序遍歷序列恰好是一個遞增有序序列。12、在含有27個節(jié)點的二叉排序樹上，查找關鍵字為35的節(jié)點，則依次比較的關鍵字有可能是（）。A.46，36，18，28，35B.18，36，28，46，35C.28，36，

6、18，46，35D.46，28，18，36，35正確答案：A解析：A、畫出各選項對應的查找樹，從中看到只有選項D對應的查找樹構成一棵二叉排序樹，可以作為一棵二叉排序樹的一部分，其他查找樹均不構成一棵二叉排序樹。13、以下關于二叉排序樹的敘述中正確的是（）。A.二叉排序樹是動態(tài)樹表，在插入新節(jié)點時會引起樹的重新分裂和合并B.在二叉排序樹中進行查找，關鍵字的比較次數(shù)不超過節(jié)點數(shù)的一半C.對二叉排序樹進行層次遍歷可以得到一個有序序列D.在構造二叉排序樹時，若關鍵字序列有序，則二叉排序樹的高度最大正確答案：D14、有一棵含有8個節(jié)點的二叉排序樹，其節(jié)點值為AH,以下（）是其后序遍歷A.BCAGEHFD

7、B.BDACEFHGC.BCAEFDHGD.ADBCEGFH正確答案：C解析：C、該二叉排序樹的中序序列為ABCDEFGH，后序序列應是AH的出棧序列，其中選項A、B和D都不是合法的出棧序列，只有選項C是合法的出棧序列。15、具有5層節(jié)點的AVL樹至少有（）個節(jié)點。A.10B.17C.15D.12正確答案：D解析：D、設Nh表示高度為h的平衡二叉樹中含有的最少節(jié)點數(shù)，有：N1=1，N2=2，Nh=Nh-1+Nh-2+1由此，求出N5=12。16、以下關于m階B-樹的敘述中正確的是（）。A.樹中每個節(jié)點至多有m/2-1個關鍵字B.所有葉子節(jié)點均在同一層上C.當插入一個關鍵字引起B(yǎng)-樹節(jié)點分裂時，

8、樹增高一層D.每個節(jié)點至少有兩棵非空子樹正確答案：B解析：B、選項A錯誤，因為m階B-樹可能只有一個根節(jié)點。選項B錯誤，在m階B-樹中，除根節(jié)點外，每個節(jié)點至少有m/2（取上界）-1個關鍵字。選項D錯誤，當插入一個關鍵字引起B(yǎng)-樹節(jié)點分裂時，樹不一定會增高一層，只有節(jié)點分裂延續(xù)到根節(jié)點，根節(jié)點也分裂后，樹才會增高一層。17、在一棵m階B-樹中刪除一個關鍵字會引起合并，則該節(jié)點原有（）個關鍵字。AJm/2BJm/2-1C.1DJm/2+1正確答案：B解析：B、引起合并的節(jié)點應為關鍵字個數(shù)的下限。18、以下關于哈希查找的敘述中錯誤的是（）。A.哈希函數(shù)選得好可以減少沖突現(xiàn)象B.哈希函數(shù)H（k）=kMODp，p通常取小于等于表長的素數(shù)C.用拉鏈法解決沖突易引起堆積現(xiàn)象D.用線性探測法解決沖突易引起堆積現(xiàn)象正確答案：C解析：C、用拉鏈法解決沖突時不存在堆積現(xiàn)象，只有用線性探測法解決沖突時易引起堆積現(xiàn)象。19、以下關于哈希查找的敘述中正確的是（）。A.哈希表的裝填因子等于表中填入的記錄數(shù)除以哈希表的長度8.采用拉鏈法解決沖突時，查找一個元素的時間是相同的C.哈希表在查找成功時的平均查找長度僅僅與表長有關D.哈希查找中不需要任何關鍵字的比較正確答案：A20、為提高哈希（Hash）表的查找效率，可以采取的正確措施是（）。工.增大裝填（載）因子口.設