習(xí)題答案1分析

1、1已知一算術(shù)表達式的中綴形式為A+B*C-D/E，后綴形式為 ABC*+DE/-,其前綴形式為 ） A . -A+B*C/DE B . -A+B*CD/E C. -+*ABC/DE D. -+A*BC/DE 參考答案：D 3.棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）。 A . 250 B . 500 C . 254 D . 505 E .以上答案都不對 參考答案：E 非葉結(jié)點數(shù)5; 哈夫曼樹見下圖，其帶權(quán)路徑長度wpl=51。 34. 一棵深度為H的滿k叉樹有如下性質(zhì)： 第H層上的結(jié)點都是葉子結(jié)點， 其余各層上每個 結(jié)點都有k棵非空子樹。若按層次順序從1開始對全部結(jié)點編號，問：

2、(1)第1層上有多少 個結(jié)點？ (2)編號為p的結(jié)點的第1個孩子結(jié)點(若存在)的編號是多少？(3)編號為p的結(jié) 點的雙親結(jié)點(若存在)的編號是多少？ 參考答案： (1) ki4個 (1+(p 1)U)+i p+k-2i (3) J (pF)】 -k 一 2給出算法將二叉樹表示的表達式二叉樹按中綴表達式輸出，并加上相應(yīng)的括號。 參考答案： 本題是將符號算術(shù)表達式用二叉樹表示的逆問題，即將二叉樹表示的表達式還原成原表 達式。二叉樹的中序遍歷序列與原算術(shù)表達式基本相同， 差別僅在于二叉樹表示中消除了括 號。將中序序列加上括號就恢復(fù)原貌。當(dāng)根結(jié)點運算符優(yōu)先級高于左子樹(或右子樹) 根結(jié) 點運算符時，就

3、需要加括號。 int Precede(char optr1, char optr2) / 比較運算符級別高低， optr1 級別高于 optr2 時返回 1，相等時返回 0，低于時返回 -1 switch(optr1) case + :case - :if(optr2= + |optr2= - )return(0);else return(-1); case * :case / :if(optr1= * |optr2= / )return(0);else return(1); void InorderExp (BiTree bt) /輸出二叉樹表示的算術(shù)表達式，設(shè)二叉樹的數(shù)據(jù)域是運算符或變量名

4、 int bracket; if(bt) if(bt-lchild!=null) bracket=Precede(bt-data,bt-lchild-data)/ 比較雙親與左子女運算符優(yōu)先級 if(bracket=1) printf( ( ); InorderExp(bt-lchild); / 輸出左子女表示的算術(shù)表達式 if(bracket=1)printf( ) ); /加上右括號 printf(bt-data);/ 輸出根結(jié)點 if(bt-rchild!=null)/輸出右子樹表示的算術(shù)表達式 bracket=Precede(bt-data,bt-rchild-data) if (br

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

6、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í)題答案 D. n* ( n-1) 5. n個結(jié)點的完全有向圖含有邊的數(shù)目（）。 A . n*nB. n （n+1）C. n/2 參考答案：D 15設(shè)圖如右所示, ，在下面的 5個序列中，符合深度優(yōu)先遍歷的序列 參考答案: 有（ ）個。 a e b d f ca c f d e ba e d f c ba e f d c b A

7、 . 5個B . 4個C. 3個 參考答案：D 21 已知有向圖 G=（V,E）, 其中 V=V 1,V2,V3,V4,V5,V6,V7, A . V1,V3,V4,V6,V2,V5,V7 C. V1,V3,V4,V5,V2,V6,V7 參考答案：A 24.在有向圖G的拓撲序列中，若頂點 A . G 中有弧 C. G中沒有弧 參考答案：D 26.關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（ A .從源點到匯點的最長路徑 C.最長回路 參考答案：A E=, , , G 的拓 撲序列是( )o B . V1,V3,V2,V6,V4,V5,V7 D . V1,V2,V5,V3,V4,V6,V7 Vi在頂點Vj之前，則

8、下列情形不可能出現(xiàn)的是（）o B . G中有一條從 Vi到Vj的路徑 D. G中有一條從 Vj到Vi的路徑 ） B .從源點到匯點的最短路徑 D .最短回路 37.設(shè)有無向網(wǎng)如下，寫出其鄰接矩陣, 并在此基礎(chǔ)上按普里姆算法求最小生成樹。 closedge closedge a 0 0 0 0 b 1 0 4 1 0 4 c 2 0 3 2 0 0 d 3 0 co 3 2 5 e 4 0 co 4 0 co f 5 0 co 5 0 8 h 6 ij co 6 0 OO h 7 0 co .7 2 5 clasedge closedge a 0 0 0 0 b 1 0 0 1 0 0 c 2

9、0 0 2 0 0 d 3 2 0 3 2 0 e 4 3 7 4 3 7 f 5 3 6 5 3 6 6 3 5 6 ：? 5 h 7 3 4 i. 3 0 鄰接矩陣: 0 0 1 0 0 2 0 0 3 2 5 4 1 9 5 0 OO 6 0 co 7 2 5 closedge closedge 0 0 0 0 1 0 0 1 0 0 2 0 0 2 0 0 3 2 0 3 2 0 4 3 7 4 5 3 5 6 2 5 “ （2）以結(jié)點V1出發(fā)廣度遍歷圖G所得的結(jié)點序列; （3）從結(jié)點V1到結(jié)點V8的最短路徑； （4）從結(jié)點V1到結(jié)點V8的關(guān)鍵路徑。 參考答案： （1） V1,V2,V

10、3,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 到 V8 的關(guān)鍵路徑是 V1-V6-V5-V3-V8，長 97。 29.試?yán)肈ijkstra算法求下圖中從頂點a到其他個頂點間的最短路徑，寫出執(zhí)行算法過程 中各步的狀態(tài)。 參考答案： 頂點a到頂點b, c, d, e, f, g間的最短路徑分別是 15, 2, 11, 10, 6, 13。 34.對圖示的AOE網(wǎng)絡(luò)，計算各活動弧的e(a)和l(ai)的函數(shù)值，各事件(頂點)的 ve (Vj) 和vl (Vj)的

11、函數(shù)值，列出各條關(guān)鍵路徑。 0 12 H 21 (1)畫出其鄰接矩陣存儲；(2)寫出圖的所有強連通 7.有向圖的鄰接表存儲如下，要求： 分量；(3)寫出頂點a到頂點i的全部簡單路徑。 a h e- d A h A i c s f 1 4 8 9 2 4 5 匚 n E 9 2 6 A 3 7 參考答案: (1) (2) (3) :abcdefghi) (b，e，i，f，c，g) 略。(注：鄰接矩陣下標(biāo)按字母升序 強連通分量：(a), (d),( h), 頂點 a到頂點 i 的簡單路徑：(a-b-e-i),( a-c-g-i ) ,( a-c-b-e-i )。 20.設(shè)有一個 其存儲地址為 10階的對稱矩陣A，米用壓縮存儲方式，以行序為主存儲，an為第一兀素, 個地址空間，貝Ua85的地址為( C. 18 D. 40 1，每個元素占 B. 33 A. 13 參考答案：B 23.將一個 A1.100 , 素A 66,65 (即該元素下標(biāo) 1.100的三對角矩陣，按行優(yōu)先存入一維數(shù)組 i=66，j=65)，在B數(shù)組中的位置 K為( B1 - 298中，A 中元 )。 數(shù)組 A198B 195C197D196 參考答