1、樹、圖 習題一、選擇題 1 已知一算術表達式的中綴形式為 A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為( D )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE 2 一個具有1025個結點的二叉樹的高h為（ C ）A11 B10 C11至1025之間 D10至1024之間 3 二叉樹的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷: HFIEJKG 。該二叉樹根的右子樹的根是： （ C ）A、 E B、 F C、 G D、 H 4 引入二叉線索樹的目的是（ A ）A加快查找結點的前驅或后繼的速度 B為了能在二叉樹中方

2、便的進行插入與刪除C為了能方便的找到雙親 D使二叉樹的遍歷結果唯一 5 設森林F中有三棵樹，第一，第二，第三棵樹的結點個數分別為M1，M2和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數是（ D ）。AM1 BM1+M2 CM3 DM2+M3 6 有n個葉子的哈夫曼樹的結點總數為（ D ）。A不確定 B2n C2n+1 D2n-1 7 一個有n個結點的圖，最少有（ B ）個連通分量，最多有（ D ）個連通分量。A0 B1 Cn-1 Dn 8 無向圖G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，對該

3、圖進行深度優先遍歷，得到的頂點序列正確的是（ D ）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b 9 已知有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>,G的拓撲序列是（ A ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5

4、,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V7二、填空題 1 8層完全二叉樹至少有_128_個結點，擁有100個結點的完全二叉樹的最大層數為_7_。 2 設有N個結點的完全二叉樹順序存放在向量A1:N中，其下標值最大的分支結點為_ëN/2û _。 3 有數據WG=7，19，2，6，32，3，21，10，則所建Huffman樹的樹高是_6_，帶權路徑長度WPL為_261_。 4 G是一個非連通無向圖，共有28條邊，則該圖至少有_9_個頂點。 5 為了實現圖的廣度優先搜索，除了一個標志數組標志已訪問的圖的結點外，還需_隊列存放被訪問

5、的結點以實現遍歷。 6 Prim（普里姆）算法適用于求_邊稠密 的網的最小生成樹；kruskal（克魯斯卡爾）算法適用于求_邊稀疏_的網的最小生成樹。三、算法題 1 將二叉樹bt中每一個結點的左右子樹互換的C語言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進隊，出隊和判別隊列是否為空的函數，請填寫算法中得空白處，完成其功能。typedef struct node int data ; struct node *lchild, *rchild; btnode; void EXCHANGE(btnode *bt)btnode *p, *q; if (bt)ADDQ(Q

6、,bt); while(!EMPTY(Q) p=DELQ(Q); q=(1) p->rchild _; p->rchild=(2) p->lchild _; (3) p->lchild _=q;if(p->lchild) (4) ADDQ(Q,p->lchild)_; if(p->rchild) (5) ADDQ(Q,p->rchild)_; 2 二叉樹采用二叉鏈表存儲，試設計一個算法計算一棵給定二叉樹的葉子結點數。答： int leafs ( bitree t) int numleft,numright; If ( t = NULL ) ret

7、urn 0; Else if ( t -> lchild = NuLL && t -> rchild = NuLL ) return 1; Else numleft = leafs ( t -> lchild ); numright = leafs ( t -> rchild ); Return ( numleft + numright ); /else / leafs3 二叉樹采用二叉鏈表存儲，試設計一個算法計算二叉樹的深度。答： int depth ( bitree t) if ( !t ) depthval = 0; Else depthleft

8、= depth ( t -> lchild ); Depthright = depth ( t -> rchild ); Depthval = 1 + ( depthleft > depthright ? depthleft : depthright ); / else Retutn depthval; / depth4 二叉樹采用二叉鏈表存儲，試寫出對二叉樹的先序遍歷非遞歸算法。答：void pretraverse ( bitree t ) initstack ( s ); If ( t ) push ( s , t ); While ( ! stackempty ( s

9、) pop ( s , p ); Visit ( p -> data ); If ( p -> rchild != NuLL ) push ( s , p -> rchild ); If ( p -> lchild ) push ( s , p -> lchild ); / while / if / pretraverse125643184128102025155237675 試寫出用普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法構造下圖的一棵最小支撐（或生成）樹的過程。 6 已知AOE網中頂點v1、v2、v3、v4、v5、v6和v7分別表示7個事件，有

10、向線段a1、a2、a3、a4、a5、a6、a7、a8、a9和a10分別表示10個活動，請分別計算出各事件的最早發生時間、各事件的最晚發生時間、各活動的最早開始時間、各活動的最晚開始時間、各活動的松弛時間，分別填表。用頂點序列表示出關鍵路徑，給出關鍵活動。其中：a13，a26，a32，a44，a52，a61，a73，a81，a93，a104事 件V1V2V3V4V5V6V7最早發生時間ve03267510最晚發生時間vl03367610活 動a1a 2a 3a 4a 5a 6a 7a 8a 9a 10最早開始時間e0003322675最晚開始時間l0013453676松弛時間le0010131001關鍵路徑： v1 v2 v5 v7 和 v1 v4 v5 v7 關鍵活動：a1 a2 a4 a8 a97 求解下面有向圖的有關問題。 （1）判斷此有向圖是否有