數(shù)據(jù)結(jié)構(gòu)分析與管理教案

1、前言緣起數(shù)據(jù)結(jié)構(gòu)是一門計(jì)算機(jī)專業(yè)基礎(chǔ)課，各類計(jì)算機(jī)考試都禁不住要考它，專升本考試自然也不例外。我給學(xué)生輔導(dǎo)這門課程差不多有幾個(gè)年頭了，講稿換了幾次，逐漸豐富起來。加之看到學(xué)生們埋頭記筆記時(shí)辛苦的模樣，就產(chǎn)生了寫一本小冊(cè)子的方法。另外，還有一層意思確實(shí)是對(duì)數(shù)次輔導(dǎo)進(jìn)行總結(jié)，以便交流之用。講明首先，需要講明的是這本書在語言風(fēng)格上不太講究，常有些不嚴(yán)謹(jǐn)?shù)谋磉_(dá)，或調(diào)侃，或土得掉渣，難登大雅之堂，請(qǐng)勿在正規(guī)場合引用這些講法。如此做的目的，僅僅是為了更簡練、更直接地描述思想，方便理解、經(jīng)歷和使用。凡是這種情況，往往都用引號(hào)括起來，并加以腳注講明。還有，本書需配合數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)教材使用。由于篇幅有限，多

2、數(shù)概念、術(shù)語沒有詳釋。 另外，每章之后都配有習(xí)題，或多或少，難度不一，并沒有局限于專升本的要求。對(duì)所有習(xí)題都提供了參考答案。致謝我要感謝所有給予我關(guān)心的人。張志老師的大力支持和關(guān)心使得本書得以面世，他還提供了近年專升本試題。李永干老師的關(guān)心使得本書順利印刷。譚業(yè)武老師給了我專門大支持，還提出了專門多建議。最后，我要感謝隆坤，她總是給我最大的支持，使那些本來只在我想象中的情況變成現(xiàn)實(shí)。莊波于濱州學(xué)院 TOC o 1-3 h z u HYPERLINK l _Toc101798259 第0章 復(fù)習(xí)提示 /ASL = (15+23)/8 = 11/8注：關(guān)鍵字在鏈表中的插入位置能夠在表頭或表尾，也能

3、夠在中間以便保持關(guān)鍵字有序。最后，此哈希表的裝填因子是= 8/11。習(xí)題 STYLEREF 1 s 9. SEQ 習(xí)題 * ARABIC s 1 1 對(duì)n=10個(gè)元素的表順序查找，在等概率情況下(對(duì)每個(gè)元素查找的概率相同)，查找成功時(shí)的平均查找長度是多少？假如查找失敗的概率為0.2，平均查找長度又是多少？ STYLEREF 1 s 9. SEQ 習(xí)題 * ARABIC s 1 2 表長15的有序表進(jìn)行折半查找，計(jì)算等概率情況下查找成功時(shí)的平均查找長度和查找第3個(gè)元素需要比較關(guān)鍵字的個(gè)數(shù)。 STYLEREF 1 s 9. SEQ 習(xí)題 * ARABIC s 1 3 對(duì)表長1023的有序表折半查找

4、，比較8個(gè)關(guān)鍵字才能找到的元素有多少個(gè)？至多比較8次就能找到的元素有多少個(gè)？ STYLEREF 1 s 9. SEQ 習(xí)題 * ARABIC s 1 4 長度為10000的表進(jìn)行分塊查找，用順序查找確定所在塊，塊內(nèi)元素?zé)o序，為使平均查找長度最小應(yīng)該分幾塊？ STYLEREF 1 s 9. SEQ 習(xí)題 * ARABIC s 1 5 編寫算法推斷給定的二叉樹是否是二叉排序樹。 STYLEREF 1 s 9. SEQ 習(xí)題 * ARABIC s 1 6 給定一組關(guān)鍵字(13，24，37，90，53，40，20)，建立二叉排序樹。 STYLEREF 1 s 9. SEQ 習(xí)題 * ARABIC s

5、1 7 給定一組關(guān)鍵字(13，24，37，90，53，40，20)，建立平衡二叉排序樹。 STYLEREF 1 s 9. SEQ 習(xí)題 * ARABIC s 1 8 編寫平衡二叉排序樹的查找算法。 STYLEREF 1 s 9. SEQ 習(xí)題 * ARABIC s 1 9 具有20個(gè)結(jié)點(diǎn)的二叉排序樹的最大深度是(_)，最小深度是(_)；20個(gè)結(jié)點(diǎn)的平衡二叉排序樹最大深度是(_)。 STYLEREF 1 s 9. SEQ 習(xí)題 * ARABIC s 1 10 在一棵非空的5階B-樹中，非葉子結(jié)點(diǎn)中最少有(_)棵子樹，最多有(_)個(gè)關(guān)鍵字；除根以外的非終端結(jié)點(diǎn)中最少有(_)棵子樹。 STYLERE

6、F 1 s 9. SEQ 習(xí)題 * ARABIC s 1 11 已知一組關(guān)鍵字19, 14, 23, 1, 68, 20, 85, 9，采納哈希函數(shù)H(key)=key MOD 13，請(qǐng)分不采納以下處理沖突的方法構(gòu)造哈希表，并求各自的平均查找長度。 1) 采納線性探測再散列； 2) 采納偽隨機(jī)探測再散列，偽隨機(jī)函數(shù)為f(n) = n2+2n+3； 3) 采納鏈地址法。內(nèi)部排序基礎(chǔ)知識(shí)和算法排序的有關(guān)概念排序（按關(guān)鍵字大小順序排列數(shù)據(jù)）。排序方法：內(nèi)部排序，外部排序；簡單的排序方法O(n2)，先進(jìn)的排序方法O(nlogn)，基數(shù)排序O(dn)；插入排序，交換排序，選擇排序，歸并排序，計(jì)數(shù)排序。排

