習(xí)題答案-(1)分析

1、1 .已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E ,后綴形式為 ABC*+DE/-,其前綴形式為（ ）。A. -A+B*C/DE B. -A+B*CD/E C. -+*ABC/DE D. -+A*BC/DE參考答案：D3. 一棵完全二叉樹上有1001個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是（）。A. 250 B. 500 C. 254 D. 505 E.以上答案都不對參考答案：E8.在一棵三元樹中度為3的結(jié)點(diǎn)數(shù)為2個，度為2的結(jié)點(diǎn)數(shù)為1個，度為1的結(jié)點(diǎn)數(shù)為2個，則度為0的結(jié)點(diǎn)數(shù)為（）個。A. 4 B. 5 C. 6 D. 7參考答案：C10.具有10個葉結(jié)點(diǎn)的二叉樹中有（）個度為2的結(jié)點(diǎn)。A. 8 B

2、. 9 C. 10 D. 11參考答案：B）種不同的二叉樹。D. 553.由3個結(jié)點(diǎn)可以構(gòu)造出（A. 2 B. 3 C. 4參考答案：D47.引入二叉線索樹的目的是（）。A .加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B.為了能在二叉樹中方便的進(jìn)行插入與刪除C.為了能方便的找到雙親D.使二叉樹的遍歷結(jié)果唯一19.將如下由三棵樹組成的森林轉(zhuǎn)換為二叉樹。M反過來，將一個二叉樹轉(zhuǎn)化成森林或樹？（注意：轉(zhuǎn)化成森林的結(jié)果和轉(zhuǎn)化成樹的結(jié)果不一樣）21.設(shè)某二叉樹的前序遍歷序列為ABCDEFGGI ,中序遍歷序列為 BCAEDGHFI ,試畫出該二叉樹。參考答案：27.設(shè)二叉樹T的存儲結(jié)構(gòu)如下:12345678910L

3、child00237580101DataJHFDBACEGIRchild0009400000其中Lchild、Rchild分別為結(jié)點(diǎn)的左、右孩子指針域，Data為結(jié)點(diǎn)的數(shù)據(jù)域，若根指針T的值為6,試：（1）畫出二叉樹的邏輯結(jié)構(gòu)；（2）寫出按前序、中序、后序遍歷該二叉樹所得 到的結(jié)點(diǎn)序列；（3）畫出二叉樹的后序線索樹。參考答案：前序序歹U: ABCEDFHGIJ 中序序歹U: ECBHFDJIGA 后序序歹U: ECHFJIGDBA31 .假定用于通訊的電文僅有8個字母C1, C2,，C8組成，各個字母在電文中出現(xiàn)的頻率分別為5, 25, 3, 6, 10, 11, 36, 4,試為這8個字母設(shè)

4、計哈夫曼編碼樹。參考答案：c8 cl哈夫場國網(wǎng)科各字母編碼如下：c1:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:11 c8:0011注意雖然哈夫曼樹的帶權(quán)路徑長度是唯一的，但形態(tài)不唯一。33 .設(shè)T是一棵二叉樹，除葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)的度皆為 2,若T中有6個葉結(jié)點(diǎn)，試問:機(jī)T的最大深度和最小可能深度分別是多少？（2）T中共有多少非葉結(jié)點(diǎn)？（3）若葉結(jié)點(diǎn)的權(quán)值分別為1、2、3、4、5、6,請構(gòu)造一棵哈曼夫樹，并計算該哈曼夫樹的帶權(quán)路徑長 度 wpl。參考答案：（1）最大深度6,最小深度4;（2）非葉結(jié)點(diǎn)數(shù)5;（3）哈夫曼樹見下圖，其帶權(quán)路徑長度wp

