數(shù)據(jù)結(jié)構(gòu)第7章 圖習(xí)題

1、第7章 圖一、單項(xiàng)選擇題1在一個(gè)無(wú)向圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的_倍。 Al/2B1 C2D42在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的_倍。Al/2 B1 C2D43一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖最多包含_條邊。 An Bn1Cn-1 Dn(n-1)/24一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖包含_條邊。An(n-l) Bn(n+l) Cn(n-l)/2 Dn(n-l)/25一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含_條邊。An(n-1) Bn(n+l) Cn(n-l)/2 Dn(n+l)/26對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為_。An Bn×n C

2、n-1 D(n-l) ×(n-l)7無(wú)向圖的鄰接矩陣是一個(gè)_。A對(duì)稱矩陣 B零矩陣 C上三角矩陣 D對(duì)角矩陣8對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)(有)向圖，若采用鄰接表表示，則表頭向量的大小為_。An Be C2n D2e9對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)(有)向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為_。An Be C2n D2e10在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有_鄰接點(diǎn)。A入邊 B出邊 C入邊和出邊 D不是入邊也不是出邊11在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有_鄰接點(diǎn)。A入邊 B出邊C入邊和出邊 D不是人邊也不是出邊12如果從無(wú)向圖的

3、任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是_。A完全圖 B連通圖C有回路 D一棵樹13采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的_算法。A先序遍歷 B中序遍歷C后序遍歷 D按層遍歷14采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的_算法。A先序遍歷 B中序遍歷C后序遍歷 D按層遍歷15如果無(wú)向圖G必須進(jìn)行二次廣度優(yōu)先搜索才能訪問其所有頂點(diǎn)，則下列說法中不正確的是_。AG肯定不是完全圖 BG一定不是連通圖CG中一定有回路 DG有二個(gè)連通分量16下列有關(guān)圖遍歷的說法不正確的是_。A連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程 B圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的

4、特征 C非連通圖不能用深度優(yōu)先搜索法 D圖的遍歷要求每一頂點(diǎn)僅被訪問一次17下列說法中不正確的是_。A無(wú)向圖中的極大連通子圖稱為連通分量 B連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問過的頂點(diǎn) C圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪問過的頂點(diǎn) D有向圖的遍歷不可采用廣度優(yōu)先搜索方法18一個(gè)有向圖G的鄰接表存儲(chǔ)如下圖7-1所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是_。Av1，v2，v3，v4，v5 Bv1，v2，v3，v5，v4Cv1，v2，v4，v5，v3 Dv1，v2，v5，v3，v4 234 35 5 4 v1v2v3v4 v5圖7-1 一個(gè)有向圖的鄰接表19對(duì)

5、圖7-2所示的無(wú)向圖，從頂點(diǎn)1開始進(jìn)行深度優(yōu)先遍歷，可得到頂點(diǎn)訪問序列_。A1，2，4，3，5，7，6 B1，2，4，3，5，6，7C1，2，4，5，6，3，7 D1，2，3，4，5，7，61654327 圖7-2 一個(gè)無(wú)向圖20對(duì)圖7-2所示的無(wú)向圖，從頂點(diǎn)1開始進(jìn)行廣度優(yōu)先遍歷，可得到頂點(diǎn)訪問序列_。A1，3，2，4，5，6，7 B1，2，4，3，5，6，7C1，2，3，4，5，7，6 D2，5，1，4，7，3，621一個(gè)無(wú)向連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的_。A極小連通子圖 B極小子圖C極大連通子圖 D極大子圖22設(shè)無(wú)向圖 G=(V, E) 和G= (V, E)，如果 G為G的生

6、成樹，則下列說法中不正確的是_。AG為G的連通分量 BG為G的無(wú)環(huán)子圖CG為G的子圖 DG為G的極小連通子圖且VV23.任意一個(gè)無(wú)向連通圖_最小生成樹。A只有一棵 B有一棵或多棵C一定有多棵 D可能不存在24對(duì)于含有n個(gè)頂點(diǎn)的帶權(quán)連通圖，它的最小生成樹是指圖中任意一個(gè)_。A由n-1條權(quán)值最小的邊構(gòu)成的子圖。 B由n-1條權(quán)值之和最小的邊構(gòu)成的子圖。C由n-1條權(quán)值之和最小的邊構(gòu)成的連通子圖。D由n個(gè)頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的生成樹。25若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄校瑒t可斷定該有向圖_。A是個(gè)有根有向圖 B是個(gè)強(qiáng)連通圖C含有多個(gè)入度為0的頂點(diǎn) D含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量26判