7、序方法的穩(wěn)定性：取決于該方法采取的策略，不是由一次具體的排序結(jié)果決定的。然而通過列舉不穩(wěn)定的排序?qū)嵗軌蛑v明該排序算法的不穩(wěn)定性。直接插入排序思路將待排序記錄插入已排好的記錄中，不斷擴(kuò)大有序序列一句話，“將待排序記錄插入有序序列，重復(fù)n-1次” 不準(zhǔn)確的講法，只為便于理解和經(jīng)歷，不要在正式場合引用。 不準(zhǔn)確的講法，只為便于理解和經(jīng)歷，不要在正式場合引用。例：52，49，80，36，14，58，61 進(jìn)行直接插入排序。808036145861(52)52)36145861(4980)5236145861(49524980)5861(3649365280)5861(144936525880)61(

8、14493652586180)(14分析表 STYLEREF 1 s 10. SEQ 表 * ARABIC s 1 1 直接插入排序比較移動(dòng)記錄順序有序時(shí)n-10最好記錄逆序有序時(shí)(n+2)(n-1)/2(n+4)(n-1)/2最壞平均n2/4，算法的時(shí)刻復(fù)雜度O(n2)。直接插入排序是穩(wěn)定的排序算法。折半插入排序思路在直接插入排序中，查找插入位置時(shí)采納折半查找的方法。程序void BinInsertSort XE BinInsertSort ( T a, int n ) for ( i=1; in; i+ ) / 在a0.i-1中折半查找插入位置使ahighaiahigh+1.i-1 low

9、 = 0; high = i-1; while ( low=high ) m = ( low+high )/2; if ( aihigh; j- ) aj+1 = aj; a high+1 = x; / 完成插入 分析時(shí)刻復(fù)雜度O(n2)。比直接插入排序減少了比較次數(shù)。折半插入排序是穩(wěn)定的排序算法。希爾排序（縮小增量排序）思路先將待排序列分割成若干個(gè)子序列，分不進(jìn)行直接插入排序，差不多有序后再對(duì)整個(gè)序列進(jìn)行直接插入排序。步驟：10. 分成子序列(按照增量dk)；20. 對(duì)子序列排序(直接插入排序)；30. 縮小增量，重復(fù)以上步驟，直到增量dk=1。增量序列中最后一個(gè)增量一定是1，如：. 9,

10、5, 3, 2, 1和. 13, 4, 1。如沒有明確講明增量序列能夠選擇. 3, 2, 1或. 5, 3, 2, 1。例：希爾排序(52，49，80，36，14，58，61)。8080493614586152dk=358145249806136dk=249145258806136dk=149365258618014注意：希爾排序是不穩(wěn)定的。時(shí)刻復(fù)雜度大約為O(n3/2)。程序void ShellSort XE ShellSort ( T a, int n ) dk = n/2; while ( dk=1 ) / 一趟希爾排序，對(duì)dk個(gè)序列分不進(jìn)行插入排序 for ( i=dk; i=0 an

11、d xaj; j-=dk ) aj+dk = aj; aj+dk = x; / 縮小增量 dk = dk/2; 起泡排序思路一句話，“依次比較相鄰元素，逆序則交換，重復(fù)n-1次” 不準(zhǔn)確的講法，只為便于理解和經(jīng)歷，不要在正式場合引用。 不準(zhǔn)確的講法，只為便于理解和經(jīng)歷，不要在正式場合引用。例：冒泡排序(52，49，80，36，14，58，61)。8080493614586152365214586180491436525861804949145258618036493652586180144936525861801449365258618014程序請(qǐng)參考 REF _Ref96512884 w h

12、 第1章 二、BubbleSort算法。分析比較和交換總是發(fā)生在相鄰元素之間，是穩(wěn)定的排序算法。時(shí)刻復(fù)雜度O(n2)?？焖倥判蛩悸芬惶伺判虬延涗浄指畛瑟?dú)立的兩部分，一部分關(guān)鍵字均比另一部分小，然后再分不對(duì)兩部分快排。例：52 49 80 36 14 58 61 快速排序。下面是一次劃分的詳細(xì)步驟：808049365861)(5261)58141480493661)581480493661)581480493661)58(14(804936)52技巧：選第1個(gè)記錄為軸，分不從后向前，從前向后掃描記錄，后面“抓大放小”(如：)，前面“抓小放大”(如：)，交替進(jìn)行(-)，最后將軸記錄放在中間()，劃

13、分成兩個(gè)序列。整個(gè)快速排序過程如下：80804936145861)(5261)58(1449(8036)52144936)(36)(49(6158)80(58)6114364952586180程序void QuickSort XE QuickSort ( T a, int low, int high ) if ( low high ) / 劃分 pivot = alow; i = low; j = high; while ( i j ) while ( i= pivot ) j-; ai = aj; while ( ij & ai = pivot ) i+; aj = ai; ai = piv

14、ot; / 對(duì)子序列快排 QuickSort ( a, low, i-1); QuickSort ( a, i+1, high); 分析平均情況下，時(shí)刻復(fù)雜度O(nlogn)。記錄本來有序時(shí)為最壞情況，時(shí)刻復(fù)雜度為O(n2)?？臻g復(fù)雜度(考慮遞歸調(diào)用的最大深度)在平均情況下為O(logn)，在最壞情況下為O(n)?？焖倥判蚴遣环€(wěn)定的。簡單選擇排序思路第i趟排序過程是在剩余的待排記錄中選一個(gè)最?。ù螅┑?，放在第i個(gè)位置。一句話，“在待排記錄中選取最小的，交換到合適位置，重復(fù)n-1次” 不準(zhǔn)確的講法，只為便于理解和經(jīng)歷，不要在正式場合引用。 不準(zhǔn)確的講法，只為便于理解和經(jīng)歷，不要在正式場合引用。例

15、：52 49 80 36 14 58 61簡單選擇排序。804980493614586152804936145861528049361458615280493614586152804936145861528049361458615280493614586152程序void SelectionSort XE SelectionSort ( T a, int n ) for ( i=0; in-1; i+ ) k = i; for ( j=i+1; jn; j+) if ( aj=high ) return; else mid = (low+high)/2; MergeSort ( a, low,

16、 mid ); MergeSort ( a, mid+1, high ); Merge ( a, low, mid, high ); 自底向上的歸并排序：void MergeSort XE MergeSort ( T a, int n ) t = 1; while ( tn ) s = t; t = s*2; for ( i=0; i+t=n; i+=t ) Merge ( a, i, i+s-1, i+t-1 ); if ( i+sn ) Merge ( a, i, i+s-1, n-1 ); 附：Merge()，將有序序列alow.mid和amid+1.high歸并到alow.high。v

17、oid Merge XE Merge ( T a, int low, int mid, int high ) / 歸并到b i = low; j = mid+1; k = low; while ( i=mid and j=high ) if ( ai=aj ) bk = ai; i+; else bk = aj; j+; k+; / 歸并剩余元素 while ( i=mid ) bk+ = ai+; while ( j=high ) bk+ = aj+; / 從b復(fù)制回a alow.high = blow.high;分析時(shí)刻復(fù)雜度O(nlogn)。需要空間多，空間復(fù)雜度O(n)。歸并排序是穩(wěn)定

18、的排序?；鶖?shù)排序思路多關(guān)鍵字排序最高位優(yōu)先（MSD），最低位優(yōu)先（LSD）。鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序采納“分配”和“收集”策略。例：503，087，512，061，908，170，897，275，653分析：數(shù)字09共10種情況，rd=10。 每個(gè)關(guān)鍵字都有3位數(shù)字，d=3。 共有9個(gè)記錄，n=9。先“收集”成一個(gè)鏈表，按最低位（個(gè)位）“分配”到10個(gè)鏈表中（0號(hào)9號(hào)）：00123456789170061512503275087908653897按個(gè)位順序“收集”成一個(gè)鏈表：( 170, 061, 512, 503, 653, 275, 087, 897, 908 )再按第2位數(shù)字（十位）“分

