建設(shè)工程相關(guān)合同管理概述

圖練習圖練習1一、選擇題1.一個有n個頂點的無向圖最多有（ ）條邊。 A.nB.n(n-1)C.n(n-1)/2D.2nC一、選擇題C22.具有6個頂點的無向圖至少應(yīng)有（ ）條邊才能確保是一個連通圖。 A.5B.6C.7D.8

AA33.具有n個頂點且每一對不同的頂點之間都有一條邊的圖被稱為（ ） A.線性圖 B.無向完全圖 C.無向圖 D.簡單圖BB44.具有4個頂點的無向完全圖有（ ）條邊。 A.6B.12C.16D.20A4.具有4個頂點的無向完全圖有（ ）條邊。A55.G是一個非連通無向圖，共有28條邊，則該圖至少有（ ）個頂點。 A.6B.7C.8D.9D5.G是一個非連通無向圖，共有28條邊，則該圖至少有（ ）個66.存儲稀疏圖的數(shù)據(jù)結(jié)構(gòu)常用的是（ ） A.鏈接矩陣 B.三元組 C.鏈接表 D.十字鏈表CC77.對一個具有n個頂點的圖，采用鏈接矩陣表示則該矩陣的大小為（ ） A.n B.(n-1)2

C.(n+1)2 D.n2DD88.設(shè)連通圖G的頂點數(shù)為n，則G的生成樹的邊數(shù)為（ ） A.n-1B.nC.2nD.2n-1A8.設(shè)連通圖G的頂點數(shù)為n，則G的生成樹的邊數(shù)為（ ）A99.N個頂點的無向圖的鏈接表中結(jié)點總數(shù)最多有（ ）個。 A.2nB.nC.n/2D.n(n-1)DD1010.對于一個具有n個頂點和e條邊的無向圖，若采用鏈接表表示，則表向量的大小為（），所有頂點鏈接表的結(jié)點總數(shù)為（）。A.n B.n+1 C.n-1 D.2nE.e/2 F.e G.2e H.n+eAGAG1111.從鏈接矩陣可以看出，該圖共有（ ）個頂點。如果是有向圖，該圖共有（ ）條弧；如果是有向圖，則共有（ ）條邊。A.9 B.3 C.6 D.1E.5 F.4 G.2 H.0BFGBFG1212.在有向圖的鏈接表存儲結(jié)構(gòu)中，頂點V在表結(jié)點中出現(xiàn)的次數(shù)是（） A.頂點v的度 B.頂點v的出度 C.頂點v的入度 D.依附于頂點v的邊CC1313.在用鏈接表表示圖的情況下，建立圖的算法的時間復(fù)雜度為（ ） A.O(n+e) B.O(n2) C.O(n*e) D.O(n3)A13.在用鏈接表表示圖的情況下，建立圖的算法的時間復(fù)雜度為1414.用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時，打印出相應(yīng)的頂點，則輸出的頂點序列是（ ）。A.逆拓撲有序的B.拓撲有序的C.無序的A14.用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時1515.已知一個圖如圖7-13所示，若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的是一種頂點序列為（ ）；按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。 (1)

A.abecdfB.acfebdC.acebfdD.acfdeb (2)A.abcedfB.abcefdC.abedfcD.acfdebDBabcedf圖7-1315.已知一個圖如圖7-13所示，若從頂點a出發(fā)按深度優(yōu)先搜1616.采用鏈接矩陣時，遍歷圖時的頂點所需時間為（ ），采用鏈接表時，遍歷圖的頂點所需時間為（ ）（注：設(shè)圖有n個頂點，e條邊） A.O(n) B.O(n2)C.O(e) D.O(n*e) E.O(n+e)

