習(xí)題一、名詞解釋 (1)主關(guān)鍵字 (2)平均查找長度 (3)靜態(tài)查找表 (4)動態(tài)查找表 (5)二叉查找樹 (6)哈希表二、填空題 (1)靜態(tài)查找表的存儲結(jié)構(gòu)主要采用順序存儲結(jié)構(gòu)，如果需要，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)， 但當(dāng)使用二分(折半)查找算法或(斐波那契數(shù)列)查找算法來查找時，要求查找表 只能是順序存儲結(jié)構(gòu)，并且查找表中的數(shù)據(jù)序列必須有序。 (2)通過中根序遍歷一棵二叉查找樹得到的數(shù)據(jù)序列必然是一個非降序(有序)序 (3)各種查找方法中，平均查找長度與結(jié)點(diǎn)個數(shù)n無關(guān)的查找方法是哈希查找。 *(4)如果對一個有序查找表SST進(jìn)行折半查找，在最壞時要比較10次，那么對該查找表 進(jìn)行順序查找時，在最壞時要比較210-1次。 解析：最壞情況要比較10次，說明樹的高度是10。而一棵深度為10的二叉樹，最多*(5)深度為7的平衡二叉樹至少有33個結(jié)點(diǎn)。解析：在節(jié)點(diǎn)最少的情況下，左右子樹的高度差為1，則總節(jié)點(diǎn)數(shù)S(n)=S(n-1)+S(n-2)+1。已知，初始值S(1)=1，S(2)=2，所以，高度為7的平制衡二百叉樹最少結(jié)點(diǎn)數(shù)是33。三、簡答題 (1)請畫出長度為8的有序查找表的折半查找判定樹。 (2)折半查找的前提：順序存儲、查找表有序。 (3)已知關(guān)鍵字序列為{45，28，67，33，29，50}，二叉排序樹初始為空，要求：①畫出按正向(從關(guān)鍵字45開始)順序插入結(jié)點(diǎn)建立的二叉排序樹。②畫出按反向(從關(guān)鍵字50開始)順序插入結(jié)點(diǎn)建立的二叉排序樹。 (4)二叉排序樹的平均查找長度：與結(jié)點(diǎn)個數(shù)和樹的形態(tài)有關(guān)。 (5)設(shè)哈希表的地址空間為0~6，哈希函數(shù)H(key)=key%7。請對關(guān)鍵字序列{32，13，成功 (6)設(shè)哈希表的地址空間為0~12，哈希函數(shù)H(key)=key%11。請對關(guān)鍵字序列{30，15，49，61，22，50，23，41，18}按二次探測再哈希法解決沖突的辦法構(gòu)造哈希表。并求出在等概并查找成功時的平均查找長度。關(guān)于關(guān)鍵字18的說明：H(18)=18%11=7,沖突；H1=(H(key)+d1)%m=(7+1)%13=8，沖突；H2=(H(key)+d1)%m=(7-1)%13=6，沖突；號存儲單元中。備注：公式Hi=(H(key)+di)%m詳見課本第164頁，其中m是表長。 (7)設(shè)哈希表的地址空間為0~12，哈希函數(shù)H(key)=key%11。請對關(guān)鍵字序列{30，