【正文】 1 ^1 ^1 0 f0 a0 b0 c1 ^10 c0 d 課后習(xí)題解答 選擇題1．下列說法正確的是（C）。A．2*h B． 2*h1 C． 2*h+1 D．h+115．一個具有567個結(jié)點的二叉樹的高h為（D）。（）13．哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。證明：由哈夫曼樹的構(gòu)造過程可知，哈夫曼樹的每一分支結(jié)點都是由兩棵子樹合并產(chǎn)生的新結(jié)點，其度必為2，所以哈夫曼樹中不存在度為1的結(jié)點。【解答】ABCDEFGHIJ按層次遍歷，第一個結(jié)點（若樹不空）為根，該結(jié)點在中序序列中把序列分成左右兩部分—左子樹和右子樹。設(shè)置前驅(qū)結(jié)點指針pre，初始為空。if (root==NULL) return(0)。p=rootlchild。 top++。} /*若當(dāng)前結(jié)點值不是x，壓棧*/ p=plchild。因此，可采用按層次遍歷二叉樹的方法依次對每個結(jié)點進行判斷。if (i=n){ T=(BiTree)malloc(sizeof(BiTNode))。amp。 q=plchild=r。 rrchild=p。樹的深度＝0 若樹為空Max（第一棵子樹的深度＋1，兄弟子樹的深度） 若樹非空int high(CSTree T) { if (T==NULL ) return ( 0 )。int high(PNode t[ ], int n) /*求有n個結(jié)點的樹t的深度*/{ maxh=0。A．v0, v3, v2, v1 B．v0, v1, v2, v3 C．v0, v2, v1, v3 D．v0, v1, v3, v26．設(shè)有向圖n個頂點和e條邊，進行拓撲排序時，總的計算時間為（D）。（）12．強連通分量是有向圖中的極大強連通子圖。 A．鏈接方式存儲，元素?zé)o序 B．鏈接方式存儲，元素有序C．順序方式存儲，元素?zé)o序 D．順序方式存儲，元素有序6．有一個長度為12的有序表，按折半查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（B）。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)鍵路徑如下圖，完成該工程需要的最短時間：29ACDFGHa2=5a4=7a10=3a7=8a8=6 課后習(xí)題解答 (P152) 選擇題1．靜態(tài)查找表與動態(tài)查找表的根本區(qū)別在于（B）A．它們的邏輯結(jié)構(gòu)不一樣 B．施加在其上的操作不一樣 C．所包含的數(shù)據(jù)元素類型不一樣 D．存儲實現(xiàn)不一樣2．在表長為n的順序表上實施順序查找，在查找不成功時與關(guān)鍵字比較的次數(shù)為（A）。（√）8．十字鏈表可以存儲無向圖和有向圖。A．n B．2n C．n/2 D．n*n3．下列哪一種圖的鄰接矩陣是對稱矩陣？（B）。 p=pnextchild。 rlchild=p。amp。 p=bt。 q==NULL) return (1)。 else In_Queue(Q,prchild)。 if (m==ir) trchild=NULL。 while (p|| !Empty_Stack(S)) /*若p非空，或棧非空*/ { while (p){ if (pdata==x) /*若當(dāng)前結(jié)點值為x，依次輸出棧中元素的值*/ { while (!Empty_Stack(S)) { Pop(S,q)。 while (t=n||top0) { while (t=namp。【提示】設(shè)root 為一棵用二叉鏈表存儲的二叉樹，則交換各結(jié)點的左右子樹的運算可基于后序遍歷實現(xiàn)：交換左子樹上各結(jié)點的左右子樹；交換左子樹上各結(jié)點的左右子樹；再交換根結(jié)點的左右子樹。 /*設(shè)置鏈表尾結(jié)點*/return(head)。二叉樹按lchildrchild方式存儲，鏈接時用葉結(jié)點的rchild域存放鏈指針。最大值：2h1； 最小值：2h112．求表達式： a＋b*(c－d)－e/f的波蘭式（前綴式）和逆波蘭式（后綴式）?！窘獯稹浚?）雙親數(shù)組表示法示意圖： （2）孩子鏈表表示法示意圖：0A11B02C03D24E25F16G17H58I29J410K411M312N82 ^6410 ^15311 ^97 ^12 ^0A1B2C3D4E5F6G7H8I9J10K11M12N8 ^（3）孩子兄弟鏈表表示法示意圖：A ^B^ N ^^ H ^C ^^ GF ^EDI ^^ J^ K ^^ M ^4．畫出圖3所示的森林經(jīng)轉(zhuǎn)換后所對應(yīng)的二叉樹，并指出森林中滿足什么條件的結(jié)點在二叉樹中是葉子。（√）9．不使用遞歸也可實現(xiàn)二叉樹的先序、中序和后序遍歷。A．cbed B．decab C．deabc D．cedba11．若一棵二叉樹的先序遍歷序列為abdgcefh，中序遍歷的序列為dgbaechf，則后序遍歷的結(jié)果為（D）。5．設(shè)有nn的帶寬為3的帶狀矩陣A，將其3條對角線上的元素存于數(shù)組B[3][n]中，使得元素B[u][v]=aij，試推導(dǎo)出從（i,j）到 (u,v)的下標變換公式。（）2．KMP算法的特點是在模式匹配時指示主串的指針不會變小。隊空的判別條件為：sqrear==sqfront。r=s。 A．Topnext=p。while(pamp。 r=s。}9．已知兩個單鏈表A和B分別表示兩個集合，其元素遞增排列，編寫算法求出A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲。rc=pa。amp。i=m。R[high]=k。amp。int fch(char c) /*判斷c是否字母*/{if(c=39。 /*刪除多余元素*/ Alast= Alast n。i。（）6．在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。（）11．靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。2．已知一順序表A，其元素值非遞減有序排列，編寫一個算法刪除順序表中多余的值相同的元素。void delete(Seqlist *A,int x,int y) {i=0。z39。 else return (0)。fnum(R[low])) low++。 Ldata[Llast]=x。 pnext=s。}if(pa) rcnext=pa。C= (LNode *)malloc(sizeof(LNode))。 C=Cnext。 /*修改p的freq域*/while(pprior!=Lamp。 D．pnext=Top。8．用不帶頭結(jié)點的單鏈表存儲隊列時，在進行刪除運算時（D）。在實際應(yīng)用中，多為直接遞歸，也常簡稱為遞歸。（）7．所謂取廣義表的表尾就是返回廣義表中最后一個元素。A．二叉樹中任何一個結(jié)點的度都為2 B．二叉樹的度為2C．一棵二叉樹的度可小于2 D．任何一棵二叉樹中至少有一個結(jié)點的度為22．以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，在具有n個結(jié)點的二叉鏈表中（n0），空鏈域的個數(shù)為（C）。A．9 B．10 C．9至566之間 D．10至567之間16．給一個整數(shù)集合{3，5，6，7，9}，與該整數(shù)集合對應(yīng)的哈夫曼樹是（B）。（√）14．在哈夫曼編碼中，出現(xiàn)頻率相同的字符編碼長度也一定相同。7．證明：若哈夫曼樹中有n個葉結(jié)點，則樹中共有2n－1個結(jié)點。若左子樹不空，層次序列中第二個結(jié)點左子樹的根；若左子樹為空，則層次序列中第二個結(jié)點右子樹的根。第一個葉子結(jié)點由指針head指向，遍歷到葉子結(jié)點時，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點的rchild為空。else { hl=Height(rootlchild)。 rootlchild=rootrchild。 t=t*2。 } if(!Empty_Stack(S)){ Pop_Stack(S,r)。這里增加一個標志以表示所有已掃描過的結(jié)點均有左、右孩子，將局部判斷結(jié)果存入CM中，CM表示整個二叉樹是否是完全二叉樹，B為1表示到目前為止所有結(jié)點均有左右孩子。Tdata=A[i]。 !t) return (0)。 r=p。 p=r。 /*若樹為空，返回0*/else { h1=high (tlchild )。 for (i=0 。A．O (nlog2e) B．O (en ) C．O ( elog2n) D．O (n+e)7．含有n個頂點e條邊的無向連通圖，利用Kruskal算法生成最小生成樹，其時間復(fù)雜度為（A）。（√）13．用鄰接矩陣A表示圖，判定任意兩個結(jié)點vi和vj之間是否有長度為m的路徑相連，則只要檢查Am的第i行第j列的元素是否為0即可。A．35/12 B．37/12 C．39/12 D．43/12 7．在有序表{1，3，9，12，32，41，62，75，77，82，95，100}上進行折半查找關(guān)鍵字為82的數(shù)據(jù)元素需要比較（C）次。 v1v3 v2v6v5v45．如圖4所示AOE網(wǎng)：（1）列出各事件的最早、最遲發(fā)生時間；（2）列出各活動的最早、最遲發(fā)生時間；（3）找出該AOE網(wǎng)中的關(guān)鍵路徑，并回答完成該工程需要的最短時間。（√）7．存儲無向圖的鄰接矩陣是對稱的，故只存儲鄰接矩陣的下(或上)三角部分即可。A．n B．2n C．n/2 D．n*n2．n條邊的無向圖的鄰接多重表的存儲中，邊結(jié)點的個數(shù)有（A）。 if(hmax) max=h。 rrchild= rlchild。ttag==1amp。 /*p指向當(dāng)前結(jié)點，r指向p的雙親，q指向要訪問的下一結(jié)點*/if(bt==NULL) return。amp。 /*左孩子入隊列*/if(prchild==NULL) B=0。 else InPost ( in, post,il,m1,pl,pl+m1il, tlchild)。 /*初始化空棧*/ p=T。 top=0。 }}5．給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出將二叉樹中所有結(jié)點的左、右子樹相互交換的算法。 /*中序遍歷右子樹*/prerc