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

《南京工業(yè)大學 數(shù)據(jù)結(jié)構(gòu) 作業(yè)答案 作業(yè)6》由會員分享，可在線閱讀，更多相關(guān)《南京工業(yè)大學 數(shù)據(jù)結(jié)構(gòu) 作業(yè)答案 作業(yè)6（3頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、【精品文檔】如有侵權(quán)，請聯(lián)系網(wǎng)站刪除，僅供學習與交流 南京工業(yè)大學 數(shù)據(jù)結(jié)構(gòu) 作業(yè)答案 作業(yè)6 .....精品文檔...... 第六次作業(yè) 1. 假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進行折半查找，試回答下列問題： （1） 畫出描述折半查找過程的判定樹； （2） 若查找元素54，需依次與哪些元素比較？ （3） 若查找元素90，需依次與哪些元素比較？ （4） 假定每個元素的查找概率相等，求查找成功時的平均查找長度。 2. 設(shè)哈希（Hash）表的地址范圍為0～17，哈希函數(shù)為：H（K）＝K MOD 16。

2、 K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，試回答下列問題： （1） 畫出哈希表的示意圖； （2） 若查找關(guān)鍵字63，需要依次與哪些關(guā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è)此二叉樹以

3、二叉鏈表作存儲結(jié)構(gòu)。且樹中結(jié)點的關(guān)鍵字均不同。 1. 假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進行折半查找，試回答下列問題： （5） 畫出描述折半查找過程的判定樹； （6） 若查找元素54，需依次與哪些元素比較？ （7） 若查找元素90，需依次與哪些元素比較？ （8） 假定每個元素的查找概率相等，求查找成功時的平均查找長度。 解： （1） 先畫出判定樹如下（注：mid=?(1+12)/2?=6）： 30 5 63 3 7 42 87 4 24

4、 54 72 95 (2) 查找元素54，需依次與30, 63, 42, 54 等元素比較； (3) 查找元素90，需依次與30, 63,87, 95, 72等元素比較； （4） 求ASL之前，需要統(tǒng)計每個元素的查找次數(shù)。判定樹的前3層共查找1＋2×2＋4×3=17次； 但最后一層未滿，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈3.08 2. 設(shè)哈希（Hash）表的地址范圍為0～17，哈希函數(shù)為：H（K）＝K MOD 16。 K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列： （10，2

5、4，32，17，31，30，46，47，40，63，49） 造出Hash表，試回答下列問題： （5） 畫出哈希表的示意圖； （6） 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進行比較？ （7） 若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？ （8） 假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。 解： （1）畫表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 （2） 查找63,

6、首先要與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)容比較，但因為12號單元為空（應(yīng)當有空標記），所以應(yīng)當只比較這一次即可。 （4） 對于黑色數(shù)據(jù)元素，各比較1次；共6次； 對紅色元素則各不相同，要統(tǒng)計移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55 3. 在一棵空的二叉查找樹中依次插入關(guān)鍵

7、字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉查找樹。 答： 12 7 17 2 11 16 21 4 9 13 驗算方法： 用中序遍歷應(yīng)得到排序結(jié)果： 2,4,7,9,11,12,13,16,17，21 4. 試寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲結(jié)構(gòu)。且樹中結(jié)點的關(guān)鍵字均不同。 解：注意仔細研究二叉排序樹的定義。易犯的典型錯誤是按下述思路進行判別：“若一棵非空的

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