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

1、第六次作業(yè)1. 假定對(duì)有序表：(3，4，5，7，24， 30，42，54，63，72，87，95)進(jìn)行折半查找，試 回答下列問題：(1) 畫出描述折半查找過程的判定樹；(2) 若查找元素 54，需依次與哪些元素比較？(3) 若查找元素 90，需依次與哪些元素比較？( 4) 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。2. 設(shè)哈希(Hash)表的地址范圍為017,哈希函數(shù)為：H( K)= K MOD 16。K 為關(guān)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(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í)的平均查找長(zhǎng)度。3. 在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為 12， 7， 17， 11， 16， 2， 13， 9， 21，4, 請(qǐng)畫出所得到的二叉查找樹。4.試寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲(chǔ)結(jié)構(gòu)。且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。1. 假定對(duì)有序表：（3,4,5, 7，24，30，42,54，63,72,87,95）進(jìn)行折半查找，試回答下列問題：（5）畫出描

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

4、 (17+ 20)= 37/12 3.082. 設(shè)哈希(Hash)表的地址范圍為017,哈希函數(shù)為：H( K)= K MOD 16。K為關(guān)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(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í)的平均查找長(zhǎng)度。解：(1)畫表如下：01234567891011121314151617321763492440103031

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

6、入關(guān)鍵字序列為12，7，17，11，16，2，13, 9, 21,4, 請(qǐng)畫出所得到的二叉查找樹。答：12 / / 7、 / /7172 11 16 2113驗(yàn)算方法： 用中序遍歷應(yīng)得到排序結(jié)果： 2,4,7,9,11,12,13,16,17，214. 試寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲(chǔ)結(jié)構(gòu)。且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。解：注意仔細(xì)研究二叉排序樹的定義。 易犯的典型錯(cuò)誤是按下述思路進(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ū)的指針。（或者直接存儲(chǔ)前驅(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 Is_BSTree（Bitree T） /判斷二叉樹 T 是否二叉排序樹，是則返回 1，否則返回0if(T-lchild&