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

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

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

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

4、特征 C非連通圖不能用深度優(yōu)先搜索法 D圖的遍歷要求每一頂點僅被訪問一次17下列說法中不正確的是_。A無向圖中的極大連通子圖稱為連通分量 B連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點 C圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點 D有向圖的遍歷不可采用廣度優(yōu)先搜索方法18一個有向圖G的鄰接表存儲如下圖7-1所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點v1出發(fā)，所得到的頂點序列是_。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 一個有向圖的鄰接表19對

5、圖7-2所示的無向圖，從頂點1開始進行深度優(yōu)先遍歷，可得到頂點訪問序列_。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 一個無向圖20對圖7-2所示的無向圖，從頂點1開始進行廣度優(yōu)先遍歷，可得到頂點訪問序列_。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一個無向連通圖的生成樹是含有該連通圖的全部頂點的_。A極小連通子圖 B極小子圖C極大連通子圖 D極大子圖22設無向圖 G=(V, E) 和G= (V, E)，如果 G為G的生

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

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

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

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

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

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

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

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

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

15、-4 一個無向圖7對于圖7-5所示的有向圖，試給出：（1）鄰接矩陣。 （2）鄰接表 （3）強連通分量（4）對照鄰接表，給出從頂點1出發(fā)的深度優(yōu)先遍歷序列。（5）對照鄰接表，給出從頂點3出發(fā)的深度優(yōu)先遍歷序列。143256圖7-5 一個有向圖8什么樣的圖其最小生成樹是惟一的？9已知帶權(quán)連通圖G(V,E)鄰接表如圖7-6所示，請畫出該圖，并分別以深度優(yōu)先和廣度優(yōu)先遍歷該圖，寫出遍歷中結(jié)點的序列，并畫出該圖的一棵最小生成樹，其中表結(jié)點的3個域各為：頂點號邊上所帶的權(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)確定最小生成樹，并說明所使用的方法及其時間復雜度。BNPLTMB 109828121124N109585510832P825839792L815539589T211089795113M12432928911311對于圖7-7所示的帶權(quán)有向圖，采用狄克斯特拉算法求從頂點1到其它頂點的最短路徑，要求給出求解過程。39822 127153426512 12 15131344313204圖7-7 一個有向圖 圖7-8一個有向圖 12設圖7-8中的頂點

17、表示村莊，有向邊代表交通路線，若要建立一家醫(yī)院，試問建在哪個村莊能使個村莊總體交通代價最小。13表2所示給出了某工程各工序之間的優(yōu)先關系和各工序所需的時間。表2 某工程各工序關系表工序代號 A B C D E F G H I J K L M N所需時間 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）畫出相應的AOE網(wǎng)（2）列出事件的最早發(fā)生時間，最遲發(fā)生時間。（3）找出關鍵路徑并指明完成該工程所需的最短時間。14如圖7-9所示的AOE網(wǎng)，求：（1）

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

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

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