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

上傳人:無(wú)*** 文檔編號(hào):100646320 上傳時(shí)間:2022-06-03 格式:DOC 頁(yè)數(shù):3 大小:128.50KB
收藏 版權(quán)申訴 舉報(bào) 下載
南京工業(yè)大學(xué) 數(shù)據(jù)結(jié)構(gòu) 作業(yè)答案 作業(yè)6_第1頁(yè)
第1頁(yè) / 共3頁(yè)
南京工業(yè)大學(xué) 數(shù)據(jù)結(jié)構(gòu) 作業(yè)答案 作業(yè)6_第2頁(yè)
第2頁(yè) / 共3頁(yè)
南京工業(yè)大學(xué) 數(shù)據(jù)結(jié)構(gòu) 作業(yè)答案 作業(yè)6_第3頁(yè)
第3頁(yè) / 共3頁(yè)

最后一頁(yè)預(yù)覽完了!喜歡就下載吧,查找使用更方便

10 積分

下載資源

資源描述:

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

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

2、 K為關(guān)鍵字,用線性探測(cè)法再散列法處理沖突,輸入關(guān)鍵字序列: (10,24,32,17,31,30,46,47,40,63,49) 造出Hash表,試回答下列問(wèn)題: (1) 畫出哈希表的示意圖; (2) 若查找關(guān)鍵字63,需要依次與哪些關(guān)鍵字進(jìn)行比較? (3) 若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較? (4) 假定每個(gè)關(guān)鍵字的查找概率相等,求查找成功時(shí)的平均查找長(zhǎng)度。 3. 在一棵空的二叉查找樹(shù)中依次插入關(guān)鍵字序列為12,7,17,11,16,2,13,9,21,4,請(qǐng)畫出所得到的二叉查找樹(shù)。 4. 試寫一個(gè)判別給定二叉樹(shù)是否為二叉排序樹(shù)的算法,設(shè)此二叉樹(shù)以

3、二叉鏈表作存儲(chǔ)結(jié)構(gòu)。且樹(shù)中結(jié)點(diǎn)的關(guān)鍵字均不同。 1. 假定對(duì)有序表:(3,4,5,7,24,30,42,54,63,72,87,95)進(jìn)行折半查找,試回答下列問(wèn)題: (5) 畫出描述折半查找過(guò)程的判定樹(shù); (6) 若查找元素54,需依次與哪些元素比較? (7) 若查找元素90,需依次與哪些元素比較? (8) 假定每個(gè)元素的查找概率相等,求查找成功時(shí)的平均查找長(zhǎng)度。 解: (1) 先畫出判定樹(shù)如下(注: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)計(jì)每個(gè)元素的查找次數(shù)。判定樹(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)鍵字,用線性探測(cè)法再散列法處理沖突,輸入關(guān)鍵字序列: (10,2

5、4,32,17,31,30,46,47,40,63,49) 造出Hash表,試回答下列問(wèn)題: (5) 畫出哈希表的示意圖; (6) 若查找關(guān)鍵字63,需要依次與哪些關(guān)鍵字進(jìn)行比較? (7) 若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較? (8) 假定每個(gè)關(guān)鍵字的查找概率相等,求查找成功時(shí)的平均查找長(zhǎng)度。 解: (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號(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ù)。“63”需要6次,“49”需要3次,“40”需要2次,“46”需要3次,“47”需要3次, 所以ASL=1/11(6+2+3×3)=17/11=1.5454545454≈1.55 3. 在一棵空的二叉查找樹(shù)中依次插入關(guān)鍵

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

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

展開(kāi)閱讀全文
溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!