19、配”到10個(gè)鏈表中：00123456789503512653061170897908275“收集”成一個(gè)鏈表：( 503, 908, 512, 653, 061, 170, 275, 897 )按第3位數(shù)字（百位）“分配”到10個(gè)鏈表中：00123456789061170275503653897908512“收集”成一個(gè)鏈表：( 061, 170, 275, 503, 512, 653, 897, 908 )完成排序。分析對(duì)n個(gè)數(shù)據(jù)進(jìn)行基數(shù)排序，每個(gè)數(shù)據(jù)基數(shù)為rd，有d位數(shù)字。那么，一趟分配和收集用時(shí)n+rd(分配用n，收集用rd)，共需d趟，總的時(shí)刻復(fù)雜度為O(d(n+rd)?；鶖?shù)排序是穩(wěn)定

20、的排序算法。各種排序方法比較表 STYLEREF 1 s 10. SEQ 表 * ARABIC s 1 2 排序方法的比較排序方法時(shí)刻復(fù)雜性空間復(fù)雜性穩(wěn)定特點(diǎn)平均最好最壞簡單插入排序O(n2)O(n)O(n2)O(1)是元素少或差不多有序時(shí)高效希爾排序O(n3/2)O(1)否冒泡排序O(n2)O(n)O(n2)O(1)是快速排序O(nlogn)O(nlogn)O(n2)O(logn)否平均時(shí)刻性能最好簡單選擇排序O(n2)O(1)否比較次數(shù)最多堆排序O(nlogn)O(1)否輔助空間少歸并排序O(nlogn)O(n)是穩(wěn)定的基數(shù)排序O(d(n+rd)O(rd)是適合個(gè)數(shù)多關(guān)鍵字較小基于關(guān)鍵字比

21、較的排序方法，在最壞情況下所能達(dá)到的最好的時(shí)刻復(fù)雜度是O(nlogn)。習(xí)題 STYLEREF 1 s 10. SEQ 習(xí)題 * ARABIC s 1 1 對(duì)待排序列(24, 86, 48, 56, 72, 36)進(jìn)行 1) 直接插入排序，2) 希爾排序，3) 起泡排序，4) 快速排序，5) 簡單選擇排序，6) 堆排序，7) 歸并排序，8) 鏈?zhǔn)交鶖?shù)排序。 STYLEREF 1 s 10. SEQ 習(xí)題 * ARABIC s 1 2 證明：借助比較進(jìn)行的排序方法，在最壞情況下所能達(dá)到的最好的時(shí)刻復(fù)雜度是O(nlogn)。附錄A: 習(xí)題解答 REF _Ref94387123 1.1 編寫冒泡排序

