數(shù)據(jù)結(jié)構(gòu) 考前復(fù)習(xí)3

1、第四章 串一、選擇題下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（ B ）串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)設(shè)有兩個(gè)串p和q,其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（C ）求子串B.聯(lián)接C.匹配D.求串長(zhǎng)串的長(zhǎng)度是指（B ）串中所含不同字母的個(gè)數(shù)B.串中所含字符的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)二、填空題 空格串是指 由空格字符（ASCII值32）所組成的字符串，其長(zhǎng)度等于空格個(gè)數(shù)_。 組成串的數(shù)據(jù)元素只能是_字符。一個(gè)字符串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串。四、應(yīng)

2、用題名詞解釋：串串是零個(gè)至多個(gè)字符組成的有限序列。從數(shù)據(jù)結(jié)構(gòu)角度講，串屬于線性結(jié)構(gòu)。與線性表 的特殊性在于串的元素是字符。描述以下概念的區(qū)別：空格串與空串?？崭袷且粋€(gè)字符，其ASCII碼值是32。空格串是由空格組成的串，其長(zhǎng)度等于空格的 個(gè)數(shù)?？沾遣缓魏巫址拇?，即空串的長(zhǎng)度是零。第六章 樹(shù)和二叉樹(shù)一、選擇題已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為（D ）-A+B*C/DE B. -A+B*CD/EC. -+*ABC/DED. -+A*BC/DE設(shè)樹(shù)T的度為4,其中度為1，2, 3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4, 2, 1，1則T中的葉 子數(shù)為（D

3、 ）A. 5B. 6C. 7D. 8在下述結(jié)論中，正確的是（D ）只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0;二叉樹(shù)的度為2；二叉樹(shù)的左右子樹(shù)可任 意交換；深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)。A.B. C. D.結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子數(shù)個(gè)數(shù)稱為此結(jié)點(diǎn)的度數(shù)的度;樹(shù)中所有結(jié)點(diǎn)的讀的最大值設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為B，它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹(shù)結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是（A ）A. m-nB. m-n-1 C. n+1D.條件不足，無(wú)法確定8.若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（B ）A. 9B. 11C. 15。.不確定設(shè)森

4、林F中有三棵樹(shù)，第一，第二，第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森 林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（D ）。A. M1B. M1+M2 C. M3D. M2+M3具有10個(gè)葉結(jié)點(diǎn)的二叉樹(shù)中有（B ）個(gè)度為2的結(jié)點(diǎn)，A. 8B. 9C. 10D. ll設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為（D ）A.不確定B. 2nC. 2n+1D. 2n-1有n個(gè)葉子的哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為（D ）。A.不確定B. 2nC. 2n+1D. 2n-1有關(guān)二叉樹(shù)下列說(shuō)法正確的是（B ）A.二叉樹(shù)的度為2B. 一棵二叉樹(shù)的度可以小于2二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2 D.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)

5、的度都為2二叉樹(shù)的第I層上最多含有結(jié)點(diǎn)數(shù)為（C ）A. 2iB. 2i-1-1C. 2i-1D. 2i -123.在一棵高度為k的滿二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為（C ）A. 2k-1B. 2kC. 2k-1D. |_log2k+1一棵二叉樹(shù)的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（B ）A. CABDEFGB. ABCDEFG C. DACEFBGD. ADCFEG已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF，則后序遍歷的結(jié) 果為（A ）。A. CBEFDAB. FEDCBA C. CBEDFAD.不定對(duì)于前序遍歷與中序遍歷結(jié)果相同的二叉樹(shù)為（F）;對(duì)于前序遍歷

