數(shù)據(jù)結(jié)構(gòu)第六章圖練習(xí)題及答案詳細(xì)解析版

1、圖1.填空題填空題⑴設(shè)無向圖設(shè)無向圖G中頂點(diǎn)數(shù)為中頂點(diǎn)數(shù)為n，則圖，則圖G至少有（至少有（）條邊，至多有（）條邊，至多有（）條邊；若）條邊；若G為有向圖，則至少有為有向圖，則至少有（）條邊，至多有（）條邊，至多有（）條邊。）條邊?！窘獯稹俊窘獯稹?，n(n1)2n(n1)2，0，n(n1)n(n1)【分析】圖的頂點(diǎn)集合是有窮非空的，而邊集可以是空集；邊數(shù)達(dá)到最多的圖稱為完全圖，在完全圖中，【分析】圖的頂點(diǎn)集合是有窮非空的，而邊集可以是空

2、集；邊數(shù)達(dá)到最多的圖稱為完全圖，在完全圖中，任意兩個(gè)頂點(diǎn)之間都存在邊。任意兩個(gè)頂點(diǎn)之間都存在邊。⑵任何連通圖的連通分量只有一個(gè)，即是（任何連通圖的連通分量只有一個(gè)，即是（）。）?！窘獯稹科渥陨怼窘獯稹科渥陨恝菆D的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是（圖的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是（）和（）和（）。）。【解答】鄰接矩陣，鄰接表【解答】鄰接矩陣，鄰接表【分析】這是最常用的兩種存儲(chǔ)結(jié)構(gòu)，此外，還有十字鏈表、鄰接多重表、邊集數(shù)組等?！痉治觥窟@是最常用的兩

3、種存儲(chǔ)結(jié)構(gòu)，此外，還有十字鏈表、鄰接多重表、邊集數(shù)組等。⑷已知無向圖已知無向圖G的頂點(diǎn)數(shù)為的頂點(diǎn)數(shù)為n，邊數(shù)為，邊數(shù)為e，其，其鄰接表鄰接表表示的空間復(fù)雜度為（表示的空間復(fù)雜度為（）。）?！窘獯稹浚稀窘獯稹浚?ne)(ne)【分析】在無向圖的鄰接表中，頂點(diǎn)表有【分析】在無向圖的鄰接表中，頂點(diǎn)表有n個(gè)結(jié)點(diǎn)，邊表有個(gè)結(jié)點(diǎn)，邊表有2e2e個(gè)結(jié)點(diǎn)，共有個(gè)結(jié)點(diǎn)，共有n2en2e個(gè)結(jié)點(diǎn)，其空間復(fù)雜個(gè)結(jié)點(diǎn)，其空間復(fù)雜度為Ｏ度為Ｏ(n2e)=(n2e)

4、=Ｏ(ne)(ne)。⑸已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第j個(gè)頂點(diǎn)的個(gè)頂點(diǎn)的入度入度的方法是（的方法是（）。）?！窘獯稹壳蟮凇窘獯稹壳蟮趈列的所有元素之和列的所有元素之和⑹有向圖有向圖G用鄰接矩陣用鄰接矩陣A[n][n]A[n][n]存儲(chǔ)，其第存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)行的所有元素之和等于頂點(diǎn)i的（的（）。）?！窘獯稹砍龆取窘獯稹砍龆娶苙個(gè)頂點(diǎn)的個(gè)頂點(diǎn)的強(qiáng)連通圖強(qiáng)連通圖至少有（至少有（）條

5、邊，其形狀是（）條邊，其形狀是（）。）。AnBn1n1Cn1n1Dn(n1)n(n1)E無回路無回路F有回路有回路G環(huán)狀環(huán)狀H樹狀樹狀【解答】【解答】A，G⑶含n個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過（個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過（）。）。A1Bn2n2Cn1n1Dn【解答】【解答】C【分析】若超過【分析】若超過n1n1，則路徑中必存在重復(fù)的頂點(diǎn)。，則路徑中必存在重復(fù)的頂點(diǎn)。⑷對(duì)于一個(gè)具有對(duì)于一個(gè)具

6、有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣存儲(chǔ)，則該矩陣的大小是（個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣存儲(chǔ)，則該矩陣的大小是（）。）。AnB(n1)2(n1)2Cn1n1Dn2n2【解答】【解答】D⑸圖的生成樹（圖的生成樹（），），n個(gè)頂點(diǎn)的生成樹有（個(gè)頂點(diǎn)的生成樹有（）條邊。）條邊。A唯一唯一B不唯一不唯一C唯一性不能確定唯一性不能確定DnEn11Fn1n1【解答】【解答】C，F(xiàn)⑹設(shè)無向圖設(shè)無向圖G=(VG=(VE)E)和GG=(V=(VEE)，如