22、算法，使結(jié)果從大到小排列。void BubbleSortDec XE BubbleSortDec ( DataType a, int n ) for ( i=0; in-1; i+ ) change = false; for( j=0; jn-i-1; j+ ) if ( ajaj+1 ) / 逆序 swap( aj, aj+1 ); change = true; if ( not change ) break; / 沒有交換則完成排序 REF _Ref99086399 h 1.2 計(jì)算下面語句段中指定語句的頻度： 1) for ( i=1; i=n; i+ ) for ( j=i; j=n;

23、 j+ ) x+;/ 2) i = 1; while ( i=n ) i = i*2;/ 分析：計(jì)算語句頻度是計(jì)算時(shí)刻復(fù)雜度的基礎(chǔ)。能夠用觀看和歸納進(jìn)行簡單的計(jì)算。1) 問題規(guī)模n執(zhí)行次數(shù)1122+133+2+1.nn+.+2+1=n(n+1)/2結(jié)論：語句頻度為n(n+1)/2。2) 問題規(guī)模n執(zhí)行次數(shù)11223243.2kk+1結(jié)論：語句頻度為。 REF _Ref94417305 h 2.1 將順序表中的元素反轉(zhuǎn)順序。void Reverse XE Reverse ( SqList& L ) for ( i=0; iL.length/2; i+) / eq oac(,?) 依舊 =0 &

24、L.elemix; i-) L.elemi+1 = L.elemi; / 插入x (因?yàn)樽詈髨?zhí)行i-，故應(yīng)在i+1處) L.elemi+1 = x; L.length+; return true; REF _Ref94429906 2.3 刪除順序表中所有等于x的元素。void Remove XE Remove ( SqList &L, DataType x ) i = 0; / 剩余元素個(gè)數(shù)，同時(shí)是下一個(gè)元素的插入位置 for ( j=0; jL.length; j+ ) if ( L.elemj!=x ) / 復(fù)制不等于x的元素組成新表 if ( i!=j ) L.elemi = L.el

25、emj; / 當(dāng)i=j時(shí)不必復(fù)制 i+; L.length = i; / 剩余元素個(gè)數(shù)本算法的時(shí)刻復(fù)雜度為O(n)；若改用反復(fù)調(diào)用查找和刪除算法，時(shí)刻復(fù)雜度會(huì)達(dá)到O(n2)。 REF _Ref94429914 2.4 編寫算法實(shí)現(xiàn)順序表元素唯一化(即使順序表中重復(fù)的元素只保留一個(gè))，給出算法的時(shí)刻復(fù)雜度。思路：設(shè)差不多唯一化的序列是(a0, , ai-1)，剩余序列是(aj, an)。所要做的確實(shí)是在差不多唯一化的序列L.elem0.i-1中查找L.elemj，假如未找到則復(fù)制到L.elemi處。如此重復(fù)直到剩余序列為空。void Unique XE Unique ( SqList &L )

26、if ( L.length=1 ) return; / 空表或只有一個(gè)元素的表差不多唯一化了 i = 1; / 開始L.elem0.0是唯一化序列 for ( j=1; jL.length; j+ ) / 在L.elem0.i-1中查找L.elemj for ( k=0; ki; k+ ) if ( L.elemk=L.elemj ) break; if ( k=i ) / L.elemj未出現(xiàn)過，復(fù)制到L.elemi處 if ( j!=i ) L.elemi = L.elemj; i+; L.length = i; / 表長為i以上算法的時(shí)刻復(fù)雜度為O(n2)。因此，能夠反復(fù)將重復(fù)元素刪除達(dá)

