第7章 查找技術

1、第7章查找技術查找技術課后習題講解課后習題講解1.填空題⑴順序查找技術適合于存儲結(jié)構(gòu)為（）的線性表，而折半查找技術適用于存儲結(jié)構(gòu)為（）的線性表，并且表中的元素必須是（）?！窘獯稹宽樞虼鎯玩溄哟鎯?，順序存儲，按關鍵碼有序⑵設有一個已按各元素值排好序的線性表，長度為125，用折半查找與給定值相等的元素，若查找成功，則至少需要比較（）次，至多需比較（）次?！窘獯稹?，7【分析】在折半查找判定樹中，查找成功的情況下，和根結(jié)點的比較次數(shù)最少，為

2、1次，最多不超過判定樹的深度。⑶對于數(shù)列25，30，8，5，1，27，24，10，20，21，9，28，7，13，15，假定每個結(jié)點的查找概率相同，若用順序存儲結(jié)構(gòu)組織該數(shù)列，則查找一個數(shù)的平均比較次數(shù)為（）。若按二叉排序樹組織該數(shù)列，則查找一個數(shù)的平均比較次數(shù)為（）?！窘獯稹?，5915【分析】根據(jù)數(shù)列將二叉排序樹畫出，將二叉排序樹中查找每個結(jié)點的比較次數(shù)之和除以數(shù)列中的元素個數(shù)，即為二叉排序樹的平均查找長度。⑷長度為20的有序表采用

3、折半查找，共有（）個元素的查找長度為3?！窘獯稹?【分析】在折半查找判定樹中，第3層共有4個結(jié)點。⑸假定一個數(shù)列25，43，62，31，48，56，采用的散列函數(shù)為H(k)=kmod7，則元素48的同義詞是（）。【解答】62【分析】H(48)=H(62)=6⑹在散列技術中，處理沖突的兩種主要方法是（）和（）?！窘獯稹块_放定址法，拉鏈法⑺在各種查找方法中，平均查找長度與結(jié)點個數(shù)無關的查找方法是（）?！窘獯稹可⒘胁檎摇痉治觥可⒘斜淼钠骄檎?/p>

4、長度是裝填因子的函數(shù)，而不是記錄個數(shù)n的函數(shù)。探側(cè)法處理沖突，則元素49的存儲地址是（）。A8B3C5D9【解答】A【分析】元素15、38、61、84分別存儲在4、5、6、7單元，而元素49的散列地址為5，發(fā)生沖突，向后探測3個單元，其存儲地址為8。⑻在采用線性探測法處理沖突所構(gòu)成的閉散列表上進行查找，可能要探測多個位置，在查找成功的情況下，所探測的這些位置的鍵值（）。A一定都是同義詞B一定都不是同義詞C不一定都是同義詞D都相同【解答】

5、C【分析】采用線性探測法處理沖突會產(chǎn)生堆積，即非同義詞爭奪同一個后繼地址。3.判斷題⑴二叉排序樹的充要條件是任一結(jié)點的值均大于其左孩子的值，小于其右孩子的值?！窘獯稹垮e。分析二叉排序樹的定義，是左子樹上的所有結(jié)點的值都小于根結(jié)點的值，右子樹上的所有結(jié)點的值都大于根結(jié)點的值。例如圖77所示二叉樹滿足任一結(jié)點的值均大于其左孩子的值，小于其右孩子的值，但不是二叉排序樹。⑵二叉排序樹的查找和折半查找的時間性能相同?！窘獯稹垮e。二叉排序樹的查找性

6、能在最好情況和折半查找相同。⑶若二叉排序樹中關鍵碼互不相同，則其中最小元素和最大元素一定是葉子結(jié)點?！窘獯稹垮e。在二叉排序樹中，最小元素所在結(jié)點一定是中序遍歷序列中第一個被訪問的結(jié)點，即是二叉樹的最左下結(jié)點，但可能有右子樹。最大元素所在結(jié)點一定是中序遍歷序列中最后一個被訪問的結(jié)點，即是二叉樹的最右下結(jié)點，但可能有左子樹。如圖78所示，5是最小元素，25是最大元素，但5和25都不是葉子結(jié)點。⑷散列技術的查找效率主要取決于散列函數(shù)和處理沖突