【正文】 逆波蘭式（后綴式）。16．假設(shè)用于通信的電文由字符集{a,b,c,d,e,f,g}中的字母構(gòu)成。二叉樹(shù)按lchildrchild方式存儲(chǔ)，鏈接時(shí)用葉結(jié)點(diǎn)的rchild域存放鏈指針。 /*中序遍歷左子樹(shù)*/if (Tlchild==NULL amp。 /*設(shè)置鏈表尾結(jié)點(diǎn)*/return(head)。 else return(hr+1)。【提示】設(shè)root 為一棵用二叉鏈表存儲(chǔ)的二叉樹(shù)，則交換各結(jié)點(diǎn)的左右子樹(shù)的運(yùn)算可基于后序遍歷實(shí)現(xiàn)：交換左子樹(shù)上各結(jié)點(diǎn)的左右子樹(shù)；交換左子樹(shù)上各結(jié)點(diǎn)的左右子樹(shù)；再交換根結(jié)點(diǎn)的左右子樹(shù)?！咎崾尽慷鏄?shù)的順序存儲(chǔ)是按完全二叉樹(shù)的順序存儲(chǔ)格式按層次存儲(chǔ)的，雙親結(jié)點(diǎn)與子女結(jié)點(diǎn)的下標(biāo)間有確定的關(guān)系。 while (t=n||top0) { while (t=namp。 t=stack[top]。 while (p|| !Empty_Stack(S)) /*若p非空，或棧非空*/ { while (p){ if (pdata==x) /*若當(dāng)前結(jié)點(diǎn)值為x，依次輸出棧中元素的值*/ { while (!Empty_Stack(S)) { Pop(S,q)。 }}8．已知一棵二叉樹(shù)的后序遍歷序列和中序遍歷序列，寫(xiě)出可以確定這棵二叉樹(shù)的算法。 if (m==ir) trchild=NULL。 CM=1。 else In_Queue(Q,prchild)。if (2*i+1n) Trchild=NULL。 q==NULL) return (1)。 Similar(srchild,trchild))}12．寫(xiě)出用逆轉(zhuǎn)鏈方法對(duì)二叉樹(shù)進(jìn)行先序遍歷的算法。 p=bt。 prchild=r。amp。 q=rlchild。 rlchild=p。 } }14．對(duì)以孩子鏈表表示的樹(shù)編寫(xiě)計(jì)算樹(shù)的深度的算法。 p=pnextchild。 else { s=i。A．n B．2n C．n/2 D．n*n3．下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（B）。A．求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的B．一個(gè)事件的最早開(kāi)始時(shí)間與以該事件為尾的弧的活動(dòng)最早開(kāi)始時(shí)間相同C．一個(gè)事件的最遲開(kāi)始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開(kāi)始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差D．關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上10．有10個(gè)結(jié)點(diǎn)的無(wú)向圖至少有（B）條邊才能確保其是連通圖。（√）8．十字鏈表可以存儲(chǔ)無(wú)向圖和有向圖。（） 簡(jiǎn)答題（圖1）①④②③⑤⑥1．對(duì)于如圖1所示的有向圖，試給出：（1）每個(gè)頂點(diǎn)的入度和出度； （2）鄰接矩陣； （3）鄰接表； （4）逆鄰接表； （5）強(qiáng)連通分量。ABCDEFGHa1=3a2=5a3=6a5=9a9=5a4=7a6=10a10=3a7=8a8=6a11=2圖4（1）ve(A)=0 ve(B)= ve(A)+3=3 ve(C)= ve(A)+5=5ve(D)=max(ve(B)+6, ve(C)+7)=12 ve(E)= ve(D)+9=21 ve(G)=ve(D)+8=20ve(F)= max(ve(D)+10, ve(G)+6)=26 ve(H)= max(ve(E)+E, ve(G)+2, ve(F)+3)=29vl(H)=29 vl(E)= vl(H) – 5=24 vl(F)= vl(H) – 3=26vl(G)= min(vl(H) – 2, vl(F) – 6)=20 vl(D)= min(vl(E) – 9, vl(F) – 10, vl(G) – 8)=12vl(B)= vl(D) – 6=6 vl(C)= vl(D) – 7=5 vl(A)= min(vl(B) – 3, vl(C) – 5)= 0（2） e(a1)=0 e(a2)=0 e(a3)=3 e(a4)=5 e(a5)=12 e(a6)=12 e(a7)=12 e(a8)=20 e(a9)=21 e(a10)=26 e(a11)=20l(a1)=3 l(a2)=0 l(a3)=6 l(a4)=5 l(a5)=15 l(a6)=16 (a7)=12 l(a8)=20 l(a9)=24 l(a10)=26 l(a11)=27（3）關(guān)鍵路徑如下圖，完成該工程需要的最短時(shí)間：29ACDFGHa2=5a4=7a10=3a7=8a8=6 課后習(xí)題解答 (P152) 選擇題1．靜態(tài)查找表與動(dòng)態(tài)查找表的根本區(qū)別在于（B）A．它們的邏輯結(jié)構(gòu)不一樣 B．施加在其上的操作不一樣 C．所包含的數(shù)據(jù)元素類(lèi)型不一樣 D．存儲(chǔ)實(shí)現(xiàn)不一樣2．在表長(zhǎng)為n的順序表上實(shí)施順序查找，在查找不成功時(shí)與關(guān)鍵字比較的次數(shù)為（A）。如用二次探測(cè)再散列處理沖突，則關(guān)鍵字為49的結(jié)點(diǎn)的地址是（D）。 A．鏈接方式存儲(chǔ)，元素?zé)o序 B．鏈接方式存儲(chǔ)，元素有序C．順序方式存儲(chǔ)，元素?zé)o序 D．順序方式存儲(chǔ)，元素有序6．有一個(gè)長(zhǎng)度為12的有序表，按折半查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（B）。矩陣元素的個(gè)數(shù)與圖的邊數(shù)無(wú)關(guān)。（）12．強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖。（√）4．鄰接表法只用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用。A．v0, v3, v2, v1 B．v0, v1, v2, v3 C．v0, v2, v1, v3 D．v0, v1, v3, v26．設(shè)有向圖n個(gè)頂點(diǎn)和e條邊，進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為（D）。} } if (hmaxh) maxh=h。int high(PNode t[ ], int n) /*求有n個(gè)結(jié)點(diǎn)的樹(shù)t的深度*/{ maxh=0。max=high(t,pdata)。樹(shù)的深度＝0 若樹(shù)為空Max（第一棵子樹(shù)的深度＋1，兄弟子樹(shù)的深度） 若樹(shù)非空int high(CSTree T) { if (T==NULL ) return ( 0 )。} /*從左子樹(shù)回來(lái)*/ if (r==NULL) return。 rrchild=p。amp。 q=plchild=r。 /*tag的值初始為0，進(jìn)入左子樹(shù)時(shí)置1，從左子樹(shù)回來(lái)時(shí)，再恢復(fù)為0*/ struct tnode *lchild, *rchild。amp。所謂兩棵二叉樹(shù)s和t相似，即要么它們都為空或都只有一個(gè)結(jié)點(diǎn)，要么它們的左右子樹(shù)都相似。if (i=n){ T=(BiTree)malloc(sizeof(BiTNode))。 /*B=0表示缺少左、右孩子*/ if(rchild!=NULL) CM=0。因此，可采用按層次遍歷二叉樹(shù)的方法依次對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行判斷。 m=il。} /*若當(dāng)前結(jié)點(diǎn)值不是x，壓棧*/ p=plchild。進(jìn)入子樹(shù)時(shí)，將子樹(shù)的根壓棧；從子樹(shù)返回時(shí)，將棧頂元素出棧。 top++。 int top。p=rootlchild。else{ printf(“%d”,n)。if (root==NULL) return(0)。 } /*處理第一個(gè)葉子結(jié)點(diǎn)*/else { prerchild=T。設(shè)置前驅(qū)結(jié)點(diǎn)指針pre，初始為空?！咎崾尽坎捎眠f歸算法實(shí)現(xiàn)?！窘獯稹緼BCDEFGHIJ按層次遍歷，第一個(gè)結(jié)點(diǎn)（若樹(shù)不空）為根，該結(jié)點(diǎn)在中序序列中把序列分成左右兩部分—左子樹(shù)和右子樹(shù)。 n1。證明：由哈夫曼樹(shù)的構(gòu)造過(guò)程可知，哈夫曼樹(shù)的每一分支結(jié)點(diǎn)都是由兩棵子樹(shù)合并產(chǎn)生的新結(jié)點(diǎn)，其度必為2，所以哈夫曼樹(shù)中不存在度為1的結(jié)點(diǎn)。（√） 簡(jiǎn)答題1．一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別？樹(shù)與二叉樹(shù)之間有何區(qū)別？【解答】①二叉樹(shù)是有序樹(shù)，度為2的樹(shù)是無(wú)序樹(shù)，二叉樹(shù)的度不一定是2。（）13．哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。log2NA．2*h B． 2*h1 C． 2*h+1 D．h+115．一個(gè)具有567個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為（D）。A． 500 B． 501 C．490 D．4958．設(shè)森林F中有三棵樹(shù)，第一，第二，第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為N1，N2和N3。（1）A=((a,b,c),d,(a,b,c))（2）B=(a,(b,(c,d),e),f)（1）11111 ^1 ^1 d0 a1 b1 c（2）1111 ^1 ^1 0 f0 a0 b0 c1 ^10 c0 d 課后習(xí)題解答 選擇題1．下列說(shuō)法正確的是（C）。 （2）利用BF算法的匹配過(guò)程： 利用KMP算法的匹配過(guò)程： 第一趟匹配：aabaabaabaac 第一趟匹配：aabaabaabaac aabaac(i=6,j=6) aabaac(i=6,j=6) 第二趟匹配：aabaabaabaac 第二趟匹配：aabaabaabaac aa(i=3,j=2) (aa)baac 第三趟匹配：aabaabaabaac 第三趟匹配：aabaabaabaac a(i=3,j=1) (成功) (aa)baac第四趟匹配：aabaabaabaac aabaac(i=9,j=6)第五趟匹配：aabaabaabaac aa(i=6,j=2)第六趟匹配：aabaabaabaac a(i=6,j=1)第七趟匹配：aabaabaabaac(成功) aabaac(i=13,j=7)3．假設(shè)按行優(yōu)先存儲(chǔ)整數(shù)數(shù)組A[9][3][5][8]時(shí)，第一個(gè)元素的字節(jié)地址是100，每個(gè)整數(shù)占４個(gè)字節(jié)。（）6．若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。A．0123 B．1123 C．1231 D．12114．二維數(shù)組M的成員是6個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要（D）個(gè)字節(jié)；M的第8列和第5行共占（A）個(gè)字節(jié)；若M按行優(yōu)先方式存儲(chǔ)，元素M[8][5]的起始地址與當(dāng)M按列優(yōu)先方式存儲(chǔ)時(shí)的（C）元素的起始地址一致。例如，函數(shù)f在執(zhí)行中，又調(diào)用函數(shù)f自身，這稱為直接遞歸；若函數(shù)f在執(zhí)行中，調(diào)用函數(shù)g，而g在執(zhí)行中，又調(diào)用函數(shù)f，這稱為間接遞歸。（）5．循環(huán)隊(duì)列通常用指針來(lái)實(shí)現(xiàn)隊(duì)列的頭尾相接。f=s。A． edcba B． decba C．dceab D． abcde7．在一個(gè)鏈隊(duì)列中，若f,r分別為隊(duì)首、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（B）。Top=p。pfreq=k。 /*若查找失敗，返回空指針*/pfreq++。 int freq。rnext=NULL。 q ) if (pdataqdata) p=pnext。 LinkList C。while (pnext!=s){q=p。pb=pbnext。 /*pb指向表B的第一個(gè)結(jié)點(diǎn)*/free(B)。 /*填裝結(jié)點(diǎn)*/ snext=pnext。 Ldata[0]=x。k++) Ldata[k1]=Ldata[k]。} }}5．線性表用順序存儲(chǔ)，設(shè)計(jì)一個(gè)算法，用盡可能少的輔助存儲(chǔ)空間將順序表中前m個(gè)元素和后n個(gè)元素進(jìn)行整體互換。amp。amp。) return (1)。) return (1)。c=39。 }Alast=n。n用來(lái)記錄當(dāng)前已刪除元素的個(gè)數(shù)。 /*使k指向第一個(gè)與A[i]不同的元素*/ n=ki1。 /*插入成功*/}}時(shí)間復(fù)雜度為O(n)。 /*表已滿，無(wú)法插入*/else {i=*elenum。（√）10．在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。（）2．順序存儲(chǔ)的線性表可以按序