27、到唯一化，時(shí)刻復(fù)雜度仍是O(n2)，然而與以上算法相比要移動(dòng)更多元素。 REF _Ref94429918 2.5 非遞減有序的順序表元素唯一化(參見習(xí)題2.4)，要求算法的時(shí)刻復(fù)雜度為O(n)。分析：由于該表是有序的，相等的元素必定靠在一起，不必從頭開始查找，因此算法的時(shí)刻復(fù)雜度能夠降低。思路：類似習(xí)題 REF _Ref94428249 h 2.4，然而查找部分只要與L.elemi-1比較就能夠了。void Unique XE Unique ( SqList &L ) i = 0; / 開始的唯一化序列為空( eq oac(,?)對(duì)比習(xí)題 REF _Ref94428249 h 2.4考慮什么緣

28、故不用i=1開始 緣故是那個(gè)地點(diǎn)不能確定表是否為空，而習(xí)題2.4則用開始的if語句排除了空表的情況。事實(shí)上，習(xí)題2.4也能夠仿照此處修改，請(qǐng)讀者自己完成。) 緣故是那個(gè)地點(diǎn)不能確定表是否為空，而習(xí)題2.4則用開始的if語句排除了空表的情況。事實(shí)上，習(xí)題2.4也能夠仿照此處修改，請(qǐng)讀者自己完成。 for ( j=1; jnext; / 原鏈表 L-next = NULL; / 新表(空表) while ( p ) / 從原鏈表中取下結(jié)點(diǎn)s s = p; p = p-next; / 插入L新表表頭 s-next = L-next; L-next = s; REF _Ref94429922 2.7

29、采納插入法將單鏈表中的元素排序。void InsertionSort XE InsertionSort ( LinkList &L ) h = L-next; / 原鏈表 L-next = NULL; / 新空表 while ( h ) / 從原鏈表中取下結(jié)點(diǎn)s s = h; h = h-next; / 在新表中查找插入位置 p = L; while ( p-next & p-next-datadata ) p = p-next; / 在p之后插入s s-next = p-next; p-next = s; REF _Ref94429925 2.8 采納選擇法將單鏈表中的元素排序。void S

30、electionSort XE SelectionSort ( LinkList &L ) p = L; while ( p-next ) / 選擇最小(從p-next至表尾) q = p; / 最小元素的前驅(qū)q s = p; while ( s-next ) if ( s-next-data next-data ) q = s; s = s-next; m = q-next; / 找到最小m / 最小元素m插入有序序列末尾(p之后) if ( q!=p ) q-next = m-next; / 解下最小m m-next = p-next; / 插入p之后 p-next = m; p = p-

31、next; / L-next至p為有序序列 REF _Ref94429926 2.9 將兩個(gè)非遞減有序的單鏈表歸并成一個(gè)，仍并保持非遞減有序。/ 將非遞減有序的單鏈表lb合并入la，保持非遞減有序/ 結(jié)果la中含有兩個(gè)鏈表中所有元素，lb為空表void Merge XE Merge ( LinkList &la, LinkList &lb ) p = la, q = lb; while ( p-next and q-next ) / 躍過la中較小的元素 while ( p-next and (p-next-data next-data) ) p = p-next; / 把lb中較小的元素插入

32、la中 while ( p-next and q-next and (q-next-data next-data) ) s = q-next; q-next = s-next; s-next = p-next; p-next = s; p = s; if ( lb-next ) / 表lb剩余部分插入la末尾 p-next = lb-next; lb-next = NULL; REF _Ref94546422 h 3.1 元素1,2,3,4依次入棧，不可能的出棧序列有哪些？分析：什么是不可能的出棧序列？假如后入棧的數(shù)(如4)先出棧，則此前入棧元素(如1,2,3)在棧中的順序就確定了，它們的出棧

33、順序一定是逆序(如3,2,1)，否則確實(shí)是不可能的出棧序列(如2,1,3)。不可能的出棧序列有：4123，4132，4213，4231，4312，3412，3142，3124。其中后3種都含312這一不可能序列。 REF _Ref94546425 h 3.2 設(shè)循環(huán)隊(duì)列Q少用一個(gè)元素區(qū)分隊(duì)列空和隊(duì)列滿，MAXSIZE=5，Q.front=Q.rear=0，畫出執(zhí)行下列操作時(shí)隊(duì)列空和隊(duì)列滿的狀態(tài)。入隊(duì)列a,b,c，出隊(duì)列a,b,c，入隊(duì)列d,e,f,g。farfabrfabcrfbcrfcr f r 隊(duì)列空 . frfdefgrfde 隊(duì)列滿。 REF _Ref94546427 h 3.3 編寫

34、算法利用棧將隊(duì)列中的元素翻轉(zhuǎn)順序。思路：先將隊(duì)列中的元素入棧，然后從棧中取出重新入隊(duì)列。void Reverse XE Reverse ( SqQueue &Q ) InitStack ( S ); while ( ! QueueEmpty(Q) ) DeQueue ( Q, x ); Push ( S, x ); while ( ! StackEmpty(S) ) Pop ( S, x ); EnQueue ( Q, x ); REF _Ref94533139 h 4.1 長度為n的串的子串最多有多少個(gè)？思路：對(duì)子串長度歸納。子串的長度是0，1，2，.，n，對(duì)應(yīng)子串的個(gè)數(shù)分不是1(空串)，n

35、，n-1，.，1，總起來確實(shí)是1+n+(n-1)+.+2+1=1+n(n+1)/2。 REF _Ref94628946 h 6.1 度為k的樹中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，nk個(gè)度為k的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)。分析：分不從結(jié)點(diǎn)個(gè)數(shù)和分支個(gè)數(shù)考慮。設(shè)葉子個(gè)數(shù)為n0，結(jié)點(diǎn)總數(shù)：n = n0+n1+n2+.+nk，分支數(shù)目：n-1 = n1+2 n2+.+k nk，因此得到葉子個(gè)數(shù) REF _Ref94628950 h 6.2 有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹的高度是多少?分析：完全二叉樹中度為1的結(jié)點(diǎn)至多有一個(gè)。完全二叉樹中的結(jié)點(diǎn)數(shù)n+(n-1) N n + (n-1) + 1，即

36、2n-1 N 2n，二叉樹的高度是因此，(1) 當(dāng)n=2k時(shí)，當(dāng)沒有度為1的結(jié)點(diǎn)時(shí)；，當(dāng)有1個(gè)度為1的結(jié)點(diǎn)時(shí)。(2) 其他情況下，。 REF _Ref94628952 h 6.3 編寫算法按照縮進(jìn)形式打印二叉樹。void PrintBinaryTree XE PrintBinaryTree ( BinTree bt, int indent ) if ( ! bt ) return; for ( i=0; idata ); PrintBinaryTree ( bt-lchild, indent+1 ); PrintBinaryTree ( bt-rchild, indent+1 ); REF _

37、Ref94628953 h 6.4 編寫算法按照逆時(shí)針旋轉(zhuǎn)90度的形式打印二叉樹。void PrintBinaryTree XE PrintBinaryTree ( BinTree bt, int level ) if ( ! bt ) return; PrintBinaryTree ( bt-rchild, level+1 ); / 旋轉(zhuǎn)后先打印右子樹 for ( i=0; idata ); PrintBinaryTree ( bt-lchild, level+1 ); REF _Ref94628972 h 6.5 編寫算法推斷二叉樹是否是完全二叉樹。分析：按層遍歷完全二叉樹，當(dāng)遇到第一個(gè)空