BE16.采用鏈接矩陣時，遍歷圖時的頂點所需時間為（ ），采用1717.采用鏈接表存儲的圖的深度優(yōu)先搜索遍歷算法類似于二叉樹的（ ）A.中序遍歷 B.先序遍歷C.后序遍歷 D.按層遍歷B17.采用鏈接表存儲的圖的深度優(yōu)先搜索遍歷算法類似于二叉樹1818.采用鏈接表存儲的圖的廣度優(yōu)先搜索遍歷算法類似于二叉樹的（ ）A.中序遍歷 B.先序遍歷C.后序遍歷 D.按層遍歷D18.采用鏈接表存儲的圖的廣度優(yōu)先搜索遍歷算法類似于二叉樹1919.已知一有向圖的鏈接表存儲結(jié)構(gòu)如圖7-14（見下頁）所示。（1）根據(jù)有向圖的深度優(yōu)先搜索遍歷算法，從頂點V1出發(fā)，所得到的頂點序列是（ ）。 A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2（2）根據(jù)有向圖的廣度優(yōu)先搜索遍歷算法，從頂點V1出發(fā)，所得到的頂點序列是（ ）。A.v1,v2,v3,v5,v4B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2CB19.已知一有向圖的鏈接表存儲結(jié)構(gòu)如圖7-14（見下頁）所20v1v2^v3v4^v5213

^34

^13^01234圖7-14v1213^34^13^0圖7-12120.已知有8個頂點值為A，B，C，D，E，F(xiàn)，G，H的無向圖，其鄰接矩陣的存儲結(jié)構(gòu)如圖7-15所示（見下頁）。由此結(jié)構(gòu)，從A頂點開始深度優(yōu)先搜索遍歷，得到的頂點序列是（ ）。

A.ABCDGHFEB.ABCDGFHEC.ABGHFECDD.ABFHEGDC

E.ABEHFGDCF.ABEHGFCDB20.已知有8個頂點值為A，B，C，D，E，F(xiàn)，G，H的無22

A

B

C

D

E

F

G

H

A01010000

B10101110

C01010000

D10100010

E01000001

F01000011

G01010101

H00001110圖7-15

ABCDEFGHA02321.已知一個圖如圖7-16（見下頁）所示，在該圖的最小生成樹中各條邊上權(quán)值之和為（ ），在該圖的最小生成樹中，從頂點V1到頂點V6的路徑為（ ）

A.31 B.38C.36 D.43E.v1,v3.v6 F.v1,v4,v6G.v1,v5,v4,v6 H.v1,v4,v3,v6CG21.已知一個圖如圖7-16（見下頁）所示，在該圖的最小生24圖7-1631254612152010988645圖7-16312546121520109886452522.已知一個圖如圖7-17所示，則依據(jù)迪杰斯特拉算法將按照（ ）頂點次序依次求出從頂點V1到其余各頂點的最短路徑。A.v2,v5,v4,v6,v3B.v2,v5,v4,v3,v6C.v2,v3,v5,v4,v1D.v5,v4,v6,v3,v2B圖7-17312546312756151022.已知一個圖如圖7-17所示，則依據(jù)迪杰斯特拉算法將按2623.在一個有n個頂點的無向網(wǎng)中，有 條邊，則應(yīng)該選用( )算法來求這個網(wǎng)的最小生成樹，從而使計算時間較少。A.PrimB.KruskalB23.在一個有n個頂點的無向網(wǎng)中，有2724.關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中的（）A.從源點到匯點的最長路徑B.從源點到匯點的最短路徑C.最長回路D.最短回路A24.關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中的（）A2825.正確的AOE網(wǎng)而言，必須是（ ），AOE中，某邊權(quán)值應(yīng)當是（ ）權(quán)值為零的邊表示（ ）（1） A.完全圖 B.哈密爾頓圖 C.無環(huán)圖 D.強連通圖（2） A.實數(shù) B正整數(shù) C.正數(shù) D.非負數(shù)（3） A.為決策而增加的活動 B.為計算方便而增加的活動 C.表示活動間的時間順序關(guān)系 D.該活動為關(guān)鍵活動CDB25.正確的AOE網(wǎng)而言，必須是（ ），AOE中，某邊權(quán)2926.當各邊上權(quán)值（ ）時，BFS算法可以用解決單源點最短路徑的問題。A.均相等

