數(shù)據(jù)結(jié)構(gòu)圖練習(xí)

1、圖練習(xí):1圖中有關(guān)路徑的定義是（ ） 。A.由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列B.由不同頂點(diǎn)所形成的序列C.由不同邊所形成的序列D.上述定義都不是2.設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有（）條邊。A n-1 B n（n-1）/2 C n（n+1）/2 D 0 E n23一個(gè) n 個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（ ）。A n-1 B n C n+1 D nlogn ；4要連通具有n 個(gè)頂點(diǎn)的有向圖，至少需要（ ）條邊。A n-l B n C n+l D 2n5 n 個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（ ） 。A. n*nB . n （n+ 1 ） C , n/2D . n* （n l ）

2、6一個(gè)有 n 個(gè)結(jié)點(diǎn)的圖，最少有（ ）個(gè)連通分量，最多有（ ）個(gè)連通 分量。A 0B 1C n-1 D n7在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（ ）倍。A 1/2 B 2 C 1D 48 . 下列說(shuō)法不正確的是（ ） 。A.圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次C .圖的深度 遍歷不適用于有向圖B.遍歷的基本算法有兩種：深度遍歷和廣度遍歷D .圖的深度遍歷是一個(gè)遞歸過(guò)程9 無(wú) 向 圖 G=(V,E), 其 中 ：V=a,b,Gd,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,

3、d),(e,d),對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是()。A . a,b,e,c,d,fB . a,c,f,e,b,dC. a,e,b,c,f,dD. a,e,d,f,c,b10 .關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中( )oA.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B .從源點(diǎn)到匯點(diǎn)的最短路徑C.最長(zhǎng)回路D.最短回路1.A2.B3.A4.B5.D6.1B6.2D7.1B7.2C8c9D10A二、判斷題1. 樹(shù)中的結(jié)點(diǎn)和圖中的頂點(diǎn)就是指數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素。 （）2在n 個(gè)結(jié)點(diǎn)的無(wú)向圖中，若邊數(shù)大于n-1, 則該圖必是連通圖。 （）3. 對(duì)有n個(gè)頂點(diǎn)的無(wú)向圖，其邊數(shù)e與各頂點(diǎn)度數(shù)間滿(mǎn)足下列等式e=0 （4.

4、有 e 條邊的無(wú)向圖，在鄰接表中有e 個(gè)結(jié)點(diǎn)。 （）5. 有向圖中頂點(diǎn) V 的度等于其鄰接矩陣中第 V 行中的 1 的個(gè)數(shù)。 （）6強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。（）7鄰接多重表是無(wú)向圖和有向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（）8. 十字鏈表是無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu)。 （）9用鄰接矩陣法存儲(chǔ)一個(gè)圖所需的存儲(chǔ)單元數(shù)目與圖的邊數(shù)有關(guān)。（）10 有 n 個(gè)頂點(diǎn)的無(wú)向圖 , 采用鄰接矩陣表示, 圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。 （）11 有向圖的鄰接矩陣是對(duì)稱(chēng)的。 （）12無(wú)向圖的鄰接矩陣一定是對(duì)稱(chēng)矩陣，有向圖的鄰接矩陣一定是非對(duì)稱(chēng)矩陣。（）13. 鄰接矩陣適用于有向圖和無(wú)向圖的存儲(chǔ)， 但不能存儲(chǔ)帶權(quán)的有向圖

5、和無(wú)向圖，而只能使用鄰接表存儲(chǔ)形式來(lái)存儲(chǔ)它。 （）14. 用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。 （）15. 廣度遍歷生成樹(shù)描述了從起點(diǎn)到各頂點(diǎn)的最短路徑。 （）16任何無(wú)向圖都存在生成樹(shù)。 （）17. 不同的求最小生成樹(shù)的方法最后得到的生成樹(shù)是相同的 . （）18帶權(quán)無(wú)向圖的最小生成樹(shù)必是唯一的。（ ）19. 最小代價(jià)生成樹(shù)是唯一的。 （）20一個(gè)網(wǎng)（帶權(quán)圖）都有唯一的最小生成樹(shù)。 （）21連通圖上各邊權(quán)值均不相同，則該圖的最小生成樹(shù)是唯一的。 （）22帶權(quán)的連通無(wú)向圖的最?。ù鷥r(jià)）生成樹(shù)（支撐樹(shù)）是唯一的。 （）23帶權(quán)