38、指針之后應(yīng)該全差不多上空指針。bool IsComplete XE IsComplete ( BinTree bt ) / 按層遍歷至第一個(gè)空指針 InitQueue ( Q ); EnQueue ( Q, bt ); while ( ! QueueEmpty(Q) ) DeQueue ( Q, p ); if ( p ) EnQueue ( Q, p-lchild ); EnQueue ( Q, p-rchild ); else break; / 遇到第一個(gè)空指針時(shí)停止遍歷 / 檢查隊(duì)列中剩余元素是否全部是空指針 while ( ! QueueEmpty(Q) ) DeQueue ( Q,

39、p ); if ( ! p ) return false; / 不是完全二叉樹 return true; / 完全二叉樹 REF _Ref94628974 h 6.6 編寫算法求二叉樹中給定結(jié)點(diǎn)的所有祖先。分析：進(jìn)行后序遍歷時(shí)，棧中保存的是當(dāng)前結(jié)點(diǎn)的所有祖先。因此，后序遍歷二叉樹，遇到該結(jié)點(diǎn)時(shí)，取出棧中的內(nèi)容即是所有祖先。/ 求二叉樹bt中結(jié)點(diǎn)xptr的所有祖先vector Ancestors XE Ancestors ( BinTree bt, BinTree xptr ) stack s; stack tag; p = bt; while ( p | ! s.empty() ) if (

40、p ) s.push ( p ); tag.push ( 1 ); p = p-lchild; else p = s.pop(); f = tag.pop(); if ( f=1 ) s.push ( p ); tag.push ( 2 ); p = p-rchild; else if ( p=xptr ) v = s; / 當(dāng)前棧的內(nèi)容確實(shí)是xptr的所有祖先 return v; p = NULL; / while return vector(); / return a null vector注：那個(gè)地點(diǎn)為描述方便借助了C+中的某些描述方式。 REF _Ref94628975 h 6.7 編

41、寫算法求二叉樹中兩個(gè)結(jié)點(diǎn)的最近的共同祖先。思路：用后序遍歷求出兩者的所有祖先，依次比較。/ 求二叉樹bt中兩個(gè)結(jié)點(diǎn)q和r的最近的共同祖先BinTree LastAncestor XE LastAncestor ( BinTree bt, BinTree q, BinTree r ) stack sq, sr; stack s; stack tag; / 求q和r的所有祖先 p = bt; while ( p | ! s.empty() ) if ( p ) s.push ( p ); tag.push ( 1 ); p = p-lchild; else p = s.pop(); f = tag

42、.pop(); if ( f=1 ) s.push ( p ); tag.push ( 2 ); p = p-rchild; else if ( p=q ) sq = s; / q的所有祖先 if ( p=r ) sr = s; / s的所有祖先 p = NULL; / 先躍過不同層的祖先，然后依次比較同一層的祖先 if ( sq.size()sr.size() ) while ( sq.size()sr.size() ) sq.pop(); else while ( sr.size()sq.size() ) sr.pop(); / 求q和r的最近的共同祖先 while ( !sq.empty

43、() and (sq.top()!=sr.top() ) /查找共同祖先 sq.pop(); sr.pop(); if ( !sq.empty() ) return sq.top(); else return NULL; REF _Ref94628977 h 6.8 編寫算法輸出以二叉樹表示的算術(shù)表達(dá)式（中綴形式），要求在必要的地點(diǎn)輸出括號(hào)。分析：當(dāng)左小孩的優(yōu)先級(jí)低于根時(shí)需要加括號(hào)，根的優(yōu)先級(jí)大于右小孩時(shí)也需要加括號(hào)。void PrintExpression XE PrintExpression ( BinTree bt ) if ( bt=NULL ) return ; if ( bt-lc

44、hild=NULL and bt-rchild=NULL ) print ( bt-data ); / 葉子結(jié)點(diǎn)直接打印 else / 左子樹 brackets = bt-lchild and is_operator(bt-lchild-data) and comp_operator(bt-lchild-data, bt-data)lchild ); if ( brackets ) print (“)”); / 根結(jié)點(diǎn) print ( bt-data ); / 右子樹 brackets = bt-rchild and is_operator(bt-lchild-data) and comp_o

45、perator(bt-data, bt-rchild-data)0; / 根的優(yōu)先級(jí)大于右小孩 if ( brackets ) print (“(“); PrintExpression ( bt-rchild ); if ( brackets ) print (“)“); 注：is_operator(c)推斷c是否是運(yùn)算符；comp_operator(a,b)比較兩個(gè)運(yùn)算符的優(yōu)先級(jí)。bool is_operator(char c) / 推斷c是否是運(yùn)算符 return c=+ | c=- | c=* | c=/;int comp_operator(char opl, char opr) / 比

46、較兩個(gè)運(yùn)算符的優(yōu)先級(jí) return (opl=* | opl=/ | opr=+ | opr=-) ? +1 : -1; REF _Ref94628980 h 6.9 樹采納小孩-兄弟鏈表存儲(chǔ)，編寫算法求樹中葉子結(jié)點(diǎn)的個(gè)數(shù)。分析：樹中的葉子沒有小孩，即firstchild為空。/ 求樹t中葉子結(jié)點(diǎn)的個(gè)數(shù)int LeafCount XE LeafCount ( CSTree t ) if ( t=NULL ) return 0; / 空樹 if ( t-firstchild=NULL ) / 沒有小孩 return 1 + LeafCount(t-nextsibling); else retur