5、l=51。34 . 一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個結(jié)點(diǎn)都有k棵非空子樹。若按層次順序從1開始對全部結(jié)點(diǎn)編號，問：（1）第1層上有多少個結(jié)點(diǎn)？ （2）編號為p的結(jié)點(diǎn)的第1個孩子結(jié)點(diǎn)（若存在）的編號是多少？（3）編號為p的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號是多少？ 參考答案：ki個(2) ( 1 +(P-D * k ) + Ip + k -2：一 k2.給出算法將二叉樹表示的表達(dá)式二叉樹按中綴表達(dá)式輸出，并加上相應(yīng)的括號。參考答案：本題是將符號算術(shù)表達(dá)式用二叉樹表示的逆問題，即將二叉樹表示的表達(dá)式還原成原表 達(dá)式。 二叉樹的中序遍歷序列與原算術(shù)表達(dá)式基本相

6、同， 差別僅在于二叉樹表示中消除了括號。將中序序列加上括號就恢復(fù)原貌。當(dāng)根結(jié)點(diǎn)運(yùn)算符優(yōu)先級高于左子樹(或右子樹) 根結(jié) 點(diǎn)運(yùn)算符時，就需要加括號。int Precede(char optr1, char optr2)/ 比較運(yùn)算符級別高低， optr1 級別高于 optr2 時返回 1，相等時返回0，低于時返回-1switch(optr1)case +:case -:if(optr2= +|optr2= - )return(0);else return(-1);case * :case /:if(optr1= *|optr2= / )return(0);else return(1); void

7、 InorderExp (BiTree bt) /輸出二叉樹表示的算術(shù)表達(dá)式，設(shè)二叉樹的數(shù)據(jù)域是運(yùn)算符或變量名 int bracket;if(bt)if(bt-lchild!=null) bracket=Precede(bt-data,bt-lchild-data)/ 比較雙親與左子女運(yùn)算符優(yōu)先級 if(bracket=1) printf( ( ); InorderExp(bt-lchild);/ 輸出左子女表示的算術(shù)表達(dá)式if(bracket=1)printf( ) );/加上右括號 printf(bt-data);/輸出根結(jié)點(diǎn)if(bt-rchild!=null)/輸出右子樹表示的算術(shù)表達(dá)

8、式bracket=Precede(bt-data,bt-rchild-data) if (bracket=1)printf( “ (” );/右子女級別低，加括號InorderExp (bt-rchild); if(bracket=1)printf( “ )” ); / 結(jié)束 Inorder Exp4 有n 個結(jié)點(diǎn)的完全二叉樹存放在一維數(shù)組 A1.n 中，試據(jù)此建立一棵用二叉鏈表表示的二叉樹，根由 tree 指向。 參考答案： 方法一： BiTree Creat(ElemType A,int i)/n 個結(jié)點(diǎn)的完全二叉樹存于一維數(shù)組 A 中， 本算法據(jù)此建立以二叉鏈表表示的完全二叉 樹BiTr

9、ee tree;if (idata=Ai;if(2*in) tree-lchild=null;else tree-lchild=Creat(A,2*i);if(2*i+1n) tree-rchild=null;else tree-rchild=Creat(A,2*i+1); return (tree); /Creat 初始調(diào)用時i=1 。圖的部分習(xí)題答案5 . n個結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目()。A. n*nB. n (n+1) C. n/2D. n* (n-1)參考答案：D15.設(shè)圖如右所示,在下面的5個序列中，符合深度優(yōu)先遍歷的序列有（）個。a e b d f ca c f d e ba

10、 e d f c b a e f d c bA. 5個B. 4個C. 3個參考答案：Da e f d b cD. 2個21. 已知有向圖 G=(V,E), 其中V=V 1,V2,V3,V4,V5,V6,V7,E=, , , G 的拓 撲序列是（）。A. V1,V3,V4,V6,V2,V5,V7C. V1,V3,V4,V5,V2,V6,V7參考答案：A24.在有向圖G的拓?fù)湫蛄兄校繇旤c(diǎn)A . G 中有弧 C. G中沒有弧參考答案：D26.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中(A.從源點(diǎn)到匯點(diǎn)的最長路徑C.最長回路參考答案：AB. V1,V3,V2,V6,V4,V5,V7D. V1,V2,V5,V3,V4,

11、V6,V7Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是()。B . G中有一條從 Vi到Vj的路徑D. G中有一條從 Vj到Vi的路徑)。B.從源點(diǎn)到匯點(diǎn)的最短路徑D.最短回路37.設(shè)有無向網(wǎng)如下，寫出其鄰接矩陣,并在此基礎(chǔ)上按普里姆算法求最小生成樹。參考答案:a0closedge0closedge00b1041o ：4c203200d30co325e40co40 ；cof50co50co_g_60co6廠coh70co72 ：5closedgeclosedgea0000b10010 ；0c200200d320320e437437f536536g6356：5h73473 -0鄰接矩陣：臼434

12、 g 535國55009gQO QO OO00 OO OOoo CO 5最小生成樹:oO55oO7654009QO7QO3ad00oCoCoC63C2oCJHjnaOO5OO2oO60 X：54X：X：60010020。32541950co60co725closedgeclosedge0001001002002003203204374535625.6063Q630730730closedge38.試寫出對如下有向無環(huán)圖進(jìn)行拓?fù)渑判蚩赡艿玫降乃型負(fù)湫蛄小⒖即鸢福好看屋敵鲆粋€入度為0的頂點(diǎn)。abcdcfg、abcdfcg、abcfdeg。39.設(shè)有向網(wǎng)如下，用弗洛伊德算法求圖中各對頂點(diǎn)間的最短

