【正文】 e f / 13．畫出和下列已知序列對(duì)應(yīng)的樹T：樹的先根次序訪問序列為：GFKDAIEBCHJ；樹的后根訪問次序?yàn)椋篋IAEKFCJHBG。若左子樹不空，層次序列中第二個(gè)結(jié)點(diǎn)左子樹的根；若左子樹為空，則層次序列中第二個(gè)結(jié)點(diǎn)右子樹的根。它們?cè)陔娢闹谐霈F(xiàn)的頻度分別為{,},（1）為這7個(gè)字母設(shè)計(jì)哈夫曼編碼。二叉樹結(jié)點(diǎn)的數(shù)目＝0 當(dāng)二叉樹為空左子樹結(jié)點(diǎn)數(shù)目＋右子樹結(jié)點(diǎn)數(shù)目＋1 當(dāng)二叉樹非空int count(BiTree root){ if (root==NULL) return (0)。【提示】這是一個(gè)非常典型的基于二叉樹遍歷算法，通過遍歷找到各個(gè)葉子結(jié)點(diǎn)，因?yàn)椴徽撉靶虮闅v、中序遍歷和后序遍歷，訪問葉子結(jié)點(diǎn)的相對(duì)順序都是相同的，即都是從左至右。第一個(gè)葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時(shí)，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。amp。 pre=T。 }3．給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出求二叉樹的深度的算法。else { hl=Height(rootlchild)。} }4．給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試求二叉樹各結(jié)點(diǎn)的層數(shù)。fun(rootlchild,n+1)。void Exchange(BiTree root) { BiTNode *p。 rootlchild=rootrchild。對(duì)順序存儲(chǔ)結(jié)構(gòu)的二叉樹進(jìn)行先序遍歷，與二叉鏈表存放二叉樹的遍歷策略類似。 if(n1) return。amp。 t=t*2。 t=t*2+1。當(dāng)找到值為x的結(jié)點(diǎn)時(shí)，棧中存放的就是其祖先結(jié)點(diǎn)，依次打印各結(jié)點(diǎn)的值。 printf(qdata)。 } if(!Empty_Stack(S)){ Pop_Stack(S,r)。【提示】根據(jù)后序遍歷和中序遍歷的特點(diǎn)，采用遞歸算法實(shí)現(xiàn)。 while (in[m]!=post [pr] ) m++。 else InPost (in,post,m+1,ir,prir+m,pr1,trchild)。這里增加一個(gè)標(biāo)志以表示所有已掃描過的結(jié)點(diǎn)均有左、右孩子，將局部判斷結(jié)果存入CM中，CM表示整個(gè)二叉樹是否是完全二叉樹，B為1表示到目前為止所有結(jié)點(diǎn)均有左右孩子。 if (T!=NULL) { In_Queue(Q,T)。 /*CM=0表示不是完全二叉樹*/} else {CM=B。 /*右孩子入隊(duì)列*/}} return(CM)。Tdata=A[i]。else Trchild=Create(A,2*i+1)?！咎崾尽績煽每斩鏄浠騼H有根結(jié)點(diǎn)的二叉樹相似；對(duì)非空二叉樹，可判左右子樹是否相似，采用遞歸算法。else if(!s amp。 !t) return (0)?！咎崾尽坑媚孓D(zhuǎn)鏈的方法遍歷二叉樹，不需要附加的?？臻g，而是在遍歷過程中沿結(jié)點(diǎn)的左右子樹下降時(shí)，臨時(shí)改變結(jié)點(diǎn)lchild或者rchild的值，使之指向雙親，從而為以后的上升提供路徑，上升時(shí)再將結(jié)點(diǎn)的lchild或者rchild恢復(fù)。} Bnode, *Btree。 r= NULL: while( p) { Visit(p)。 r=p。 r=p。ttag==0) || (ramp。rrchild==NULL)) { if(ramp。 p=r。 rlchild=p。else { rtag=0。 p=q。 /*若樹為空，返回0*/else { h1=high (tlchild )?！咎崾尽坎捎眠f歸算法實(shí)現(xiàn)。p=pnextchild。} return(max+1)。 for (i=0 。 h=1。 } return(maxh) 。A．有向圖 B．無向圖 C．AOV網(wǎng) D．AOE網(wǎng)4．最短路徑的生成算法可用（C）。A．O (nlog2e) B．O (en ) C．O ( elog2n) D．O (n+e)7．含有n個(gè)頂點(diǎn)e條邊的無向連通圖，利用Kruskal算法生成最小生成樹，其時(shí)間復(fù)雜度為（A）。A．8 B．9 C．10 D．11 判斷題1．求最小生成樹的Prim算法在邊較少、結(jié)點(diǎn)較多時(shí)效率較高。（）5．任何有向網(wǎng)絡(luò)（AOV網(wǎng)絡(luò)）拓?fù)渑判虻慕Y(jié)果是唯一的。（）9．任何無向圖都存在生成樹。（√）13．用鄰接矩陣A表示圖，判定任意兩個(gè)結(jié)點(diǎn)vi和vj之間是否有長度為m的路徑相連，則只要檢查Am的第i行第j列的元素是否為0即可。 【解答】（1）每個(gè)頂點(diǎn)的入度和出度：頂點(diǎn)1（2，1）、頂點(diǎn)2（2，2）、頂點(diǎn)3（1，3）、頂點(diǎn)4（3，0）、頂點(diǎn)5（2，3）、頂點(diǎn)6（1，2）。4．設(shè)有向圖G如圖3所示，試畫出圖G的十字鏈表結(jié)構(gòu)，并寫出圖G的兩個(gè)拓?fù)湫蛄小．n B．1 C．n+1 D．n13．順序查找適用于存儲(chǔ)結(jié)構(gòu)為（C）的線性表。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}上進(jìn)行折半查找關(guān)鍵字為82的數(shù)據(jù)元素需要比較（C）次。A．8 B．3 C．5 D．99．散列函數(shù)有一個(gè)。當(dāng)前表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7。A．O(log２n2) B．O(nlog２n) C．O(n) D．O(log２n)5．適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（D）。 v1v3 v2v6v5v45．如圖4所示AOE網(wǎng)：（1）列出各事件的最早、最遲發(fā)生時(shí)間；（2）列出各活動(dòng)的最早、最遲發(fā)生時(shí)間；（3）找出該AOE網(wǎng)中的關(guān)鍵路徑，并回答完成該工程需要的最短時(shí)間?！窘獯稹浚?）該圖的鄰接矩陣：0 1 1 0 0 0 01 0 1 0 0 0 01 0 0 1 0 0 00 1 1 0 1 1 00 0 0 1 0 0 10 0 0 1 0 0 10 0 0 0 1 1 0（2）該圖的鄰接表：0v10 2 ^3245 ^36 ^12 ^0 2 ^36 ^4 5 ^1v22v33v44v55v66v7（3）該圖的多重鄰接表：v1v2v3v4v5v6v7010 ^2 31 ^32 ^343 ^564 ^6 ^5 ^ （4）從v1出發(fā)的“深度優(yōu)先”遍歷序列：v1v2v4v3v5v7v6（5）從v1出發(fā)的“廣度優(yōu)先”遍歷序列：v1v2v3v4v5v6v73．用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否有關(guān)？【解答】設(shè)圖的頂點(diǎn)個(gè)數(shù)為n(n≥0)，則鄰接矩陣元素個(gè)數(shù)為n2，即頂點(diǎn)個(gè)數(shù)的平方。（）15．AOE網(wǎng)中一定只有一條關(guān)鍵路徑。（√）11．連通分量是無向圖中的極小連通子圖。（√）7．存儲(chǔ)無向圖的鄰接矩陣是對(duì)稱的，故只存儲(chǔ)鄰接矩陣的下(或上)三角部分即可。（√）3．用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。A．從源點(diǎn)到匯點(diǎn)的最長路徑 B．從源點(diǎn)到匯點(diǎn)的最短路徑 C．最長的回路 D．最短的回路9．下面關(guān)于求關(guān)鍵路徑的說法不正確的是（C）。A．v0, v3, v2, v1 B．v0, v1, v2, v3 C．v0, v2, v1, v3 D．v0, v1, v3, v2（2）從頂點(diǎn)V0出發(fā)進(jìn)行廣度優(yōu)先搜索，經(jīng)歷的結(jié)點(diǎn)順序?yàn)椋―）。A．n B．2n C．n/2 D．n*n2．n條邊的無向圖的鄰接多重表的存儲(chǔ)中，邊結(jié)點(diǎn)的個(gè)數(shù)有（A）。 h++。i++) { if (t[i].parent==1 ) h=1?！咎崾尽繌拿恳粋€(gè)結(jié)點(diǎn)開始，從下向上搜索至根結(jié)點(diǎn)，記錄結(jié)點(diǎn)的層次數(shù)，其中的最大值就是樹的深度。 if(hmax) max=h。 /*若根結(jié)點(diǎn)沒有子樹*/else { p=t[i].firstchild。 /*h2為t的兄弟子樹的深度*/ return(max(h1+1,h2))?！咎崾尽坎捎眠f歸算法實(shí)現(xiàn)。 rrchild= rlchild。 r=q。} /*從右子樹回來*/else { rtag=0。ttag==0) { q=rrchild。ttag==1amp。 } else { /*上升*/whle((ramp。 } else if(prchild) /*下降進(jìn)入右子樹*/{ q=prchild。 q=plchild。 /*p指向當(dāng)前結(jié)點(diǎn)，r指向p的雙親，q指向要訪問的下一結(jié)點(diǎn)*/if(bt==NULL) return。 int tag。amp。 t || s amp。amp。 }11．編寫算法判定兩棵二叉樹是否相似。else Tlchild=Create(A,2*i)。BiTree Create(dataype A[],int i)/*n個(gè)結(jié)點(diǎn)的完全二叉樹存于一維數(shù)組A中，據(jù)此建立以二叉鏈表表示的完全二叉樹,初始調(diào)用時(shí),i=1*/{ BiTree T。 /*左孩子入隊(duì)列*/if(prchild==NULL) B=0。 if(plchild==NULL) { B=0。 /*初始化隊(duì)列Q*/ B=1。【提示】根據(jù)完全二叉樹的定義可知，對(duì)完全二叉樹按照從上到下，從左到右的次序遍歷應(yīng)滿足：①若某結(jié)點(diǎn)沒有左孩子，則一定無右孩子；②若某結(jié)點(diǎn)缺（左或右）孩子，則其所有后繼一定無孩子。 else InPost ( in, post,il,m1,pl,pl+m1il, tlchild)。 tdata=post[pr]。 } else return。} else{ Push_Stack(S,p)。 /*初始化空棧*/ p=T。【提示】對(duì)二叉樹進(jìn)行先序非遞歸遍歷，查找值為x的結(jié)點(diǎn)。 else { top。 stack[top]=t。 top=0。void PreOrder (datatype data[n+1]) /*0號(hào)單元未用*/ { int stack[n] 。}}6．一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹采用順序結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)非遞歸算法對(duì)其進(jìn)行先序遍歷。Exchange(rootrchild)。 }}5．給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出將二叉樹中所有結(jié)點(diǎn)的左、右子樹相互交換的算法。二叉樹結(jié)點(diǎn)的層次數(shù)＝1 當(dāng)結(jié)點(diǎn)為根結(jié)點(diǎn)其雙親結(jié)點(diǎn)的層次數(shù)＋1 當(dāng)結(jié)點(diǎn)非根結(jié)點(diǎn)void fun (BiTree root, int n){ if (t==NULL) return。if (hlhr) return (hl+1)。int Height(BiTree root) { int hl,hr。 /*中序遍歷右子樹*/prerchild=NULL。 pre=T。 /*全局變量*/LinkList InOrder(BiTree T) /*中序遍歷二叉樹T，將葉子結(jié)點(diǎn)從左到右鏈成一個(gè)單鏈表，表頭指針為head*/{ if(T) { InOrder(Tlchild)。這里使用中序遞歸遍歷。 }2．請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，要求該算法把二叉樹的葉結(jié)點(diǎn)按從左至右的順序鏈成一個(gè)單鏈表。等長編碼的平均長度：*3+*3+*3+*3+*3+*3+*3=3哈夫曼編碼：*2+*3+*3+*4+*3+*2+*4=哈夫曼編碼比等長編碼使電文總長壓縮了：1 算法設(shè)計(jì)題1．給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出求二叉樹結(jié)點(diǎn)的數(shù)目的算法。層次序列的