47、n LeafCount(t-firstchild) + LeafCount(t-nextsibling); REF _Ref94628983 h 6.10 采納小孩-兄弟鏈表存儲(chǔ)樹，編寫算法求樹的度。分析：度最大的結(jié)點(diǎn)的度數(shù)。int Degree XE Degree ( CSTree t ) if ( t=NULL ) return 0; else return max( Degree(t-firstchild), 1+Degree(t-nextsibling); REF _Ref94628986 h 6.11 采納小孩-兄弟鏈表存儲(chǔ)樹，編寫算法求樹的深度。int Depth XE Depth

48、 ( CSTree t ) if ( t=NULL ) return 0; else depchild = Depth(t-firstchild); / 小孩的深度 depsibling = Depth(t-nextsibling); / 兄弟的深度 return max(depchild+1, depsibling); / 取較大者 REF _Ref94628988 h 6.12 已知二叉樹的前序和中序序列，編寫算法建立該二叉樹。分析：劃分先序序列a=(D,(L),(R)和后序序列b=(L),D,(R)，然后對(duì)子序列(L)和(R)遞歸。/ 依照先序序列asi.ti和中序序列bsj.tj構(gòu)造二

49、叉樹BinTree CreateBinaryTree XE CreateBinaryTree ( T a, int si, int ti, T b, int sj, int tj ) if ( nlchild = CreateBinaryTree ( a, si+1, si+k-sj, b, sj, k-1 ); / 建立左子樹 p-rchild = CreateBinaryTree ( a, si+k-sj+1, b, k+1, tj); / 建立右子樹 return p;GFDKICBAEHJGFDKICBAEHJ分析：依照先根和后根序列能夠唯一確定一棵樹。先根序列中的第一個(gè)是樹的根，后根

50、序列中最后一個(gè)是根，然后依照先根序列和后根序列，將其余序列劃分成若干不相交的子序列，確實(shí)是根的子樹，對(duì)每一個(gè)子樹，重復(fù)前面的步驟，最終就能夠得到整個(gè)樹。先根GFKDAIEBCHJ 根為G，第一棵子樹的根為F，又后根DIAEKFCJHBG，因此第一棵子樹為(DIAEKF)，同樣第二棵子樹為(CJHB)，依此類推，可得該樹。BADGCEFHIBADGCEFHIKLJ分析：依照森林和二叉樹的對(duì)應(yīng)關(guān)系，可知森林的先序序列和中序序列。劃分出每一棵樹，正好得到每棵樹的先序和后序序列，最終得到整個(gè)森林。 REF _Ref94795009 h 6.15 某通信過程中使用的編碼有8個(gè)字符A,B,C,D,E,F,

51、G,H，其出現(xiàn)的次數(shù)分不為20, 6, 34, 11, 9, 7, 8, 5。若每個(gè)字符采納3位二進(jìn)制數(shù)編碼，整個(gè)通信需要多少字節(jié)？請(qǐng)給出哈夫曼編碼，以及整個(gè)通信使用的字節(jié)數(shù)？分析：由于每個(gè)字符出現(xiàn)的頻率不同，使用固定長度的編碼往往比哈夫曼編碼使得整個(gè)通信量增多。那個(gè)地點(diǎn)先建立哈夫曼樹，得出哈夫曼編碼，然后計(jì)算通信所需的字節(jié)數(shù)。每字節(jié)含8位。使用固定長度的編碼所需字節(jié)數(shù)為(20+6+34+11+9+7+8+5)*3/8=37.5字節(jié)。一種可能的哈夫曼編碼是：A:00, B:1100, C:10, D:010, E:011, F:1110, G:1111, H:1101，通信的總字節(jié)數(shù)是(20+

52、34)*2+(11+9)*3+(6+5+7+8)*4/8=34字節(jié)。 REF _Ref94802916 h 6.16 n個(gè)權(quán)值構(gòu)造的哈夫曼樹共有多少個(gè)結(jié)點(diǎn)？分析：哈夫曼樹總是取兩個(gè)最小的子樹合并成一棵二叉樹，共需n-1步完成算法，共增加n-1個(gè)結(jié)點(diǎn)，故總結(jié)點(diǎn)個(gè)數(shù)為n+(n-1)=2n-1。 REF _Ref96427153 h 7.1 具有n個(gè)頂點(diǎn)的有向圖構(gòu)成強(qiáng)連通圖最少有多少條??？當(dāng)弧的數(shù)目超過多少時(shí)該圖一定是強(qiáng)連通的？分析：假如n條弧恰好使n個(gè)頂點(diǎn)構(gòu)成環(huán)的話，這是構(gòu)成強(qiáng)連通圖所需弧最少的情況。類似無向圖的情況，n-1個(gè)頂點(diǎn)最多有(n-1)(n-2)條弧，再增加n-1條指向另外一點(diǎn)頂點(diǎn)的弧(

53、或者相反方向的弧)，現(xiàn)在該圖恰好不能構(gòu)成強(qiáng)連通圖，若再增加一條弧則必定強(qiáng)連通。因此，n個(gè)頂點(diǎn)的有向圖最少需要n條弧就能夠構(gòu)成強(qiáng)連通圖；當(dāng)弧的數(shù)目超過(n-1)(n-2)+(n-1) = (n-1)2時(shí)，必定構(gòu)成強(qiáng)連通圖。 REF _Ref96428002 h 7.2 給出下面有向圖(a)的1)鄰接矩陣 2)鄰接表 3)逆鄰接表 4) 十字鏈表 和 無向圖(b)的 5)鄰接多重表。AABCDEABCDE(a)(b)00110000110000001010010010ABCDEABC/DE0123412/23/02/03/ABCDE/0123434/0/14/013/1)2)3)AABCDE/30

