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