13、路徑。黑力0123005co41co028235 0832oo60D0123005co41co02co2350732760g0123_0057415029235r 不32760參考答案:D(U012300541co02co235073_2_7_J&0D巧01230057415029235073276035.設(shè)有A OE網(wǎng)如下，試求關(guān)鍵路徑。口 n。參考答案:關(guān)鍵路徑 1 : V1fV?f Vf V7關(guān)鍵路徑 2 : Vi一 V3一 V6一 V732.下圖是帶權(quán)的有向圖 G的鄰接表表示法，求：(1)以結(jié)點(diǎn)V1出發(fā)深度遍歷圖 G所得的結(jié)點(diǎn)序列;(2)以結(jié)點(diǎn)V1出發(fā)廣度遍歷圖G所得的結(jié)點(diǎn)序列;(3)

14、從結(jié)點(diǎn)V1到結(jié)點(diǎn)V8的最短路徑；(4)從結(jié)點(diǎn)V1到結(jié)點(diǎn)V8的關(guān)鍵路徑。VIV2V34V5V67V8A26343188A512A33811511820N41567246712650八411n參考答案：(1) V1,V2,V3,V8,V5,V7,V4,V6;(2) V1,V2,V4,V6,V3,V5,V7,V8;(3) V1 到V8最短路徑 56,路徑為 V1-V2-V5-V7-V8;(4) V1 至UV8 的關(guān)鍵路徑是 V1-V6-V5-V3-V8,長 97。29.試?yán)肈ijkstra算法求下圖中從頂點(diǎn)a到其他個頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。2參考答案：頂點(diǎn)a到頂點(diǎn)b, c,

15、 d, e, f, g間的最短路徑分別是 15, 2, 11, 10, 6, 13。34.對圖示的AOE網(wǎng)絡(luò)，計算各活動弧的 e(a)和l(ai)的函數(shù)值，各事件(頂點(diǎn))的 ve (Vj) 和vl (Vj)的函數(shù)值，列出各條關(guān)鍵路徑。7.有向圖的鄰接表存儲如下，要求： (1)畫出其鄰接矩陣存儲；(2)寫出圖的所有強(qiáng)連通 分量；(3)寫出頂點(diǎn)a到頂點(diǎn)i的全部簡單路徑。參考答案：(1)略。(注：鄰接矩陣下標(biāo)按字母升序：abcdefghi)(2)強(qiáng)連通分量：(a) , (d), ( h) , (b, e, i, f, c, g)(3)頂點(diǎn)的頂點(diǎn) i 的簡單路徑:(a-b-e-i) , ( a-c-g-i ) , ( a-c-b-e-i )。數(shù)組20.設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序?yàn)橹鞔鎯Γ?1為第一元素,其存儲地址為1,每個元素占一個地址空間，則a85的地址為()。A. 13 B. 33 C. 18 D. 40參考答案：B23.將一個 A1.100 , 1.100的三對角矩陣，按行優(yōu)先存入一維數(shù)組B1 - 298中，A中元素A 66,65 (