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

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

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

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

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

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

^34

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

A.ABCDGHFEB.ABCDGFHEC.ABGHFECDD.ABFHEGDC

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

A

B

C

D

E

F

G

H

A01010000

B10101110

C01010000

D10100010

E01000001

F01000011

G01010101

H00001110圖7-15

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

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

B.均不相等

C.不一定相等

A26.當(dāng)各邊上權(quán)值（ ）時(shí)，BFS算法可以用解決單源點(diǎn)最短3027.已知一個(gè)圖如圖7-18所示，則由該圖得到的一種拓?fù)湫蛄袨椋?）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.已知一個(gè)圖如圖7-18所示，則由該圖得到的一種拓?fù)湫蛄?128.判斷一個(gè)有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用（ ）。A.求關(guān)鍵路徑的方法B.求最短路徑的Dijksra方法C.深度優(yōu)先搜索遍歷算法D.廣度優(yōu)先搜索遍歷算法C28.判斷一個(gè)有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒?229.下面結(jié)論中正確的是（ ）A.在無(wú)向圖中，邊的條數(shù)是結(jié)點(diǎn)度數(shù)之和。B.在圖結(jié)構(gòu)中，結(jié)點(diǎn)可以沒(méi)有任何前趨和后繼.。C.在n個(gè)結(jié)點(diǎn)的無(wú)向圖中，若邊數(shù)大于n-1，則該圖必是連通圖。D.圖的鏈接矩陣必定是對(duì)稱矩陣B29.下面結(jié)論中正確的是（ ）B3330.下面結(jié)論中正確的是（ ）A.若有向圖的鏈接矩陣中對(duì)角線以下元素均為零，則該圖的拓?fù)渑判虮囟ù嬖贐.網(wǎng)絡(luò)的最小代價(jià)生成樹(shù)是惟一的C.在拓?fù)渑判蛐蛄兄校我鈨蓚€(gè)相繼結(jié)點(diǎn)vi和vj都存在從vi到vj的路徑D.在有向圖中，從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的最短路徑是惟一的

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

無(wú)向圖的連通分量是該圖的極大連通子圖 B.

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

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

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

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

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

若有向圖G中包含一個(gè)環(huán)，則G的結(jié)點(diǎn)間不存在在拓?fù)湫蛄小?D.

圖的拓?fù)渑判蛐蛄惺俏ㄒ坏?。C32.下面結(jié)論中正確的是（ ）C3633.下面結(jié)論中不正確的是（ ） A．

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

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

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

在圖的連接多重表表示中，任意一條邊，只用一個(gè)表目表示。 D．在拓?fù)渑判蛐蛄兄校我鈨蓚€(gè)相距結(jié)點(diǎn)Vi和Vj之間都存在一條路徑。C34.下面結(jié)論中正確的是（ ）C38二、填空題1.N個(gè)頂點(diǎn)的連通圖至少_____條邊。

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

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

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

2

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

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

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

1

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

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

出度數(shù)度數(shù)出度數(shù)度數(shù)4710.假定一個(gè)無(wú)向圖，有n個(gè)頂點(diǎn)e條邊，則在鏈接矩陣表示中，求任一個(gè)頂點(diǎn)度數(shù)的時(shí)間復(fù)雜度為_(kāi)____；用鏈接表表示中，訪問(wèn)一個(gè)頂點(diǎn)的所有鏈接點(diǎn)的時(shí)間復(fù)雜度為_(kāi)_______。

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

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個(gè)頂點(diǎn)和e條邊，以鏈接表作存儲(chǔ)結(jié)構(gòu)時(shí)，進(jìn)行深度優(yōu)先搜索遍歷的時(shí)間復(fù)雜度為_(kāi)________；以鏈接矩陣作存儲(chǔ)結(jié)構(gòu)時(shí)，進(jìn)行廣度優(yōu)先搜索遍歷的時(shí)間復(fù)雜度為_(kāi)____。

O(n+e)

O(n2)

O(n+e)O(n2)5113.對(duì)用鏈接矩陣表示的圖進(jìn)行深度優(yōu)先或廣度優(yōu)先搜索遍歷的時(shí)間復(fù)雜度為_(kāi)____，對(duì)用鏈接表表示的圖進(jìn)行深度優(yōu)先或廣度優(yōu)先搜索遍歷時(shí)是時(shí)間復(fù)雜度為_(kāi)________，圖的深度優(yōu)先或廣度優(yōu)先搜索遍歷的空間復(fù)雜度為_(kāi)____。

O(n+e)

O(n2)

O(n)

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

n(n-1)n-1n(n-1)n-15315.在n個(gè)頂點(diǎn)、e條