《南京工業(yè)大學(xué) 數(shù)據(jù)結(jié)構(gòu) 作業(yè)答案 作業(yè)6》由會(huì)員分享,可在線閱讀,更多相關(guān)《南京工業(yè)大學(xué) 數(shù)據(jù)結(jié)構(gòu) 作業(yè)答案 作業(yè)6(3頁珍藏版)》請(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)行折半查找,試回答下列問題:
(1) 畫出描述折半查找過程的判定樹;
(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表,試回答下列問題:
(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è)此二叉樹以
3、二叉鏈表作存儲(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) 畫出描述折半查找過程的判定樹;
(6) 若查找元素54,需依次與哪些元素比較?
(7) 若查找元素90,需依次與哪些元素比較?
(8) 假定每個(gè)元素的查找概率相等,求查找成功時(shí)的平均查找長(zhǎng)度。
解:
(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)計(jì)每個(gè)元素的查找次數(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表,試回答下列問題:
(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ù)?!?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,請(qǐng)畫出所得到的二叉查找樹。
答:
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è)此二叉樹以二叉鏈表作存儲(chǔ)結(jié)構(gòu)。且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。
解:注意仔細(xì)研究二叉排序樹的定義。易犯的典型錯(cuò)誤是按下述思路進(jìn)行判別:“若一棵非空的
8、二叉樹其左、右子樹均為二叉排序樹,且左子樹的根的值小于根結(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,否則返回0
if(T->lchild&&flag) Is_BSTree(T->lchild);
if(T->datadata;
if(T->rchild&&flag) Is_BSTree(T->rchild);
return flag;
}//Is_BSTree