第7章查找技術(shù)

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

2、25，43，62，31，48，56，采用的散列函數(shù)為H(k)=k mod 7，則元素48的同義詞是（ ）。【解答】62【分析】H(48)= H(62)=6(5) 在散列技術(shù)中，處理沖突的兩種主要方法是（ ）和（ ）?！窘獯稹块_(kāi)放定址法，拉鏈法2. 選擇題 靜態(tài)查找與動(dòng)態(tài)查找的根本區(qū)別在于（ ）。A 它們的邏輯結(jié)構(gòu)不一樣 B 施加在其上的操作不同C 所包含的數(shù)據(jù)元素的類型不一樣 D 存儲(chǔ)實(shí)現(xiàn)不一樣【解答】B【分析】靜態(tài)查找不涉及插入和刪除操作，而動(dòng)態(tài)查找涉及插入和刪除操作。 二叉排序樹(shù)中，最小值結(jié)點(diǎn)的（ ）。A 左指針一定為空 B 右指針一定為空C 左、右指針均為空 D 左、右指針均不為空【解答

3、】A【分析】在二叉排序樹(shù)中，值最小的結(jié)點(diǎn)一定是中序遍歷序列中第一個(gè)被訪問(wèn)的結(jié)點(diǎn)，即二叉樹(shù)的最左下結(jié)點(diǎn)。(3)散列技術(shù)中的沖突指的是（ ）。A 兩個(gè)元素具有相同的序號(hào) B 兩個(gè)元素的鍵值不同，而其他屬性相同C 數(shù)據(jù)元素過(guò)多 D 不同鍵值的元素對(duì)應(yīng)于相同的存儲(chǔ)地址【解答】D(4) 設(shè)散列表表長(zhǎng)m=14，散列函數(shù)H(k)=k mod 11。表中已有15、38、61、84四個(gè)元素，如果用線性探側(cè)法處理沖突，則元素49的存儲(chǔ)地址是（ ）。A 8 B 3 C 5 D 9 【解答】A【分析】元素15、38、61、84分別存儲(chǔ)在4、5、6、7單元，而元素49的散列地址為5，發(fā)生沖突，向后探測(cè)3個(gè)單元，其存儲(chǔ)地

4、址為8。3. 判斷題 二叉排序樹(shù)的充要條件是任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值?！窘獯稹垮e(cuò)。分析二叉排序樹(shù)的定義，是左子樹(shù)上的所有結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值，右子樹(shù)上的所有結(jié)點(diǎn)的值都大于根結(jié)點(diǎn)的值。例如圖7-7所示二叉樹(shù)滿足任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值，但不是二叉排序樹(shù)。 二叉排序樹(shù)的查找和折半查找的時(shí)間性能相同。【解答】錯(cuò)。二叉排序樹(shù)的查找性能在最好情況和折半查找相同。 若二叉排序樹(shù)中關(guān)鍵碼互不相同，則其中最小元素和最大元素一定是葉子結(jié)點(diǎn)?！窘獯稹垮e(cuò)。在二叉排序樹(shù)中，最小元素所在結(jié)點(diǎn)一定是中序遍歷序列中第一個(gè)被訪問(wèn)的結(jié)點(diǎn)，即是二叉樹(shù)的最左下結(jié)點(diǎn)，但可能有右子樹(shù)

5、。最大元素所在結(jié)點(diǎn)一定是中序遍歷序列中最后一個(gè)被訪問(wèn)的結(jié)點(diǎn)，即是二叉樹(shù)的最右下結(jié)點(diǎn)，但可能有左子樹(shù)。如圖7-8所示，5是最小元素，25是最大元素，但5和25都不是葉子結(jié)點(diǎn)。 散列技術(shù)的查找效率主要取決于散列函數(shù)和處理沖突的方法?！窘獯稹垮e(cuò)。更重要的取決于裝填因子，散列表的平均查找長(zhǎng)度是裝填因子的函數(shù)。 當(dāng)裝填因子小于1時(shí)，向散列表中存儲(chǔ)元素時(shí)不會(huì)引起沖突。【解答】錯(cuò)。裝填因子越小，只能說(shuō)明發(fā)生沖突的可能性越小。4分別畫出在線性表（a，b，c，d，e，f，g）中進(jìn)行折半查找關(guān)鍵碼e和g的過(guò)程。【解答】查找關(guān)鍵碼e的過(guò)程如圖7-9所示，查找關(guān)鍵碼g的過(guò)程如圖7-10所示。5將數(shù)列（24，15，38，27，121，76，130）的各元素依次插入一棵初始為空的二叉排序樹(shù)中，請(qǐng)畫出最后的結(jié)果并求等概率情況下查找成功的平均查找長(zhǎng)度。【解答】二叉排序樹(shù)如圖7-11所示，其平均查找長(zhǎng)度=1+22+32+42=19/76已知散列函數(shù)H(k)=k mod 12，鍵值序列為(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82)，采用拉鏈法處理沖突，試構(gòu)造開(kāi)散列表，并計(jì)算查找成功的平均查找長(zhǎng)度?！窘獯稹縃(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3