B.均不相等

C.不一定相等

A26.當各邊上權(quán)值（ ）時，BFS算法可以用解決單源點最短3027.已知一個圖如圖7-18所示，則由該圖得到的一種拓撲序列為（ ）A.v1,v4,v6,v2,v5,v3B.v1,v2,v3,v4,v5,v6 C.v1,v4,v2,v3,v6,v5D.v1,v2,v4,v6,v3,v5

A圖7-1831254627.已知一個圖如圖7-18所示，則由該圖得到的一種拓撲序列3128.判斷一個有向圖是否存在回路，除了可以利用拓撲排序方法外，還可以利用（ ）。A.求關(guān)鍵路徑的方法B.求最短路徑的Dijksra方法C.深度優(yōu)先搜索遍歷算法D.廣度優(yōu)先搜索遍歷算法C28.判斷一個有向圖是否存在回路，除了可以利用拓撲排序方法3229.下面結(jié)論中正確的是（ ）A.在無向圖中，邊的條數(shù)是結(jié)點度數(shù)之和。B.在圖結(jié)構(gòu)中，結(jié)點可以沒有任何前趨和后繼.。C.在n個結(jié)點的無向圖中，若邊數(shù)大于n-1，則該圖必是連通圖。D.圖的鏈接矩陣必定是對稱矩陣B29.下面結(jié)論中正確的是（ ）B3330.下面結(jié)論中正確的是（ ）A.若有向圖的鏈接矩陣中對角線以下元素均為零，則該圖的拓撲排序必定存在B.網(wǎng)絡(luò)的最小代價生成樹是惟一的C.在拓撲排序序列中，任意兩個相繼結(jié)點vi和vj都存在從vi到vj的路徑D.在有向圖中，從一個結(jié)點到另一個結(jié)點的最短路徑是惟一的

A30.下面結(jié)論中正確的是（ ）A3431.下面結(jié)論中不正確的是（ ） A.

無向圖的連通分量是該圖的極大連通子圖 B.

有向圖用鏈接矩陣表示，容易實現(xiàn)求結(jié)點度數(shù)的操作。 C.

無向圖用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩陣元素之和的一半 D.

有向圖的鄰接矩陣必定不是對稱矩陣D31.下面結(jié)論中不正確的是（ ）D3532.下面結(jié)論中正確的是（ ） A.

按深度優(yōu)先搜索遍歷圖時，與始點相連的結(jié)點先于不在始點相連的結(jié)點訪問。 B.

一個圖按深度優(yōu)先搜索法遍歷的結(jié)果是唯一的。 C.

若有向圖G中包含一個環(huán)，則G的結(jié)點間不存在在拓撲序列。 D.

圖的拓撲排序序列是唯一的。C32.下面結(jié)論中正確的是（ ）C3633.下面結(jié)論中不正確的是（ ） A．

按廣度優(yōu)先搜索遍歷圖時，與始點相連的結(jié)點先于不于始點相連的結(jié)點訪問。 B．

一個圖按廣度優(yōu)先搜索法遍歷的結(jié)果是唯一的。 C．無向圖的鏈接表表示法中，表中結(jié)點的數(shù)目是圖中邊的條數(shù)2倍。 D．圖的多重鏈接表表示法中，表中結(jié)點的數(shù)目是圖中邊的條數(shù)。B33.下面結(jié)論中不正確的是（ ）B3734.下面結(jié)論中正確的是（ ） A.在無向圖中，邊的條數(shù)是結(jié)點度數(shù)之和。 B．

用Prim算法和Kruskal算法求得的圖最小生成樹相同。 C．