6、和后序遍歷結(jié)果相同的二叉樹(shù)為（B）。A. 一般二叉樹(shù)B.只有根結(jié)點(diǎn)的二叉樹(shù)C.根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù) 根結(jié)點(diǎn)無(wú)右孩子的二叉樹(shù)E.所有結(jié)點(diǎn)只有左子數(shù)的二叉樹(shù)F.所有結(jié)點(diǎn)只有右 子樹(shù)的二叉樹(shù)一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足（C ）A.所有的結(jié)點(diǎn)均無(wú)左孩子B.所有的結(jié)點(diǎn)均無(wú)右孩子C.只有一個(gè)葉子結(jié)點(diǎn)D.是任 意一棵二叉樹(shù)57.由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的有向樹(shù)？ （ A ）A. 2B. 3C. 4D. 563.下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（B ）。A .0,10,110,1111B .11,10,001,101,0001C. 00,010,0

7、110,1000D. b,c,aa,ac,aba,abb,abc二、判斷題 TOC o 1-5 h z 二叉樹(shù)是度為2的有序樹(shù)。X完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)。X二叉樹(shù)的遍歷結(jié)果不是唯一的.寸二叉樹(shù)的遍歷只是為了在應(yīng)用中找到一種線性次序。寸一個(gè)樹(shù)的葉結(jié)點(diǎn)，在前序遍歷和后序遍歷下，皆以相同的相對(duì)位置出現(xiàn)。寸二叉樹(shù)的前序遍歷并不能唯一確定這棵樹(shù)，但是，如果我們還知道該樹(shù)的根結(jié)點(diǎn)是那一個(gè)，則可以確定這棵二叉樹(shù)。X 對(duì)一棵二叉樹(shù)進(jìn)行層次遍歷時(shí)，應(yīng)借助于一個(gè)棧。X45.霍夫曼樹(shù)的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)。寸48.當(dāng)一棵具有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)的WPL值為最小時(shí)，稱其樹(shù)為Huffman樹(shù)，且其二 叉樹(shù)的形狀必

8、是唯一的。X三、填空題1.二叉樹(shù)由_根結(jié)點(diǎn)_左子樹(shù)一右子樹(shù)_三個(gè)基本單元組成。2 .樹(shù)在計(jì)算機(jī)內(nèi)的表示方式有雙親鏈表表示法，孩子鏈表表示法，孩子兄弟表 示法。3 .在二叉樹(shù)中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_p-lchild=null & p-rchlid=null。深度為H的完全二叉樹(shù)至少有2H-1個(gè)結(jié)點(diǎn)；至多有2H-1個(gè)結(jié)點(diǎn)；H和結(jié)點(diǎn)總數(shù)N 之間的關(guān)系是H=log2N+1。四、應(yīng)用題證明，由一棵二叉樹(shù)的前序序列和中序序列可唯一確定這棵二叉樹(shù)。設(shè)一棵二叉 樹(shù)的前序序列為ABDGECFH，中序序列為：DGBEAFHC。試畫(huà)出該二叉樹(shù)。試畫(huà)出在先根次序和中根次序下結(jié)點(diǎn)排列順序皆相同的所有類型的

9、二叉樹(shù)形。試畫(huà)出在先根次序和后根次序下結(jié)點(diǎn)排列順序皆相同的所有類型的二叉樹(shù)形。由前序序列ABDGECFH和中序序列DGBEAFHC構(gòu)造的二叉樹(shù)如圖：(1)給定一組數(shù)列(15,8,10,21,6,19,3)分別代表字符A,B,C,D,E,F,G出現(xiàn)的 頻度，試敘述建立哈夫曼樹(shù)的算法思想，畫(huà)出哈夫曼樹(shù)，給出各字符的編碼值，并說(shuō)明這 種編碼的優(yōu)點(diǎn)。先序遍歷二叉樹(shù)的順序是“根一左子樹(shù)一右子樹(shù)”，中序遍歷“左子樹(shù)一根一右子樹(shù)”， 后序遍歷順序是：“左子樹(shù)一右子樹(shù)一根”，根據(jù)以上原則，本題解答如下：若先序序列與后序序列相同，則或?yàn)榭諛?shù)，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹(shù)若中序序列與后序序列相同，則或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)