6、的連通無(wú)向圖的最小代價(jià)生成樹(shù)是唯一的。 （）24. 最小生成樹(shù)問(wèn)題是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹(shù)。1"2. X3. x4. X5. X6. V7X8X9. x10.V11X12.X13.14.15.16.17.18.19.20.21.22.2324vzXVXXXXXXVXX三、填空題1 .判斷一個(gè)無(wú)向圖是一棵樹(shù)的條件是 。2 .有向圖G的強(qiáng)連通分量是指 。3 . 一個(gè)連通圖的 是一個(gè)極小連通子圖。4 .具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為 。5 .若用n表示圖中頂點(diǎn)數(shù)目，則有 條邊的無(wú)向圖成為完全圖。6 .設(shè)無(wú)向圖G有n個(gè)頂點(diǎn)和e條邊，每個(gè)頂點(diǎn)Vi的度為di (1<=i<

7、=n，則 e=7 . G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有 個(gè)頂點(diǎn)。8 .在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要 條弧。9 .在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá) 。10 .設(shè)G為具有N個(gè)頂點(diǎn)的無(wú)向連通圖，則 G中至少有條邊。11 . n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的條數(shù)至少為 o12 .如果含n個(gè)頂點(diǎn)的圖形形成一個(gè)環(huán)，則它有 棵生成樹(shù)。13 . N個(gè)頂點(diǎn)的連通圖的生成樹(shù)含有 條邊。14 .構(gòu)造n個(gè)結(jié)點(diǎn)的強(qiáng)連通圖，至少有 條弧。15 .有N個(gè)頂點(diǎn)的有向圖，至少需要量 條弧 rj分、才能保證是連通的。- -J,.16 .右圖中的強(qiáng)連通分量的個(gè)數(shù)為()個(gè)。

8、17 . N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣 至少有 個(gè)非零元素。18 .在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無(wú)向圖來(lái)說(shuō)等于該頂點(diǎn)的 ;對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的 。19 .在有向圖的鄰接矩陣表示中，計(jì)算第I個(gè)頂點(diǎn)入度的方法是 。20 .對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接表的表示，則表頭向量大小為 ,鄰接表的邊結(jié)點(diǎn)個(gè)數(shù)為。21 .已知一無(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,則采用的是遍歷方法。答案：1 .有n個(gè)

9、頂點(diǎn)，n-1條邊的無(wú)向連通圖2 .有向圖的極大強(qiáng)連通子圖3 .生成樹(shù)4 . 455. n(n-1)/26 .7. 98. n9. 2(n-1) 10. N-111. n-112. n 13. N-114. n15. N16. 3 17. 2(N-1)18. 度 出度19. 第I列非零元素個(gè)數(shù) 20.n 2e22.深度優(yōu)先23.寬度優(yōu)先遍歷四、應(yīng)用題1 . (1).如果G1是一個(gè)具有n個(gè)頂點(diǎn)的連通無(wú)向圖，那么G1最多有多少條邊？ G1最少有多少條邊？(2) .如果G2是一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖，那么G2最多有多少條邊？ G2最少有多少條邊？(3) .如果G3是一個(gè)具有n個(gè)頂點(diǎn)的弱連通有向圖

10、，那么G3最多有多少條邊？ G3最少有多少條邊？2 . n個(gè)頂點(diǎn)的無(wú)向連通圖最少有多少條邊？n個(gè)頂點(diǎn)的有向連通圖最少有多少條邊？3 .首先將如下圖所示的無(wú)向圖給出其存儲(chǔ)結(jié)構(gòu)的鄰接鏈表表示，然后寫(xiě)出對(duì)其分別進(jìn)行深度，廣度優(yōu)先遍歷的結(jié)果。4 .給出圖G:(1) .畫(huà)出G的鄰接表表示圖；(2) .根據(jù)你畫(huà)出的鄰接表，以頂點(diǎn)為根，畫(huà)出G的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。5 .對(duì)一個(gè)圖進(jìn)行遍歷可以得到不同的遍歷序列，那么導(dǎo)致得到的遍歷序列不唯一的因素有 哪些？6 .考慮下圖：(1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(shù)(2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹(shù)(3)根據(jù)普利姆(Prim)算法，求它的最小生成樹(shù)從A點(diǎn)開(kāi)始(4)根據(jù)kruskal算法，求它的最小生成樹(shù)7 .考慮下圖：(1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(shù)(2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹(shù)(3)根據(jù)普利姆(Prim)算法，求它的最小生成樹(shù)從1點(diǎn)開(kāi)始(4)根據(jù)kruskal算法，求它的最小生成樹(shù)答案：(1) (1) G1最多n(n-1)/2 條邊，最少n-1條邊(2) G2最多n(n-1)條邊，最少n 條邊(3) G3最多n(n-1)條邊，最少n-1 條邊( 注：弱連通有向圖指把有向圖看作無(wú)向圖時(shí)，仍是連通的 )2 n-1 ， n3 深度優(yōu)先遍歷序列：125967384寬度優(yōu)先遍歷序列： 123456789注： ( 1)鄰接表不