在圖的連接多重表表示中，任意一條邊，只用一個表目表示。 D．在拓撲排序序列中，任意兩個相距結(jié)點Vi和Vj之間都存在一條路徑。C34.下面結(jié)論中正確的是（ ）C38二、填空題1.N個頂點的連通圖至少_____條邊。

n-1二、填空題n-1392.一個無向圖有n個頂點和e條邊，則所有頂點的度數(shù)之和即Σdi（di表示頂點I的度）=_____。

2e2e403.在圖形結(jié)構(gòu)中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以_______________。

任意多個任意多個414.若無向圖G的頂點度數(shù)的最小值大于或等于____時，G至少有一條回路。

2

4.若無向圖G的頂點度數(shù)的最小值大于或等于____時，G至少425.設(shè)無向圖G的頂點數(shù)為n,圖G最少有_____邊，最多有_________條邊，若G為有向圖，有n個頂點，則圖G最少______條邊，最多有_________條邊。具有n個頂點的無向完全圖，邊的總數(shù)為_____________條，而具有n個頂點的有向完全圖中，邊數(shù)有__________條。

0n(n-1)/20n(n-1)n(n-1)/2n(n-1)5.設(shè)無向圖G的頂點數(shù)為n,圖G最少有_____邊，最多有436.在無權(quán)圖G的鏈接矩陣A中，若（Vi,Vj）或<Vi,Vj>屬于圖G的邊集合，則對應(yīng)元素A[i][j]等于_____，否則等于_____。

1010447.在無向圖G的鏈接矩陣A中，若A[i][j]等于1，則A[j][i]等于_____。

1

1458.已知一個圖的鏈接矩陣表示，計算第i個結(jié)點的入度的方法是_____。

求矩陣第i列非零元素之和求矩陣第i列非零元素之和469.在一個圖G的鏈接表表示中，每個頂點的鏈接表中所含的結(jié)點數(shù)，對于有向圖而言等于該頂點的_____，而對于無向圖而言等于該頂點的_____。

出度數(shù)度數(shù)出度數(shù)度數(shù)4710.假定一個無向圖，有n個頂點e條邊，則在鏈接矩陣表示中，求任一個頂點度數(shù)的時間復(fù)雜度為_____；用鏈接表表示中，訪問一個頂點的所有鏈接點的時間復(fù)雜度為________。

O(n)O(e*n)O(n)O(e*n)4811.已知圖G的鏈接表如圖7-19(見下頁)所示，其從頂點V1出發(fā)的深度優(yōu)先搜索序列為___________________________，其從頂點V1出發(fā)的廣度優(yōu)先搜索序列為________________________________。

v1,v2,v3,v6,v5,v4v1,v2,v5,v4,v3,v6

v1,v2,v3,v6,v5,v4v1,v2,v5,v4,v49圖7-19v1v2v3v4^v5v6^143

^24^0123455

^352

^圖7-19v1143^24^055012.設(shè)圖G有n個頂點和e條邊，以鏈接表作存儲結(jié)構(gòu)時，進行深度優(yōu)先搜索遍歷的時間復(fù)雜度為_________；以鏈接矩陣作存儲結(jié)構(gòu)時，進行廣度優(yōu)先搜索遍歷的時間復(fù)雜度為_____。

O(n+e)

O(n2)

O(n+e)O(n2)5113.對用鏈接矩陣表示的圖進行深度優(yōu)先或廣度優(yōu)先搜索遍歷的時間復(fù)雜度為_____，對用鏈接表表示的圖進行深度優(yōu)先或廣度優(yōu)先搜索遍歷時是時間復(fù)雜度為_________，圖的深度優(yōu)先或廣度優(yōu)先搜索遍歷的空間復(fù)雜度為_____。

O(n+e)

O(n2)

O(n)

O(n+e)O(n2)O(n)5214.n個頂點的弱連通有向圖G，最多有________條邊，最少有_____條邊。

n(n-1)n-1n(n-1)n-15315.在n個頂點、e條