第7章 查找技術(shù)

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

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

3、折半查找，共有（）個(gè)元素的查找長(zhǎng)度為3。【解答】4【分析】在折半查找判定樹中，第3層共有4個(gè)結(jié)點(diǎn)。⑸假定一個(gè)數(shù)列25，43，62，31，48，56，采用的散列函數(shù)為H(k)=kmod7，則元素48的同義詞是（）?！窘獯稹?2【分析】H(48)=H(62)=6⑹在散列技術(shù)中，處理沖突的兩種主要方法是（）和（）。【解答】開放定址法，拉鏈法⑺在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)的查找方法是（）。【解答】散列查找【分析】散列表的平均查找

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

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

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