數(shù)據(jù)結(jié)構(gòu)第九章查找習(xí)題解答

1、第九章查找 習(xí)題解答9.5 畫出對長度為10的有序表進行折半查找的判定樹，并求其等概率時查找成功的平均查找長度。解：求得的判定樹如下：asl成功=（1+2*2+4*3+3*4）/10 =2.99.9 已知如下所示長度為12的表（jan,feb,mar,apr,may,june,july,aug,sep,oct,nov,dec）(1)試按表中元素的順序依次插入一查初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。(2)若對表中元素先進行排序構(gòu)成有序表，求在等概率的情況下對此有序表進行折半查找時查找成功的平均查找長度。解：（1）求得的二叉排序樹如下圖

2、所示： 在等概率情況下查找成功的平均查找長度為：asl成功=（1+2*2+3*3+4*3+5*2+6*1）/12=42/12=3.5 (2)分析：對表中元素進行排序后，其實就變成了對長度為12的有序表進行折半查找了，那么在等概率的情況下的平均查找長度只要根據(jù)折半查找的判定樹就很容易求出。長度為12的有序表進行折半查找的判定樹如下圖所示：所以可求出：asl成功=（1+2*2+4*3+5*4）/12=37/129.19 選取哈希函數(shù)h(k)=(3k) mod 11。用開放定址法處理沖突，di=i(7k)mod 10 +1)(i=1,2,3,)。試在010的散列地址空間中對關(guān)鍵字序列（22，41，5

3、3，46，30，13，01，67）造哈希表，并求等概率情況下查找成功時的平均查找長度。解：因為h(22)=0；h(41)=2；h(53)=5；h(46)=6；h(30)=2；h1(30)=3；h(13)=6；h1(13)=8；h(01)=3；h1(01)=0；h2(01)=8；h3(01)=5；h4（01）=2；h5(01)=10h(67)=3；h1(67)=2；h2(67)=1所以：構(gòu)造的哈希表如下圖所示： 0 1 2 3 4 5 6 7 8 9 102267413053461301 ci：1 3 1 2 1 1 2 6并求得等概率情況下查找成功的平均查找長度為： asl成功=（1*4+2*

4、2+3+6）/8=17/89.21 在地址空間為016的散列區(qū)中，對以下關(guān)鍵字序列構(gòu)造兩哈希表：（jan,feb,mar,apr,may,june,july,aug,sep,oct,nov,dec）(1)用線性探測開放定址法處理沖突；(2)用鏈地址法處理。并分別求這兩個哈希表在等概率情況下查找成功和不成功時的平均查找長度。設(shè)哈希函數(shù)為h(x)=i/2取整,其中i為關(guān)鍵字中第一個字母在字母表中的序號。解：（1）因為：h(jan)=5;h(feb)=3;h(mar)=6;h(apr)=0;h(may)=6; h1(may)=7;h(june)=5;h1(june)=6;h2(june)=7;h3(

5、june)=8h(july)=5;h1(july)=6;h2(july)=7;h3(july)=8;h4(july)=9;h(aug)=0; h1(aug)=1h(sep)=9; h1(sep)=10h(oct)=7; h1(oct)=8;h2(oct)=9; h3(oct)=10; h4(oct)=11;h(nov)=7; h1(nov)=8;h2(nov)=9; h3(nov)=10; h4(nov)=11;h5(nov)=12;h(dec)=2 所以，用線性探測開放定址法處理沖突構(gòu)造的哈希表如下圖所示：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16apr

6、augdecfeb janmarmayjunejulysepoctnovci:1 2 1 1 1 1 2 4 5 2 5 6 并求得：asl成功=（1*5+2*3+4+5*2+6）/12=31/12 asl不成功=（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14=60/140 12345678910111213141516aug apr （2）用鏈地址法處理沖突構(gòu)造的哈希表如下圖所示：dec feb june july jan may marnov oct sep 并求得：asl成功=（1*7+2*4+3）/12=18/12asl不成功=（1*3+2*3+3）14=12/149

7、.25 假設(shè)順序表按關(guān)鍵字自大至小有序，試改寫教科書9.1.1節(jié)中的順序查找算法，將監(jiān)視哨設(shè)在高下標(biāo)端。然后畫出描述此查找過程的判定樹，分別求出等概率下查找成功和不成功的平均查找長度。解：（1）順序表的存儲結(jié)構(gòu)描述： typedef struct keytype key; elemtype; /記錄類型；typedef struct elemtype *elem; int length; sstable; /順序表類型；按要求所得算法如下： int search(sstable st, keytype key) st.elemst.length.key=key; for (i=0; key&l

8、t;st.elemi.key; i+); if (i=st.length) return 0; else if (key=st.elemi.key) return i; else return 0; (2)按此查找過程的判定樹如下圖所示：（3）等概率下的查找成功與查找不成功的平均查找長度分別為：、 asl成功=（1+2+3+.+n）/n=(n+1)/2 als不成功=（1+2+3+n）/(n+1)=(n+2)/2補充：設(shè)散列表的長度為13，散列函數(shù)為h(k）=k%13，給定的關(guān)鍵字序列為: 19，14，23，01，68，20，84，27，55，11，10，79。試畫出分別用拉鏈法和線性探查法解

9、決沖突時所構(gòu)造的散列表，并求出在等概率情況下，求這兩種方法的查找成功和查找不成功的平均查找長度。解：（1）用拉鏈法處理沖突：因為：h(19)=6；h(14)=1;h(23)=10;h(01)=1;h(68)=3;h(20)=7;h(84)=6;h(27)=1;h(55)=3;h(11)=11;h(10)=10;h(79)=1所以，構(gòu)造的哈希表如下圖所示：0 1234567891011122701 14 79 68 5584 1920 23 10 11 并求得：asl成功=（1*6+2*4+3+4）/12=21/12 asl不成功=（4+2*3+1*2）/13=12/13 （2）用線性探測再散列

10、法處理沖突：因為：h(19)=6；h(14)=1;h(23)=10;h(01)=1; h1(01)=2;h(68)=3;h(20)=7;h(84)=6; h1(84)=7; h2(84)=8;h(27)=1;h1(27)=2; h2(27)=3; h3(27)=4;h(55)=3; h1(55)=4; h2(55)=5;h(11)=11;h(10)=10; h1(10)=11; h2(10)=12;h(79)=1; h1(79)=2; h2(79)=3; h3(79)=4; h4(79)=5; h5(79)=6; h6(79)=7; h7(79)=8;h8(79)=9所以，構(gòu)造的哈希表如下圖所示：