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

【精品文檔】如有侵權(quán)，請聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流南京工業(yè)大學(xué) 數(shù)據(jù)結(jié)構(gòu) 作業(yè)答案 作業(yè)6.精品文檔.第六次作業(yè)1. 假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問題：（1） 畫出描述折半查找過程的判定樹；（2） 若查找元素54，需依次與哪些元素比較？（3） 若查找元素90，需依次與哪些元素比較？（4） 假定每個元素的查找概率相等，求查找成功時的平均查找長度。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表，試回答下列問題：（1） 畫出哈希表的示意圖；（2） 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？（3） 若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？（4） 假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。3. 在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉查找樹。4. 試寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲結(jié)構(gòu)。且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。1. 假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問題：（5） 畫出描述折半查找過程的判定樹；（6） 若查找元素54，需依次與哪些元素比較？（7） 若查找元素90，需依次與哪些元素比較？（8） 假定每個元素的查找概率相等，求查找成功時的平均查找長度。解：（1） 先畫出判定樹如下（注：mid=ë(1+12)/2û=6）：305 633 7 42 87 4 24 54 72 95(2) 查找元素54，需依次與30, 63, 42, 54 等元素比較；(3) 查找元素90，需依次與30, 63,87, 95, 72等元素比較；（4） 求ASL之前，需要統(tǒng)計(jì)每個元素的查找次數(shù)。判定樹的前3層共查找12×24×3=17次；但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL1/12（1720）37/123.082. 設(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） 假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。解： （1）畫表如下：012345678910111213141516173217634924401030314647（2） 查找63,首先要與H(63)=63%16=15號單元內(nèi)容比較，即63 vs 31 ,no;然后順移，與46,47,32,17,63相比，一共比較了6次！（3）查找60,首先要與H(60)=60%16=12號單元內(nèi)容比較，但因?yàn)?2號單元為空（應(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（623×3）17/11=1.54545454541.553. 在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉查找樹。答： 127 17 2 11 16 21 4 9 13驗(yàn)算方法： 用中序遍歷應(yīng)得到排序結(jié)果： 2,4,7,9,11,12,13,16,17，214. 試寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲結(jié)構(gòu)。且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。解：注意仔細(xì)研究二叉排序樹的定義。易犯的典型錯誤是按下述思路進(jìn)行判別：“若一棵非空的二叉樹其左、右子樹均為二叉排序樹，且左子樹的根的值小于根結(jié)點(diǎn)的值，又根結(jié)點(diǎn)的值不大于右子樹的根的值，則是二叉排序樹”（即不能只判斷左右孩子的情況，還要判斷左右孩子與雙親甚至根結(jié)點(diǎn)的比值也要遵循（左小右大）原則）。若要采用遞歸算法，建議您采用如下的函數(shù)首部：bool BisortTree(BiTree T, BiTree&PRE)，其中PRE為指向當(dāng)前訪問結(jié)點(diǎn)的前驅(qū)的指針。（或者直接存儲前驅(qū)的數(shù)值，隨時與當(dāng)前根結(jié)點(diǎn)比較）一個漂亮的算法設(shè)計(jì)如下：int last=0, flag=1; / last是全局變量，用來記錄前驅(qū)結(jié)點(diǎn)值，只要每個結(jié)點(diǎn)都比前驅(qū)大就行。int Is_BSTree(Bitree T) /判斷二叉樹T是否二叉排序樹，是則返回1，否則返回0 if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->data<last) flag=0; /與其中序前驅(qū)相比較, flag=0表示當(dāng)前結(jié)點(diǎn)比直接前驅(qū)小，則立即返回 last=T->data; if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; /Is_BSTree