數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版清華大學(xué)出版社)-章課后部分答案.doc

《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版清華大學(xué)出版社)-章課后部分答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版清華大學(xué)出版社)-章課后部分答案.doc（5頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第八章 選擇題 1. C 2.A 3.B 4.C 5.D 6.B 7.B 8.A 9.D 10.D 11.C 12.C 填空題 1. n、n+1 2. 4 3. 8.25( 折半查找所在塊 ) 4. 左子樹(shù)、右子樹(shù) 5. 26 6. 順序、(n+1)/2、O(log2n) 7. m-1、[m/2]-1 8. 直接定址 應(yīng)用題 1. 進(jìn)行折半查找時(shí)，判定樹(shù)是唯一的，折半查找過(guò)程是走了一條從根節(jié)點(diǎn)到末端節(jié)點(diǎn)的路徑，所以其最大查找長(zhǎng)度為判定樹(shù)深度[log2n]+1.其平均查找長(zhǎng)度約為[log2n+1]-1.在二叉排序樹(shù)上查找時(shí)，其最大查找長(zhǎng)度也是與二叉樹(shù)的深度相關(guān)，但是含有n個(gè)節(jié)點(diǎn)的二叉排序樹(shù)不是唯一的，當(dāng)對(duì)n個(gè)元素的有序序列構(gòu)造一棵二叉排序樹(shù)時(shí)，得到的二叉排序樹(shù)的深度也為n，在該二叉樹(shù)上查找就演變成順序查找，此時(shí)的最大查找長(zhǎng)度為n；在隨機(jī)情況下二叉排序樹(shù)的平均查找長(zhǎng)度為1+4log2n。 因此就查找效率而言，二分查找的效率優(yōu)于二叉排序樹(shù)查找，但是二叉排序樹(shù)便于插入和刪除，在該方面性能更優(yōu)。 3. 評(píng)價(jià)哈希函數(shù)優(yōu)劣的因素有：能否將關(guān)鍵字均勻的映射到哈希表中，有無(wú)好的處理沖突的方法，哈希函數(shù)的計(jì)算是否簡(jiǎn)單等。 沖突的概念：若兩個(gè)不同的關(guān)鍵字Ki和Kj，其對(duì)應(yīng)的哈希地址Hash(Ki) = Hash(Kj)，則稱為地址沖突，稱Ki和K,j為同義詞。 （1） 開(kāi)放定址法 （2） 重哈希法 （3） 鏈接地址法 4. （1）構(gòu)造的二叉排序樹(shù)，如圖 （2）中序遍歷結(jié)果如下： 10 12 15 20 24 28 30 35 46 50 55 68 （4） 平均查找長(zhǎng)度如下： ASLsucc = （1x1+2x2+3x3+4x3+5x3）/12 = 41/12 8. 哈希地址如下： H(35) = 35%11 = 2 H(67) = 67%11 = 1 H(42) = 42%11 = 9 H(21) = 21%11 = 10 H(29) = 29%11 = 7 H(86) = 86%11 = 9 H(95) = 95%11 = 7 H(47) = 47%11 = 3 H(50) = 50%11 = 6 H(36) = 36%11 = 3 H(91) = 91%11 = 3 第九章 選擇題 1. D 2.C 3.B 4.D 5.C 6.B 7.A 8.A 9.D 10.D 填空題 1. 插入排序、交換排序、選擇排序、歸并排序 2. 移動(dòng)（或者交換） 3. 歸并排序、快速排序、堆排序 4. 保存當(dāng)前要插入的記錄，可以省去在查找插入位置時(shí)的對(duì)是否出界的判斷 5. O(n)、O(log2n) 6. 直接插入排序或者改進(jìn)了的冒泡排序、快速排序 7. Log2n、n 8. 完全二叉樹(shù)、n/2 9. 15 10. {12 38 25 35 50 74 63 90} 應(yīng)用題 11. （1）Shell排序(步長(zhǎng)為5 3 1)每趟的排序結(jié)果 初始序列為 100 87 52 61 27 170 37 45 61 118 14 88 32 步長(zhǎng)為5的排序 14 37 32 61 27 100 87 45 61 118 170 88 52 步長(zhǎng)為3的排序結(jié)果 14 27 32 52 37 61 61 45 88 87 170 100 118 步長(zhǎng)為1的排序結(jié)果 14 27 32 37 45 52 61 61 87 88 100 118 最后結(jié)果 14 27 32 37 45 52 61 61 87 88 100 118 170 （2）快速排序每趟的排序結(jié)果如圖 初始序列 100 87 52 61 27 170 37 45 61 118 14 88 32 第一趟排序 [32 87 52 61 27 88 37 45 61 14]100[118 170] 第二趟排序 [14 27]32[61 52 88 37 45 61 87]100 118[170] 第三趟排序 14[27]32[45 52 37]61[88 61 87]100 118[170] 第四趟排序 14[27]32[37]45[52]61[87 61]88 100 118[170] 第五趟排序 14[27]32[37]45[52]61[87 61]88 100 118[170] 最后結(jié)果 14[27]32[37]45[52]61[61]87 88 100 118[170] （3）二路歸并排序每趟的排序結(jié)果 初始序列 [100][87][52][61][27][170][37][45][61][118][14][88][32] 第一趟歸并 [87 100][52 61][27 170][37 45][61 118][14 88][32] 第二趟歸并 [52 61 87 100][27 37 45 170][14 61 88 118][32] 第三趟歸并排序 [27 37 45 52 61 87 100 170][14 32 61 88 118] 第四趟歸并排序 [14 27 32 37 45 52 61 61 87 88 100 118 170] 最后結(jié)果 14 27 32 37 45 52 61 61 87 88 100 118 170 12. 采用快速排序時(shí)，第一趟排序過(guò)程中的數(shù)據(jù)移動(dòng)如圖： 算法設(shè)計(jì)題 1. 分析：為討論方便，待排序記錄的定義為（后面各算法都采用此定義）： 　　#define MAXSIZE 100 /* 順序表的最大長(zhǎng)度，假定順序表的長(zhǎng)度為100 */ 　　typedef int KeyType; /* 假定關(guān)鍵字類(lèi)型為整數(shù)類(lèi)型 */ 　　typedef struct { 　　 KeyType key; /* 關(guān)鍵字項(xiàng) */ 　　 OtherType other; /* 其他項(xiàng) */ 　　}DataType; /* 數(shù)據(jù)元素類(lèi)型 */ 　　typedef struct { 　　 DataType R[MAXSIZE+1]; /* R[0]閑置或者充當(dāng)哨站 */ 　　 int length; /* 順序表長(zhǎng)度 */ 　　}sqList; /* 順序表類(lèi)型 */ 　　 設(shè)n個(gè)整數(shù)存儲(chǔ)在R[1..n]中，因?yàn)榍皀-2個(gè)元素有序，若采用直接插入算法，共要比較和移動(dòng)n-2次，如果最后兩個(gè)元素做一個(gè)批處理，那么比較次數(shù)和移動(dòng)次數(shù)將大大減小。 算法如下： （1） 求出大小 若R[n] >= R[n-1]，則large = R[n]，small = R[n-1]；否則large = R[n-1]，small = R[n]。 （2） 尋找large的位置，從 i = n – 2 開(kāi)始循環(huán)，若large < R[i]，則R[i]后移兩個(gè)單元，并且i-1；否則執(zhí)行第三步。 （3） 插入large R[i+2] = large （4） 尋找small的位置 從i開(kāi)始循環(huán)，若small < R[i]，則R[i]后移一個(gè)單元，并且i減1；否則，執(zhí)行第五步。 （5） 插入small R[i+1] = small，結(jié)束 算法描述如下： 　　void insert-two( SqList * s ){ 　　 int n,i; 　　 DataType large,small; 　　 n = s->length; 　　 if( s->R[n].key >= s->R[n-1].key ){ 　　 large = s->R[n]; 　　 small = s->R[n-1]; 　　 }else{ 　　 large = s->R[n-1]; 　　 small = s->R[n]; 　　 } 　　 i = n-2; 　　 s->R[0] = large; 　　 while( large.key < s->R[i].key ){ 　　 s->R[i+2] = s->R[i]; 　　 i = i-1; 　　 } 　　 s->R[i+2] = large; 　　 s->R[0] = small; 　　 while( small.key < s->R[i].key ){ 　　 s->R[i+1] = s->R[i]; 　　 i = i-1; 　　 s->R[i+1] = small; 　　 } } 算法分析： 因?yàn)閷?duì)兩個(gè)元素的插入是“同時(shí)”相繼進(jìn)行的，所以讓其比較次數(shù)的最大值為n，最小值為3；平均值約為n/2；移動(dòng)次數(shù)的最大值為n+2，最小值為4，平均約為n/2 。 可以看出，平均比較次數(shù)和記錄的平均移動(dòng)次數(shù)約為直接插入排序的一半。該算法是穩(wěn)定的。 2. 分析：設(shè)R[0]~R[n-1]中存有n個(gè)記錄的待排序列，對(duì)其進(jìn)行雙向冒泡。奇數(shù)趟對(duì)序列R[]從前往后掃描，比較相鄰的關(guān)鍵字，若逆序則交換，直到把關(guān)鍵字最大的記錄移動(dòng)到序列尾部；偶數(shù)趟從后往前掃描，比較相鄰的關(guān)鍵字，若逆序則交換，直到把關(guān)鍵字最小的記錄移動(dòng)到序列前端，反復(fù)進(jìn)行上述過(guò)程，直到有序?yàn)橹?。因此需設(shè)變量i，記錄掃描的循環(huán)次數(shù)（奇數(shù)趟和偶數(shù)趟兩趟作為一個(gè)循環(huán)），以便對(duì)待排序列的上下界進(jìn)行修正。 算法描述如下： 　　void Shuttlesort( DataType R[], int n ){ 　　 int i=1,j,exchange = 1; 　　 while( exchange == 1 ){ 　　 exchange = 0; 　　 for( j=i-1;j<=n-i-1;++j ){ 　　 if( R[j].key > R[j+1].key ){ 　　 R[j] <=> R[j+1]; /* 交換 */ 　　 exchange = 1; 　　 } 　　 } 　　 for( j=n-i-1;j>=i;j-- ){ 　　 if( R[j-1].key > R[j].key ){ 　　 R[j-1] <=> R[j]; /* 交換 */ 　　 exchange = 1; 　　 } 　　 } 　　 ++i; 　　 } } 可以看出，循環(huán)次數(shù)最多為[n/2]+1次，最少為1次。記錄的比較次數(shù)和移動(dòng)次數(shù)等同于單向掃描時(shí)的冒泡排序。 [此文檔可自行編輯修改，如有侵權(quán)請(qǐng)告知?jiǎng)h除，感謝您的支持，我們會(huì)努力把內(nèi)容做得更好] 最新可編輯word文檔