10、點(diǎn)至多只有左子樹(shù)的二叉樹(shù).若先序序列與中序序列相同，則或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù).若中序序列與層次遍歷序列相同，則或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)。由中序序列DBEAFIHCG和后序序列DEBHIFGCA確定的二叉樹(shù)略。第七章圖一、選擇題圖中有關(guān)路徑的定義是(A )。A.由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列B-由不同頂點(diǎn)所形成的序列C-由不同邊所形成的序列D.上述定義都不是設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有(B )條邊。A. n-1B. n(n-1)/2 C. n(n+1)/2D. 0 E. n2 一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為(A)。A. n-

11、1B. nC. n+1D. nlogn；要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要(B )條邊。A. n-lB. nC. n+lD. 2nn個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目(D )。C. n / 2D. n*）個(gè)連通分量，最多有（DC. n_1（nl）個(gè)連通分量。D. nA. n*nB. n （n+1）一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有（BA. 0B. 1在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（B ）倍，在一個(gè)有向圖中， 所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（C ）倍。A. 1/2B. 2C. 1D. 4 下面結(jié)構(gòu)中最適于表示稀疏無(wú)向圖的是（C），適于表示稀疏有向圖的是（BDE ）。A.鄰接矩陣B

12、 .逆鄰接表C.鄰接多重表D.十字鏈表 E.鄰接表下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？ （ B ）A.有向圖B.無(wú)向圖C. AOV網(wǎng)D. AOE網(wǎng)12.A從鄰接陣矩可以看出，該圖共有(B)個(gè)頂點(diǎn)；如果是有向圖該圖共有(B)條孤；如果是無(wú)向圖，則共有(D)條邊。E.以上答案均不正確E.以上答案均不正確E.以上答案均不正確 TOC o 1-5 h z .A.9B.3C.6D.1.A.5B.4C.3D.2.A.5B.4C.3D.2當(dāng)一個(gè)有N個(gè)頂點(diǎn)的圖用鄰接矩陣A表示時(shí)，頂點(diǎn)Vi的度是（B ）。Ai, j Ali,j1La j, i lAi, j 人質(zhì)A，=1B.j=iC.,=1D.,=1+j=i下列說(shuō)

13、法不正確的是（B ）。圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問(wèn)一次C.圖的深度遍歷不適用于有向圖遍歷的基本算法有兩種：深度遍歷和廣度遍歷D.圖的深度遍歷是一個(gè)遞歸過(guò)程無(wú)向圖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），對(duì)該圖進(jìn)行深度 優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（D ）。A. a,b,e,c,d,fa,c,f,e,b,da,e,b,c,f,da,e,d,f,c,b第17題圖設(shè)圖如右所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有多少？ （D ）a e b d f c a c f d e b b

14、 cA. 5個(gè)B. 4個(gè)下圖中給出由7個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn)1出發(fā)，對(duì)它進(jìn)行深度優(yōu)先遍歷得到的 序列是（C ），而進(jìn)行廣度優(yōu)先遍歷得到的頂點(diǎn)序列是（C）。.A.1354267B.1347652C.1534276D.1247653 E.以上答案均不正確.A. 1534267 B. 1726453 C. 1354276 D. 1247653 E .以上答 案均不正確下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）：ABA.深度優(yōu)先遍歷 B.拓?fù)渑判駽.求最短路徑D.求關(guān)鍵路徑在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹(shù)的Prim算法的時(shí)間復(fù)雜度為（B ）。A. O(n)O(n+e)C. O(w) D.

15、O(m)已知有向圖 G=(V,E)，其中 V=V,V,V,V,V,V,V,一.12.3.45.6.7E=,G 的拓?fù)湫?21314253536465767列是(A )。A. V,V,V,V,V,V,VB. V,V,V,V,V,V,V13462571326457V,V,V,V,V,V,VD. V,V,V,V,V,V,V13452671253467若一個(gè)有向圖的鄰接距陣中，主對(duì)角線以下的兀素均為零，則該圖的拓?fù)溆行蛐蛄校ˋ ）。A.存在B-不存在27一個(gè)有向無(wú)環(huán)圖的拓?fù)渑判蛐蛄校?BA. 一定B-不一定28.在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi（ D ）。A. G 中有弧B.G中沒(méi)有弧D.）是唯一的

