【正文】 6 (2)最小生成樹（prim算法）設(shè)一個無向圖的鄰接矩陣如下圖所示：（1）畫出該圖；（2）畫出從頂點0出發(fā)的深度優(yōu)先生成樹；答案： (1)圖形態(tài) 。 2, 3, 4。（用圖或者表的方式均可）。(!visited[j])) function(j,g)。j++) if((garcs[i][j]==1)amp。 for(j=0。 printf(node:%c\n,gvexs[i])。}graph。 char vexs[N]。O四、程序分析題寫出下面算法的功能。O鄰接表只能用于存儲有向圖，而鄰接矩陣則可存儲有向圖和無向圖。OAOV網(wǎng)是一個帶權(quán)的有向圖。P鄰接表只能用于存儲有向圖，而鄰接矩陣則可存儲有向圖和無向圖。 O一個圖的廣度優(yōu)先搜索樹是惟一的。若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個數(shù)即為頂點vi的 。n個頂點的無向圖最多有 邊。答案：1判定一個有向圖是否存在回路，可以利用 。答案：鄰接矩陣遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，其中 是一個遞歸過程。答案：n1條一個連通圖的生成樹是一個 ，它包含圖中所有頂點，但只有足以構(gòu)成一棵樹的n1條邊。A. 16 B. 4 C. 0 D. 23無向圖中一個頂點的度是指圖中（ ）。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ù)為（ ）。A. 廣度優(yōu)先搜索算法 B. 最小生成樹算法 C. 最短路徑算法 D. 拓?fù)渑判蛩惴?任何一個無向連通圖的最小生成樹（ ）種。A. n B. e C. 2e D. n*e2設(shè)圖的鄰接矩陣為，則該圖為（ ）。A. 從源點到匯點的最長路徑　 B. 從源點到匯點的最短路徑 C. 最長的回路 D. 最短的回路2以下說法正確的是（ ）。A. n(n1)/2 B. n(n1) C. n(n+1)/2 D. n22已知一個有向圖的鄰接表存儲結(jié)構(gòu)如圖所示，根據(jù)深度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是（ ）。且非0的元素個數(shù)1采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（ ）。的元素之和 C. 第i行非165。A. 第i行非165。A. 1/2 B. 1 C. 2 D. 41下列關(guān)于圖遍歷的說法不正確的是（ ）。A. 將鄰接矩陣的第i行刪除 B. 將鄰接矩陣的第i行元素全部置為0 C. 將鄰接矩陣的第i列刪除 D. 將鄰接矩陣的第i列元素全部置為01任一個有向圖的拓?fù)湫蛄校? ）。E2則稱（ ）。A. 入邊 B. 出邊 C. 入邊和出邊 D. 不是出邊也不是入邊1設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個圖，如果V1205。A. 125634　 B. 516234 C. 123456 D. 5216431在無向圖中定義頂點vi與vj之間的路徑為從vi到vj的一個（ ）。A. N2 B. N1 C. N D. N+1鄰接表是圖的一種（ ）。A. 中序遍歷 B. 先序遍歷 C. 后序遍歷 D. 按層次遍歷無向圖的鄰接矩陣是一個（ ）。 A. 廣度優(yōu)先遍歷 B. 拓?fù)渑判? C. 求最短路徑 D. 求關(guān)鍵路徑帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（ ）。A. 完全圖 B. 連通圖 C. 有回路 D. 一棵樹關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（ ）。 } }第七章 圖一、選擇題1對于具有n個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為（ ）。count_preorder(tlchild)。答案：1如下所示的二叉樹，請寫出先序、中序、后序遍歷的序列。a,b,c,d,e，它們的出現(xiàn)頻率依次為9，試構(gòu)造哈夫曼樹，并給出每個字符的哈夫曼編碼。答案：一份電文中有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已知某森林的二叉樹如下所示，試畫出它所表示的森林。答案：(1)樹形態(tài)： (2)帶權(quán)路徑長度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79已知一棵二叉樹的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。答案：二叉樹形態(tài) 試用權(quán)集合{12,4,5,6,1,2}構(gòu)造哈夫曼樹，并計算哈夫曼樹的帶權(quán)路徑長度。請為這8個字母設(shè)計哈夫曼編碼。假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請畫出該二叉樹。 printf(“%d”,pdata)。void function(Bitree *t){ if(p!=NULL){ function(plchild)。 } return(t)。 tleft=t2。 t1=function(btleft)。 else{ t=(Bitree *)malloc(sizeof(Bitree))。 Bitree *function(Bitree *bt){ Bitree *t,*t1,*t2。 else return hr+1。 hr= depth(trchild) 。 int depth(Bitree *t){ if(t==NULL) return 0。 。 void InOrderTraverse(BiTree bt){ if( ){ InOrderTraverse(btlchild)。樹內(nèi)各結(jié)點度的 最大值 稱為樹的度。哈夫曼樹是其樹的帶權(quán)路徑長度 最小 的二叉樹。log2n（√ ）完全二叉樹的某結(jié)點若無左孩子，則它必是葉結(jié)點。log2n（ ）在哈夫曼編碼中，當(dāng)兩個字符出現(xiàn)的頻率相同時，其編碼也相同，對于這種情況應(yīng)做特殊處理。（ ）中序遍歷一棵二叉排序樹的結(jié)點，可得到排好序的結(jié)點序列。A. 3　 B. 4 C. 5 D. 62由權(quán)值為3，6，7，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ A ）。A. 度為2的樹是二叉樹 B. 度為2的有序樹是二叉樹 C. 子樹有嚴(yán)格左右之分的樹是二叉樹 D. 子樹有嚴(yán)格左右之分，且度不超過2的樹是二叉樹樹的先根序列等同于與該樹對應(yīng)的二叉樹的（ ）。 A. 每個結(jié)點至多有兩棵子樹的樹　 B. 哈夫曼樹 C. 每個結(jié)點至多有兩棵子樹的有序樹 D. 每個結(jié)點只有一棵子樹1用順序存儲的方法，將完全二叉樹中所有結(jié)點按層逐個從左到右的順序存放在一維數(shù)組R[1..n]中，若結(jié)點R[i]有左孩子，則其左孩子是（ ）。A. 不發(fā)生改變　 B. 發(fā)生改變 C. 不能確定 D. 以上都不對1假定在一棵二叉樹中，度為2的結(jié)點數(shù)為15，度為1的結(jié)點數(shù)為30，則葉子結(jié)點數(shù)為（ ）個。amp。 A. A*B+C/DE+F B. AB*C+D/EF+ C. ABC+*DEF+/ D. ABCDED*+/+1在線索二叉樹中，t所指結(jié)點沒有左子樹的充要條件是（ ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC1樹最適合用來表示（ C ）。A. 98　 B. 99 C. 50 D. 48表達式a*(b+c)d的后綴表達式是（ B ）。A. 3　 B. 2 C. 4 D. 5若以{4,5,6,7,8}作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶權(quán)路徑長度為（ C ）。 A. 31 B. 32 C. 33 D. 16由二叉樹的前序和后序遍歷序列（ B ）惟一確定這棵二叉樹。A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孫設(shè)一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為（ ）。A. 2k B. 2k1 C. 2k1 D. 2k1用順序存儲的方法，將完全二叉樹中所有結(jié)點按層逐個從左到右的順序存放在一維數(shù)組R[1..N]中，若結(jié)點R[i]有右孩子，則其右孩子是（ B ）。四、綜合題現(xiàn)有一個稀疏矩陣，請給出它的三元組表。二維數(shù)組，可以按照 兩種不同的存儲方式。三、填空題已知二維數(shù)組A[m][n]采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是LOC(A[0][0])，則A[i][j]的地址是___ Loc(A[0][0])+(i*N+j)*k ____。（ ）廣義表的長度是指廣義表中括號嵌套的層數(shù)。（ ）一個稀疏矩陣采用三元組表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把mu和nu的值進行互換，則完成了矩陣轉(zhuǎn)置。A. 由0個或多個原子或子表構(gòu)成的有限序列 B. 至少有一個元素是子表 C. 不能遞歸定義 D. 不能為空表1對廣義表L=((a,b),((c,d),(e,f)))執(zhí)行head(tail(head(tail(L))))操作的結(jié)果是（ ）。A. 二維數(shù)組和三維數(shù)組　 B. 三元組和散列 C. 三元組和十字鏈表 D. 散列和十字鏈表1假設(shè)以三元組表表示稀疏矩陣，則與如圖所示三元組表對應(yīng)的45的稀疏矩陣是（注：矩陣的行列下標(biāo)均從1開始）（ B ）。A. i(i1)/2+j1 B. i(i1)/2+j C. i(i+1)/2+j1 D. i(i+1)/2+j1廣義表A=((a),a)的表頭是（ B ）。A. 表達變得簡單 B. 對矩陣元素的存取變得簡單 C. 去掉矩陣中的多余元素 D. 減少不必要的存儲空間的開銷1設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一個元素，其存儲地址為1，每元素占1個地址空間，則a85的地址為（ ）。A. b,c B. (b,c) C. c D. (c)常對數(shù)組進行兩種基本操作是（ C ）。A. 3 B. 4 C. 7 D. 8采用稀疏矩陣的三元組表形式進行壓縮存儲，若要完成對三元組表進行轉(zhuǎn)置，只要將行和列對換，這種說法（ B ）。A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是子表或原子數(shù)組A[0..5,0..6]的每個元素占5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A[5][5]的地址是（ A ）。A. a B. (a) C. () D. ((a))稀疏矩陣的常見壓縮存儲方法有（ C ）兩種。}答案：串的模式匹配算法第五章 數(shù)組和廣義表一、選擇題設(shè)廣義表L=((a，b，c))，則L的長度和深度分別為（ C ）。 } if(j=tlen) return itlen+1。 }else{ i=ij+1。jtlen) if(sdata[i]==tdata[j]){ i++。 while(islenamp。}答案：.串比較算法寫出算法的功能。i++) if(sdata[i]!=s2data[i]) return s1data[i]s2data[i]。amp。 for(i=0。}}/*listDelete*/寫出下面算法的功能。 } if(j=tlen) return itlen+1 。