【正文】 度，請在空格處將算法補充完整。 int depth(Bitree *t){ if(t==NULL) return 0。 else{ hl=depth(tlchild)。 hr= depth(trchild) 。 if( hlhr ) return hl+1。 else return hr+1。 } }寫出下面算法的功能。 Bitree *function(Bitree *bt){ Bitree *t,*t1,*t2。 if(bt==NULL) t=NULL。 else{ t=(Bitree *)malloc(sizeof(Bitree))。 tdata=btdata。 t1=function(btleft)。 t2=function(btright)。 tleft=t2。 tright=t1。 } return(t)。 }答案：交換二叉樹結(jié)點左右子樹的遞歸算法寫出下面算法的功能。void function(Bitree *t){ if(p!=NULL){ function(plchild)。 function(prchild)。 printf(“%d”,pdata)。}}答案：二叉樹后序遍歷遞歸算法五、綜合題假設(shè)以有序?qū),c表示從雙親結(jié)點到孩子結(jié)點的一條邊，若已知樹中邊的集合為{a,b,a,d,a,c,c,e,c,f,c,g,c,h,e,i,e,j,g,k},請回答下列問題：（1）哪個結(jié)點是根結(jié)點？ a（2）哪些結(jié)點是葉子結(jié)點？ b,d,i,j,f,k,h（3）哪些結(jié)點是k的祖先？ g,c,a（4）哪些結(jié)點是j的兄弟？ i（5）樹的深度是多少？ 4假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請畫出該二叉樹?！局R點：二叉樹前序序列的隱含性質(zhì)：第一個一定是二叉樹的根，后面緊跟著的是其左子樹的根；二叉樹后序序列的隱含性質(zhì)：最后一個一定是二叉樹的根，它的緊前一個是其右子樹的根】答案： 假設(shè)用于通訊的電文僅由8個字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：，，，。請為這8個字母設(shè)計哈夫曼編碼。答案： 已知二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。答案：二叉樹形態(tài) 試用權(quán)集合{12,4,5,6,1,2}構(gòu)造哈夫曼樹，并計算哈夫曼樹的帶權(quán)路徑長度。答案： WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69已知權(quán)值集合為{5,7,2,3,6,9}，要求給出哈夫曼樹，并計算帶權(quán)路徑長度WPL。答案：(1)樹形態(tài)： (2)帶權(quán)路徑長度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79已知一棵二叉樹的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。畫出二叉樹的形態(tài)。答案：一份電文中有6種字符：A,B,C,D,E,F，它們的出現(xiàn)頻率依次為16，5，9，3，30，1，完成問題：（1）設(shè)計一棵哈夫曼樹；（畫出其樹結(jié)構(gòu)）（2）計算其帶權(quán)路徑長度WPL；答案：(1)樹形態(tài)： (2)帶權(quán)路徑長度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129已知某森林的二叉樹如下所示，試畫出它所表示的森林。答案： 有一分電文共使用5個字符。a,b,c,d,e，它們的出現(xiàn)頻率依次為9，試構(gòu)造哈夫曼樹，并給出每個字符的哈夫曼編碼。答案：1畫出與下圖所示的森林相對應(yīng)的二叉樹，并指出森林中的葉子結(jié)點在二叉樹中具有什么特點。答案：1如下所示的二叉樹，請寫出先序、中序、后序遍歷的序列。 答案：先序：FDBACEGIHJ 中序：ABCDEFGHIJ 后序：ACBEDHJIGF六、編程題編寫求一棵二叉樹中結(jié)點總數(shù)的算法。答案：（以先序遍歷的方法為例）void count_preorder(Bitree *t, int *n) { if(t!=NULL){*n++。count_preorder(tlchild)。count_preorder(tlchild)。 } }第七章 圖一、選擇題1對于具有n個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為（ B ）。A. n B. n2 C. n1 D. (n1)2如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是（ B ）。A. 完全圖 B. 連通圖 C. 有回路 D. 一棵樹關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（ A ）。A. 從源點到匯點的最長路徑　 B. 從源點到匯點的最短路徑 C. 最長的回路 D. 最短的回路下面（ B ）可以判斷出一個有向圖中是否有環(huán)（回路）。 A. 廣度優(yōu)先遍歷 B. 拓撲排序 C. 求最短路徑 D. 求關(guān)鍵路徑帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（ B ）。 A. 第i行非無窮的元素之和　 B. 第i列非無窮的元素個數(shù)之和 C. 第i行非無窮且非0的元素個數(shù) D. 第i行與第i列非無窮且非0的元素之和采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的（ B ）。A. 中序遍歷 B. 先序遍歷 C. 后序遍歷 D. 按層次遍歷無向圖的鄰接矩陣是一個（ A ）。A. 對稱矩陣 B. 零矩陣 C. 上三角矩陣 D. 對角矩陣當利用大小為N的數(shù)組存儲循環(huán)隊列時，該隊列的最大長度是（ B ）。A. N2 B. N1 C. N D. N+1鄰接表是圖的一種（ B ）。A. 順序存儲結(jié)構(gòu) B. 鏈式存儲結(jié)構(gòu) C. 索引存儲結(jié)構(gòu) D. 散列存儲結(jié)構(gòu)下面有向圖所示的拓撲排序的結(jié)果序列是（ B ）。A. 125634　 B. 516234 C. 123456 D. 5216431在無向圖中定義頂點vi與vj之間的路徑為從vi到vj的一個（ A ）。A. 頂點序列 B. 邊序列 C. 權(quán)值總和 D. 邊的條數(shù) 1在有向圖的逆鄰接表中，每個頂點鄰接表鏈接著該頂點所有（ A ）鄰接點。A. 入邊 B. 出邊 C. 入邊和出邊 D. 不是出邊也不是入邊1設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個圖，如果V1205。V2,E1205。E2則稱（ A ）。A. G1是G2的子圖 B. G2是G1的子圖 C. G1是G2的連通分量 D. G2是G1的連通分量1已知一個有向圖的鄰接矩陣表示，要刪除所有從第i個結(jié)點發(fā)出的邊，應(yīng)（ B ）。A. 將鄰接矩陣的第i行刪除 B. 將鄰接矩陣的第i行元素全部置為0 C. 將鄰接矩陣的第i列刪除 D. 將鄰接矩陣的第i列元素全部置為01任一個有向圖的拓撲序列（ D ）。 B. 有一個 C. 一定有多個 D. 有一個或多個1在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（ B ）倍。A. 1/2 B. 1 C. 2 D. 41下列關(guān)于圖遍歷的說法不正確的是（ C ）。A. 連通圖的深度優(yōu)先搜索是一個遞歸過程 B. 圖的廣度優(yōu)先搜索中鄰接點的尋找具有“先進先出”的特征 C. 非連通圖不能用深度優(yōu)先搜索法 D. 圖的遍歷要求每一頂點僅被訪問一次1帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入度為A中：（ D ）。A. 第i行非165。的元素之和 B. 第i列非165。的元素之和 C. 第i行非165。且非0的元素個數(shù) D. 第i列非165。且非0的元素個數(shù)1采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（ D ）。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層次遍歷一個具有n個頂點的有向圖最多有（ B ）條邊。A. n(n1)/2 B. n(n1) C. n(n+1)/2 D. n22已知一個有向圖的鄰接表存儲結(jié)構(gòu)如圖所示，根據(jù)深度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是（ C ）。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v22關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（ A ）。A. 從源點到匯點的最長路徑　 B. 從源點到匯點的最短路徑 C. 最長的回路 D. 最短的回路2以下說法正確的是（ B ）。 A. 連通分量是無向圖中的極小連通子圖 B. 強連通分量是有向圖中的極大強連通子圖 C. 在一個有向圖的拓撲序列中若頂點a在頂點b之前，則圖中必有一條弧a,b D. 對有向圖G，如果以任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個頂點，則該圖一定是完全圖2假設(shè)有向圖含n個頂點及e條弧，則表示該圖的鄰接表中包含的弧結(jié)點個數(shù)為（ B ）。A. n B. e C. 2e D. n*e2設(shè)圖的鄰接矩陣為，則該圖為（ A ）。A. 有向圖 B. 無向圖 C. 強連通圖 D. 完全圖2為便于判別有向圖中是否存在回路，可借助于（ D ）。A. 廣度優(yōu)先搜索算法 B. 最小生成樹算法 C. 最短路徑算法 D. 拓撲排序算法2任何一個無向連通圖的最小生成樹（ B ）種。A. 只有一棵　 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在2已知一有向圖的鄰接表存儲結(jié)構(gòu)如圖所示，根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是（ B ）。12345324524^^^^^A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v22對于一個有向圖，若一個頂點的入度為k1,、出度為k2，則對應(yīng)鄰接表中該頂點單鏈表中的結(jié)點數(shù)為（ B ）。A. k1　 B. k2 C. k1+k2 D. k1k2一個具有8個頂點的有向圖中，所有頂點的入度之和與所有頂點的出度之和的差等于（ C ）。A. 16 B. 4 C. 0 D. 23無向圖中一個頂點的度是指圖中（ B ）。A. 通過該頂點的簡單路徑數(shù) B. 與該頂點相鄰接的頂點數(shù) C. 與該頂點連通的頂點數(shù) D. 通過該頂點的回路數(shù)二、填空題n個頂點的連通圖至少有 邊。答案：n1條一個連通圖的生成樹是一個 ，它包含圖中所有頂點，但只有足以構(gòu)成一棵樹的n1條邊。答案：極小連通子圖一個圖的 表示法是惟一的。答案：鄰接矩陣遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，其中 是一個遞歸過程。答案：深度優(yōu)先搜索在無向圖G的鄰接矩陣A中，若A[i][j]等于1，則A[j][i]等于 。答案：1判定一個有向圖是否存在回路，可以利用 。答案：拓撲排序 已知一個圖的鄰接矩陣表示，計算第i個結(jié)點的入度的方法是 。答案：第i列上非無窮元素的個數(shù)之和 n個頂點的無向圖最多有 邊。答案：n*(n1)/2 已知一個圖的鄰接矩陣表示，刪除所有從第i個結(jié)點出發(fā)的邊的方法是 。答案：將鄰接矩陣的第i行元素全部置為0. 若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個數(shù)即為頂點vi的 。答案：出度三、判斷題圖的連通分量是無向圖的極小連通子圖。 錯一個圖的廣度優(yōu)先搜索樹是惟一的。錯圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。對鄰接表只能用于存儲有向圖，而鄰接矩陣則可存儲有向圖和無向圖。錯存儲圖的鄰接矩陣中，