16、。在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是G中有一條從Vi到Vj的路徑G中有一條從Vj到Vi的路徑關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（A.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑C.最長(zhǎng)回路A ）。從源點(diǎn)到匯點(diǎn)的最短路徑最短回路下面關(guān)于求關(guān)鍵路徑的說(shuō)法不正確的是（C ）。求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的一個(gè)事件的最早開(kāi)始時(shí)間同以該事件為尾的弧的活動(dòng)最早開(kāi)始時(shí)間相同一個(gè)事件的最遲開(kāi)始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開(kāi)始時(shí)間與該活動(dòng)的持 續(xù)時(shí)間的差D .關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上 二、判斷題 TOC o 1-5 h z 樹(shù)中的結(jié)點(diǎn)和圖中的頂點(diǎn)就是指數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素。（”）在n個(gè)結(jié)點(diǎn)的無(wú)向圖中，若邊數(shù)大于n-1,則該圖必是連

17、通圖。（X ）有e條邊的無(wú)向圖，在鄰接表中有e個(gè)結(jié)點(diǎn)。（X ）有向圖中頂點(diǎn)V的度等于其鄰接矩陣中第V行中的1的個(gè)數(shù)。（X ） 強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。（”）強(qiáng)連通分量是無(wú)向圖的極大強(qiáng)連通子圖。（X ）連通分量指的是有向圖中的極大連通子圖。（X ） 鄰接多重表是無(wú)向圖和有向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（X）十字鏈表是無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu)。（X ）無(wú)向圖的鄰接矩陣可用一維數(shù)組存儲(chǔ)。（V ）用鄰接矩陣法存儲(chǔ)一個(gè)圖所需的存儲(chǔ)單元數(shù)目與圖的邊數(shù)有關(guān)。（X ）有n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。（V ）有向圖的鄰接矩陣是對(duì)稱的。（X ）無(wú)向圖的鄰接矩陣一定是對(duì)稱矩陣，

18、有向圖的鄰接矩陣一定是非對(duì)稱矩陣。（X ）鄰接矩陣適用于有向圖和無(wú)向圖的存儲(chǔ)，但不能存儲(chǔ)帶權(quán)的有向圖和無(wú)向圖，而只能 使用鄰接表存儲(chǔ)形式來(lái)存儲(chǔ)它。（X ）用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小與圖 中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。（V ）一個(gè)有向圖的鄰接表和逆鄰接表中結(jié)點(diǎn)的個(gè)數(shù)可能不等。（X ）需要借助于一個(gè)隊(duì)列來(lái)實(shí)現(xiàn)DFS算法。（X ）廣度遍歷生成樹(shù)描述了從起點(diǎn)到各頂點(diǎn)的最短路徑。（X ）任何無(wú)向圖都存在生成樹(shù)。（X ）不同的求最小生成樹(shù)的方法最后得到的生成樹(shù)是相同的.（X ）帶權(quán)無(wú)向圖的最小生成樹(shù)必是唯一的。（X ）最小代價(jià)生成樹(shù)是唯一的。（X ）一個(gè)網(wǎng)（