7、定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以用_。A求關(guān)鍵路徑的方法 B求最短路徑的Dijkstra算法C廣度優(yōu)先遍歷算法 D深度優(yōu)先遍歷算法27求最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為_。AO(n) BO(n+e)CO(n2) DO(ne)28求最短路徑的Floyd算法的時(shí)間復(fù)雜度為_。AO(n) BO(ne)CO(n2) DO(n3) 29關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中_。A從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B從源點(diǎn)到匯點(diǎn)的最短路徑C最長(zhǎng)的回路 D最短的回路30下面說法不正確的是_。A在AOE網(wǎng)中，減少任一關(guān)鍵活動(dòng)的權(quán)值后，整個(gè)工期也就相應(yīng)減少BAOE網(wǎng)工程工期為關(guān)鍵活動(dòng)的權(quán)值和C在關(guān)

8、鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)，而關(guān)鍵活動(dòng)也必須在關(guān)鍵路徑上DA和B31下面說法不正確的是_。A關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B任何一個(gè)關(guān)鍵活動(dòng)提前完成，將使整個(gè)工程提前完成C所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程提前完成D某些關(guān)鍵活動(dòng)若提前完成，將使整個(gè)工程提前完成二、填空題1對(duì)于具有n個(gè)頂點(diǎn)的無(wú)向圖G最多有_條邊。2對(duì)于具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖G至少有_條邊。3對(duì)于具有n個(gè)頂點(diǎn)的有向圖，每個(gè)頂點(diǎn)的度最大可達(dá)_。4若無(wú)向圖G的頂點(diǎn)度數(shù)最小值大于_時(shí)，G至少有一條回路。5對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小為_，所有鄰接表中的結(jié)點(diǎn)總數(shù)是_。6已知一個(gè)

9、有向圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的弧的方法是_。7對(duì)于n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是_，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相連的方法是_，求任意一個(gè)頂點(diǎn)的度的方法是_。8對(duì)于n個(gè)頂點(diǎn)的有向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是_，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相連的方法是_，求任意一個(gè)頂點(diǎn)的度的方法是_。9無(wú)向圖的連通分量是指_。 10已知圖G的鄰接表如圖7-3所示，從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序列為_，從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列為_。v1v2v3v4 v5v6 234 35 6 4 63 圖7-3 圖G的鄰接表11n個(gè)頂點(diǎn)連通圖的生成樹一定有_條邊。1

10、2一個(gè)連通圖的_是一個(gè)極小連通子圖。 13Prim算法適用于求_的網(wǎng)的最小生成樹，Kruskal算法適用于求_的網(wǎng)的最小生成樹。 14在AOV圖中，頂點(diǎn)表示_,有向邊表示_。15可以進(jìn)行拓?fù)渑判虻挠邢驁D一定是_。16從源點(diǎn)到匯點(diǎn)長(zhǎng)度最長(zhǎng)的路徑稱為關(guān)鍵路徑，該路徑上的活動(dòng)稱為_。 17Dijkstra算法從源點(diǎn)到其它各頂點(diǎn)的路徑長(zhǎng)度按_次序依次產(chǎn)生，該算法在邊上的權(quán)出現(xiàn)_情況時(shí)，不能正確產(chǎn)生最短路徑。18求從某源點(diǎn)到其余各項(xiàng)點(diǎn)的Dijkstra算法在圖的頂點(diǎn)數(shù)為10，用鄰接矩陣表示圖時(shí)計(jì)算時(shí)間約為10ms，則在圖的頂點(diǎn)數(shù)為40時(shí)，計(jì)算時(shí)間約為_ms。三、判斷題1具有n個(gè)頂點(diǎn)的無(wú)向圖至多有n（n-

11、1）條邊。2有向圖中各頂點(diǎn)的入度之和等于各頂點(diǎn)的出度之和。3鄰接矩陣只儲(chǔ)存了邊的信息，沒有存儲(chǔ)頂點(diǎn)的信息。4對(duì)同一個(gè)有向圖，只保存出邊的鄰接表中結(jié)點(diǎn)的數(shù)目總是和只保存入邊的鄰接表中結(jié)點(diǎn)的數(shù)目一樣多。5如果表示圖的鄰接矩陣是對(duì)稱矩陣，則該圖一定是無(wú)向圖。6如果表示有向圖的鄰接矩陣是對(duì)稱矩陣，則該有向圖一定是有向完全圖。7如果表示某個(gè)圖的鄰接矩陣不是對(duì)稱矩陣，則該圖一定是有向圖。8連通分量是無(wú)向圖的極小連通子圖。9強(qiáng)連通分量是有向圖的極大連通子圖。10對(duì)有向圖G，如果以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每一個(gè)頂點(diǎn)，則該圖一定是完全圖。11連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫時(shí)剛

