南京工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)作業(yè)答案作業(yè)6

1、第六次作業(yè)1. 假定對有序表：(3, 4, 5, 7, 24, 30, 42, 54, 63, 72, 87, 95)進(jìn)行折半查找, 試回答下列問題：(1) 畫出描述折半查找過程的判定樹；(2) 若查找元素54,需依次與哪些元素比較(3) 若查找元素90,需依次與哪些元素比較(4) 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長度。2. 設(shè)哈希(Hash)表的地址范圍為 017,哈希函數(shù)為：H ( K)= K MOD 16。 K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列：(10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49)造出Hash表，試

2、回答下列問題：(1) 畫出哈希表的示意圖；(2) 若查找關(guān)鍵字63,需要依次與哪些關(guān)鍵字進(jìn)行比較(3) 若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較(4) 假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長度。3. 在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為12, 7, 17, 11, 16, 2, 13, 9,21, 4,請畫出所得到的二叉查找樹。4試寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲 結(jié)構(gòu)。且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。1. 假定對有序表：(3, 4, 5, 7, 24, 30, 42, 54, 63, 72, 87, 95)進(jìn)行折半查找,試回答下列問題：

3、(5) 畫出描述折半查找過程的判定樹；(6) 若查找元素54,需依次與哪些元素比較(7) 若查找元素90,需依次與哪些元素比較(8) 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長度。解：(1) 先畫出判定樹如下(注： mid= (1+12)/2=6)3056374(2) 查找元素 54,需依次與 30, 63, 42, 54 等元素比較；(3) 查找元素 90,需依次與 30, 63,87, 95, 72 等元素比較;(4) 求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹的前3層共查找1 + 2 X 2+ 4 X 3=17 次；但最后一層未滿，不能用8X 4,只能用5 X 4=20次

4、,所以 ASL= 1/12 (17+ 20)= 37/12 2. 設(shè)哈希（Hash）表的地址范圍為 017,哈希函數(shù)為：H （K）= K MOD 16 。K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列：（10， 24， 32， 17， 31， 30， 46， 47， 40， 63， 49）造出Hash表，試回答下列問題：（5）畫出哈希表的示意圖；（6）若查找關(guān)鍵字63,需要依次與哪些關(guān)鍵字進(jìn)行比較（7）若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較（8）假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長度。012345678901112131415161731642413342739

5、4000167解：（1）畫表如下：4（2） 查找63,首先要與 H（63）=63%16=15號單元內(nèi)容比較，即 63 vs 31 ,no;13#然后順移，與46,47,32,17,63 相比，一共比較了 6次！（3）查找60,首先要與 H（60）=60%16=12號單元內(nèi)容比較，但因?yàn)?12號單元為空（應(yīng) 當(dāng)有空標(biāo)記），所以應(yīng)當(dāng)只比較這一次即可。（4）對于黑色數(shù)據(jù)元素，各比較 1次；共6次；對紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40'需要2次，“ 46”需要3次，“ 47 ”需要3次，所以 ASL=1/11 （6+ 2+ 3 X 3）= 17/1

6、1= 12， 7， 17， 11， 16， 2， 13， 9，3. 在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為 21，4,請畫出所得到的二叉查找樹。答：12721/17/2 11 16 /4 913驗(yàn)算方法：用中序遍歷應(yīng)得到排序結(jié)果：2,4,7,9,11,12,13,16,17，214試寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲 結(jié)構(gòu)。且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。解：注意仔細(xì)研究二叉排序樹的定義。易犯的典型錯(cuò)誤是按下述思路進(jìn)行判別：“若棵非空的二叉樹其左、右子樹均為二叉排序樹，且左子樹的根的值小于根結(jié)點(diǎn)的值，又根 結(jié)點(diǎn)的值不大于右子樹的根的值，則是二叉排序樹”（即不能

7、只判斷左右孩子的情況，還要判斷左右孩子與雙親甚至根結(jié)點(diǎn)的比值也要遵循（左小右大）原則）。若要采用遞歸算法，建議您采用如下的函數(shù)首部：bool BisortTree(BiTree T, BiTree&PRE)，其中PRE為指向當(dāng)前訪問結(jié)點(diǎn)的前驅(qū)的指針。(或者直接存儲前驅(qū)的數(shù)值，隨時(shí)與當(dāng)前根結(jié)點(diǎn)比較) 一個(gè)漂亮的算法設(shè)計(jì)如下：int last=0 , flag=1 ;/ last 是全局變量， 用來記錄前驅(qū)結(jié)點(diǎn)值，只要每個(gè)結(jié)點(diǎn)都比前驅(qū)大就行。int ls_BSTree(Bitree T) /判斷二叉樹 T是否二叉排序樹，是則返回1,否則返回 0if(T->lchild&&flag) ls_BSTree(T->lchild);if(T->data<last) flag=0;/ 與其中序前驅(qū)相比較 , flag=