19、帶權(quán)圖）都有唯一的最小生成樹(shù)。（X ）連通圖上各邊權(quán)值均不相同，則該圖的最小生成樹(shù)是唯一的。（V ）帶權(quán)的連通無(wú)向圖的最小（代價(jià)）生成樹(shù)（支撐樹(shù)）是唯一的。（X ）拓?fù)渑判蛩惴ò岩粋€(gè)無(wú)向圖中的頂點(diǎn)排成一個(gè)有序序列。（X ）拓?fù)渑判蛩惴▋H能適用于有向無(wú)環(huán)圖。（X ） TOC o 1-5 h z 39.任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)渑判颍彝負(fù)湫蛄胁晃ㄒ?。（）AOV網(wǎng)的含義是以邊表示活動(dòng)的網(wǎng)。（）對(duì)一個(gè)AOV網(wǎng)，從源點(diǎn)到終點(diǎn)的路徑最長(zhǎng)的路徑稱作關(guān)鍵路徑。關(guān)鍵路徑是AOE網(wǎng)中從源點(diǎn)到終點(diǎn)的最長(zhǎng)路徑。（）AOE網(wǎng)一定是有向無(wú)環(huán)圖。（）三、填空題1.判斷一個(gè)無(wú)向圖是一棵樹(shù)的條件是_有n個(gè)頂點(diǎn)，n-1條

20、邊的無(wú)向連通圖。 具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為45。 若用n表示圖中頂點(diǎn)數(shù)目，則有n（n-1）/2條邊的無(wú)向圖成為完全圖。設(shè)無(wú)向圖G有n個(gè)頂點(diǎn)和e條邊，每個(gè)頂點(diǎn)Vi的度為di （1=i=n，則e=在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要_ n 條 弧。 在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)一 2（n-1）。 設(shè)G為具有N個(gè)頂點(diǎn)的無(wú)向連通圖，則G中至少有 n-1條邊。如果含n個(gè)頂點(diǎn)的圖形形成一個(gè)環(huán)，則它有 n 棵生成樹(shù)。 N個(gè)頂點(diǎn)的連通圖的生成樹(shù)含有_n-1 條邊。在有向圖的鄰接矩陣表示中，計(jì)算第I個(gè)頂點(diǎn)入度的方法是第I列非零元素個(gè)數(shù)對(duì)于一個(gè)具有n個(gè)頂點(diǎn)

21、e條邊的無(wú)向圖的鄰接表的表示，則表頭向量大小為n ， 鄰接表的邊結(jié)點(diǎn)個(gè)數(shù)為2e 。22.已知一無(wú)向圖 G= （V，E），其中 V=a,b,c,d,e E=（a,b）,（a,d）,（a,c）,（d,c）,（b,e） 現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開(kāi)始遍歷圖，得到的序列為abecd，則采用的是_深度優(yōu)先 遍歷方法。為了實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了一個(gè)標(biāo)志數(shù)組標(biāo)志已訪問(wèn)的圖的結(jié)點(diǎn)外，還需 隊(duì)列 存放被訪問(wèn)的結(jié)點(diǎn)以實(shí)現(xiàn)遍歷。和深度優(yōu)先生成樹(shù)按下圖所示，畫(huà)出它的廣度優(yōu)先生成樹(shù)構(gòu)造連通網(wǎng)最小生成樹(shù)的兩個(gè)典型算法是_普里姆(prim)算法和克魯斯卡爾一、5】(Kruskal)算法 ?！颈本┛萍即髮W(xué)1998求圖的

22、最小生成樹(shù)有兩種算法，_克魯斯卡爾_算法適合于求稀疏圖的最小生成樹(shù)。Prim (普里姆)算法適用于求 邊稠密的網(wǎng)的最小生成樹(shù);kruskal (克魯斯卡爾)算法適用于求邊稀疏的網(wǎng)的最小生成樹(shù)。33.有向圖G可拓?fù)渑判虻呐袆e條件是_不存在環(huán)。四、應(yīng)用題(1).如果G1是一個(gè)具有n個(gè)頂點(diǎn)的連通無(wú)向圖，那么G1最多有多少條邊？ G1最少 有多少條邊？.如果G2是一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖，那么G2最多有多少條邊？ G2最 少有多少條邊？.如果G3是一個(gè)具有n個(gè)頂點(diǎn)的弱連通有向圖，那么G3最多有多少條邊？ G3最 少有多少條邊？n個(gè)頂點(diǎn)的無(wú)向連通圖最少有多少條邊？ n個(gè)頂點(diǎn)的有向連通圖最少有多少條邊？解答問(wèn)題。設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：