54、/40/01/0212/13/32/434)AABCD0123E40102/041213/1423/24/34/5) REF _Ref96427168 h 7.3 對(duì)習(xí)題7.2中圖(a)和(b)從A動(dòng)身進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索，寫出遍歷結(jié)果。分析：畫出搜索樹，寫出結(jié)果。(a) 深度優(yōu)先搜索：ABCDE，廣度優(yōu)先搜索：ABCDE；(b) 深度優(yōu)先搜索：ABCDE，廣度優(yōu)先搜索：ABCED。 REF _Ref96428010 h 7.4 下面給出圖G的鄰接矩陣，請(qǐng)寫出從頂點(diǎn)A動(dòng)身深度優(yōu)先遍歷的結(jié)果。AABCDE/32/012340/0411/2/分析：那個(gè)地點(diǎn)用鄰接表給出了圖的存儲(chǔ)結(jié)構(gòu)，同時(shí)

55、確定了鄰接點(diǎn)的先后關(guān)系。仍然采納搜索樹分析。深度優(yōu)先遍歷結(jié)果：ADEBC。 REF _Ref96427175 h 7.5 寫出圖的深度優(yōu)先遍歷算法。參考 REF _Ref96443472 w h 第7章 一、3. (1) 3. 。 REF _Ref96427178 h 7.6 寫出圖的廣度優(yōu)先遍歷算法。參考 REF _Ref96443517 w h 第7章 一、3. (2) 3. 。 REF _Ref96427182 h 7.7 證明最小生成樹的MST性質(zhì)。參考課本P173。 REF _Ref96428028 h 7.8 分不用普里姆算法和克魯斯卡爾算法計(jì)算下圖的最小生成樹。AABEFDC23

56、21315433普里姆算法：UV-UU到V-U中各頂點(diǎn)的最小代價(jià)最小代價(jià)邊BCDEFAB,C,D,E,FAB/3AC/1AD/2AC/1A,CB,D,E,FAB/3AD/2CE/5CF/4AD/2A,C,DB,E,FAB/3CE/5DF/2DF/2A,C,D,FB,EAB/3FE/3AB/3A,C,D,F,BEBE/1BE/1A,C,D,F,B,E克魯斯卡爾算法：依次選擇代價(jià)最小的邊：AC, BE, AD, DF，然后，能夠選擇AB或BC或EF即可。最小生成樹的總代價(jià)是9。 REF _Ref96428032 h 7.9 對(duì)下圖進(jìn)行拓?fù)渑判?寫出所有可能的拓?fù)溆行蛐蛄小ABDEFCG分析：可能

57、的拓?fù)溆行蛐蛄杏卸喾N，A之后可能是B或D，逐漸類推可得到所有可能的拓?fù)湫蛄校篈DBCGFE, ABDCGFE, ABCDGFE, ABCGDFE, ABCGFDE, ABCGFED，共6種。 REF _Ref96428036 h 7.10 下面是某工程的AOE網(wǎng)，計(jì)算1)整個(gè)工程完工需要多長時(shí)刻(單位：天)？ 2)工程的關(guān)鍵路徑。112345687912531352232事件最早發(fā)生時(shí)刻ve最晚發(fā)生時(shí)刻vl活動(dòng)最早開始時(shí)刻e最晚開始時(shí)刻lv100a(1,2)05v227a(1,3)00v355a(1,4)02v435a(2,5)27v588a(3,5)55v656a(3,6)56v71111a

58、(4,6)35v81111a(5,7)88v91313a(5,8)89a(6,8)56a(7,8)1111a(7,9)1111a(8,9)1111整個(gè)工程完工需要13天，關(guān)鍵路徑有135789和13579。 REF _Ref96428039 h 7.11 用迪杰斯特拉算法計(jì)算下圖中頂點(diǎn)A到其他頂點(diǎn)的最短路徑。AABCDEF6846152332終點(diǎn)從A到各頂點(diǎn)的最短路徑B8AB8AB6ADEB6ADEBC8ADC8ADC7ADFC7ADFCD2ADE3ADEF6AF4ADF4ADF最短路徑2AD3ADE4ADF6ADEB7ADFC REF _Ref96428042 h 7.12 用弗洛伊德算法計(jì)

59、算下圖中每對(duì)頂點(diǎn)之間的最短路徑。AABCD342521002AC3BA04CB02CD5DA1DB002AC3BA05BAC4CB02CD5DA1DB7DAC002AC3BA05BAC7CBA4CB02CD4DBA1DB6DBAC0A(0)A(1)A(2)006ACB2AC4ACD3BA05BAC7BACD7CBA4CB02CD4DBA1DB6DBAC005ACDB2AC4ACD3BA05BAC7BACD6CDBA3CDB02CD4DBA1DB6DBAC0A(3)A(4) REF _Ref95389943 h 9.1 對(duì)n=10個(gè)元素的表順序查找，在等概率情況下(對(duì)每個(gè)元素查找的概率相同)，查

60、找成功時(shí)的平均查找長度是多少？假如查找失敗的概率為0.2，平均查找長度又是多少？分析：等概率情況下查找成功時(shí)ASL = (n+1)/2 = 5.5；若查找失敗的概率為0.2，則ASL = 0.8(10+1)/2 + 0.211 = 6.6。技巧：能夠用歸納法。查找第1個(gè)元素比較10個(gè)關(guān)鍵字，查找第2個(gè)元素比較9個(gè)關(guān)鍵字，查找第10個(gè)元素比較1個(gè)關(guān)鍵字，總共比較10+9+1=55個(gè)關(guān)鍵字，ASL=55/10=5.5。提示：以上分析差不多上按照課本上的算法，假如遇到其他具體算法還需要具體分析。 按照課本上的算法，查找從后往前進(jìn)行，因此查找第1個(gè)元素要比較10個(gè)關(guān)鍵字。查找失敗時(shí)，由于和 按照課本上