12、訪問過的頂點(diǎn)。12圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫時(shí)剛訪問過的頂點(diǎn)。13有向圖的遍歷不可采用廣度優(yōu)先搜索方法。14連通圖的生成樹包含了圖中所有頂點(diǎn)。15設(shè)G為具有n個(gè)頂點(diǎn)的連通圖，如果其中的某個(gè)子圖有n個(gè)頂點(diǎn)，n-1條邊，則該子圖一定是G的生成樹。16最小生成樹是指邊數(shù)最小的生成樹。17從n個(gè)頂點(diǎn)的連通圖中選取n-1條權(quán)值最小的邊，即可構(gòu)成最小生成樹。18只要無(wú)向網(wǎng)中沒有權(quán)值相同的邊，其最小生成樹就是惟一的。19只要無(wú)向網(wǎng)中有權(quán)值相同的邊，其最小生成樹就可能不是惟一的。20有環(huán)圖也能進(jìn)行拓?fù)渑判颉?1拓?fù)渑判蛩惴▋H適用于有向無(wú)環(huán)圖。22任何有向無(wú)環(huán)圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?，而且拓?fù)湫蛄胁晃?/p>

13、一。23關(guān)鍵路徑是由權(quán)值最大的邊構(gòu)成的。24在AOE網(wǎng)中，減小任一關(guān)鍵活動(dòng)上的權(quán)值后，整個(gè)工期也就相應(yīng)減小。25在AOE網(wǎng)中工程工期為關(guān)鍵活動(dòng)上權(quán)值之和。26在關(guān)鍵路徑的活動(dòng)都是關(guān)鍵活動(dòng)，而關(guān)鍵活動(dòng)未必在關(guān)鍵路徑上。27關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間。28所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程將提前完成。29某些關(guān)鍵活動(dòng)若提前完成，將可能使整個(gè)工程提前完成。30求單源最短路徑的狄克斯特拉算法不適用于有回路的有向網(wǎng)。四、簡(jiǎn)答題1圖G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有多少個(gè)頂點(diǎn)？2用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否有關(guān)？3對(duì)于稠密圖和稀疏圖，

14、就存儲(chǔ)而言，采用鄰接矩陣和鄰接表哪個(gè)更好些？4請(qǐng)回答下列關(guān)于圖的一些問題：（1）有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有多少條邊？最少有多少條邊？（2）表示一個(gè)有1000個(gè)頂點(diǎn)，1000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣元素？是否為稀疏矩陣？（3）對(duì)于一個(gè)有向圖，不用拓?fù)渑判颍绾闻袛鄨D是否存在環(huán)？5對(duì)n個(gè)頂點(diǎn)的無(wú)向圖和有向圖，采用鄰接表表示時(shí)，如何判別下列有關(guān)問題？（1）圖中有多少條邊？（2）任意兩個(gè)頂點(diǎn)i和j是否有邊相連？（3）任意一個(gè)頂點(diǎn)的度是多少？6給出如圖7-4所示的無(wú)向圖G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。并在給定的鄰接表基礎(chǔ)上，指出從頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列。12543圖7

15、-4 一個(gè)無(wú)向圖7對(duì)于圖7-5所示的有向圖，試給出：（1）鄰接矩陣。 （2）鄰接表 （3）強(qiáng)連通分量（4）對(duì)照鄰接表，給出從頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷序列。（5）對(duì)照鄰接表，給出從頂點(diǎn)3出發(fā)的深度優(yōu)先遍歷序列。143256圖7-5 一個(gè)有向圖8什么樣的圖其最小生成樹是惟一的？9已知帶權(quán)連通圖G(V,E)鄰接表如圖7-6所示，請(qǐng)畫出該圖，并分別以深度優(yōu)先和廣度優(yōu)先遍歷該圖，寫出遍歷中結(jié)點(diǎn)的序列，并畫出該圖的一棵最小生成樹，其中表結(jié)點(diǎn)的3個(gè)域各為：頂點(diǎn)號(hào)邊上所帶的權(quán)指針v1v2v3v4v54 4 4 18 5 22 5 10 1 161 122 12 1 182 223 163 22 23 44 1

16、0 1.2.34.5圖7-6 連通圖的鄰接表10已知世界6大城市為：北京（B）紐約（N）巴黎（P）倫敦（L）東京（T）墨西哥城（M）試用由表1給出的交通網(wǎng)確定最小生成樹，并說明所使用的方法及其時(shí)間復(fù)雜度。BNPLTMB 109828121124N109585510832P825839792L815539589T211089795113M12432928911311對(duì)于圖7-7所示的帶權(quán)有向圖，采用狄克斯特拉算法求從頂點(diǎn)1到其它頂點(diǎn)的最短路徑，要求給出求解過程。39822 127153426512 12 15131344313204圖7-7 一個(gè)有向圖 圖7-8一個(gè)有向圖 12設(shè)圖7-8中的頂點(diǎn)

17、表示村莊，有向邊代表交通路線，若要建立一家醫(yī)院，試問建在哪個(gè)村莊能使個(gè)村莊總體交通代價(jià)最小。13表2所示給出了某工程各工序之間的優(yōu)先關(guān)系和各工序所需的時(shí)間。表2 某工程各工序關(guān)系表工序代號(hào) A B C D E F G H I J K L M N所需時(shí)間 15 10 50 8 15 40 300 15 120 60 15 30 20 40先驅(qū)工作 - - A,B B C,D B E G,I E I F,I H,J,K L G完成如下各小題：（1）畫出相應(yīng)的AOE網(wǎng)（2）列出事件的最早發(fā)生時(shí)間，最遲發(fā)生時(shí)間。（3）找出關(guān)鍵路徑并指明完成該工程所需的最短時(shí)間。14如圖7-9所示的AOE網(wǎng)，求：（1）

18、每項(xiàng)活動(dòng)ai最早開始時(shí)間e(ai)和最遲開始時(shí)間l(ai)。（2）完成此工程最少需要多少天（設(shè)邊上權(quán)值為天數(shù)）。（3）哪些是關(guān)鍵活動(dòng)a13=2a1=5a2=6a3=3a4=6a5=3a6=3a7=4a12=4a11=2a10=5a9=4a8=113425678910（4）是否存在某項(xiàng)活動(dòng)，當(dāng)其提高速度后能使整個(gè)工程縮短工期？圖7-9五、算法設(shè)計(jì)題1假設(shè)圖G采用鄰接表存儲(chǔ)，分別設(shè)計(jì)實(shí)現(xiàn)以下要求的算法：（1）求出圖G中每個(gè)頂點(diǎn)的入度。（2）求出圖G中每個(gè)頂點(diǎn)的出度（3）求出圖G中出度最大的一個(gè)頂點(diǎn)，輸出該頂點(diǎn)的編號(hào)。（4）計(jì)算圖G中出度為0的頂點(diǎn)數(shù)。（5）判斷圖G中是否存在邊<i,j>

19、。2假設(shè)圖G采用鄰接矩陣存儲(chǔ)，分別設(shè)計(jì)實(shí)現(xiàn)以下要求的算法：（1）求出圖G中每個(gè)頂點(diǎn)的入度。（2）求出圖G中每個(gè)頂點(diǎn)的出度（3）求出圖G中出度最大的一個(gè)頂點(diǎn)，輸出該頂點(diǎn)的編號(hào)。（4）計(jì)算圖G中出度為0的頂點(diǎn)數(shù)。（5）判斷圖G中是否存在邊<i,j>。3設(shè)計(jì)一個(gè)將鄰接表轉(zhuǎn)換為鄰接矩陣的算法。4一個(gè)連通圖采用鄰接表作為存儲(chǔ)機(jī)構(gòu)，設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)從頂點(diǎn)v出發(fā)的深度優(yōu)先遍歷的非遞歸過程。5設(shè)計(jì)一個(gè)算法，求不帶權(quán)無(wú)向連通圖G中距離頂點(diǎn)v的最遠(yuǎn)頂點(diǎn)。6設(shè)計(jì)一個(gè)算法，判斷無(wú)向圖G是否是一棵樹，若是樹，返回1；否則返回0。7假設(shè)圖采用鄰接表存儲(chǔ)，分別寫出基于DFS和BPS遍歷的算法來(lái)判別頂點(diǎn)i和頂點(diǎn)j

20、（i!=j）之間是否有路徑。8假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，判斷無(wú)向圖G是否連通，若連通則返回1；否則返回0。9假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，輸出圖G中從頂點(diǎn)u到v的長(zhǎng)度為1的所有簡(jiǎn)單路徑。10假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，輸出圖G中從頂點(diǎn)u到v的所有簡(jiǎn)單路徑。11假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，從如圖7-10所示的無(wú)向圖G中找出滿足如下條件的一條路徑：（1）給定起點(diǎn)vi和終點(diǎn)vj。（2）給定一組必經(jīng)點(diǎn)7,9，即輸出的路徑必須包含這些頂點(diǎn)。（3）給定一組必避點(diǎn)1,6，即輸出的路徑不能包含這些頂點(diǎn)。01234567891011121314圖7-1012假設(shè)圖G采用鄰接矩陣存儲(chǔ)，采用遍歷方法實(shí)際一個(gè)有向圖的根的算法。若有向圖中存在一個(gè)頂點(diǎn)v，從v可以通過路徑達(dá)達(dá)圖中其它所有頂點(diǎn)，則稱v為該有向圖的根。13假設(shè)圖G采用鄰接矩陣存儲(chǔ)，設(shè)計(jì)一個(gè)算法判斷在給定的有向圖中是否存在一個(gè)簡(jiǎn)單有向回路，若存在，則以頂點(diǎn)序列的方法輸出該回路（找到一條即可）。14采