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

第7章圖一、單項選擇題１.在一個無向圖G中，所有頂點得度數(shù)之與等于所有邊數(shù)之與得______倍.A。l/2 B．1C.2?D.4２.在一個有向圖中，所有頂點得入度之與等于所有頂點得出度之與得＿＿＿___倍。A．l／2?Ｂ。1C．2?D。43.一個具有n個頂點得無向圖最多包含__＿___條邊。A。n?B。n+１Ｃ．n—1 D.n（n-1）／2４.一個具有n個頂點得無向完全圖包含______條邊。Ａ.n(ｎ—l) Ｂ。ｎ（n+ｌ)C。n（n－l）/2 Ｄ。n（ｎ—l）/２5．一個具有ｎ個頂點得有向完全圖包含____＿_條邊。A。n（ｎ－１）?B。ｎ(n+l）C．n(ｎ－l）／２ D。n（n+l)／26.對于具有ｎ個頂點得圖,若采用鄰接矩陣表示,則該矩陣得大小為__＿__＿。A。n Ｂ.n×nC。n－1?Ｄ。(n-l)×（n－l）７．無向圖得鄰接矩陣就是一個_＿____。A.對稱矩陣?B.零矩陣Ｃ。上三角矩陣 Ｄ.對角矩陣8．對于一個具有n個頂點與ｅ條邊得無（有）向圖，若采用鄰接表表示，則表頭向量得大小為__＿＿__。Ａ.n?B.eＣ．2n D．２e9．對于一個具有ｎ個頂點與e條邊得無（有）向圖，若采用鄰接表表示，則所有頂點鄰接表中得結(jié)點總數(shù)為＿_＿___。A.n?Ｂ.ｅC。2n?D.２e10。在有向圖得鄰接表中,每個頂點鄰接表鏈接著該頂點所有______鄰接點.Ａ．入邊?Ｂ．出邊C。入邊與出邊?Ｄ。不就是入邊也不就是出邊11。在有向圖得逆鄰接表中，每個頂點鄰接表鏈接著該頂點所有___＿__鄰接點。A.入邊 B．出邊Ｃ.入邊與出邊 D．不就是人邊也不就是出邊12。如果從無向圖得任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點,則該圖一定就是＿___＿＿。A.完全圖 B.連通圖C．有回路 D．一棵樹13。采用鄰接表存儲得圖得深度優(yōu)先遍歷算法類似于二叉樹得__＿___算法。Ａ。先序遍歷 B.中序遍歷Ｃ。后序遍歷?D。按層遍歷14。采用鄰接表存儲得圖得廣度優(yōu)先遍歷算法類似于二叉樹得＿__＿__算法。A.先序遍歷?Ｂ.中序遍歷C．后序遍歷 D。按層遍歷1５．如果無向圖G必須進行二次廣度優(yōu)先搜索才能訪問其所有頂點，則下列說法中不正確得就是＿____＿。A.G肯定不就是完全圖?B.G一定不就是連通圖C．G中一定有回路?D。G有二個連通分量16.下列有關(guān)圖遍歷得說法不正確得就是___＿＿_。Ａ.連通圖得深度優(yōu)先搜索就是一個遞歸過程B。圖得廣度優(yōu)先搜索中鄰接點得尋找具有“先進先出”得特征C。非連通圖不能用深度優(yōu)先搜索法D．圖得遍歷要求每一頂點僅被訪問一次17。下列說法中不正確得就是_＿_＿_＿。A．無向圖中得極大連通子圖稱為連通分量Ｂ。連通圖得廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過得頂點C.圖得深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過得頂點D.有向圖得遍歷不可采用廣度優(yōu)先搜索方法1８。一個有向圖G得鄰接表存儲如下圖７－1所示,現(xiàn)按深度優(yōu)先搜索遍歷，從頂點v1出發(fā)，所得到得頂點序列就是_＿＿_＿_.Ａ．v１，v2,v３，v4，v5?B．v１,v２,ｖ3，v5,v４C。ｖ1，v２，v4，ｖ5,ｖ3?D.v1,ｖ２，v５,ｖ3,ｖ42234∧35∧5∧4∧v1v2v3v4∧v5圖7—1一個有向圖得鄰接表19.對圖７—2所示得無向圖，從頂點1開始進行深度優(yōu)先遍歷,可得到頂點訪問序列_＿__＿＿。A.１,2,4,３,５，７,６B．１,2，4，3，5,6，7C。1,2，４，5，6，3，７D．1,２，３,4，5,7，6161654327圖7－2一個無向圖2０.對圖7—２所示得無向圖,從頂點1開始進行廣度優(yōu)先遍歷，可得到頂點訪問序列___＿_＿.A.１，3,２，4,5，6,7 B。1,2，4，３，5,6，７Ｃ。１，２，3,４，5，7，6?Ｄ.２,５，1，4,7，３，６2１。一個無向連通圖得生成樹就是含有該連通圖得全部頂點得___＿＿_。A。極小連通子圖 B.極小子圖C。極大連通子圖 Ｄ。極大子圖22.設(shè)無向圖Ｇ＝(V，Ｅ）與G’=（V’,E'）,如果G’為G得生成樹,則下列說法中不正確得就是__＿＿_＿.Ａ．Ｇ’為G得連通分量B。G’為G得無環(huán)子圖C.G'為G得子圖Ｄ．G’為G得極小連通子圖且Ｖ’＝V２3、任意一個無向連通圖______最小生成樹。Ａ.只有一棵?Ｂ．有一棵或多棵Ｃ．一定有多棵?D?？赡懿淮嬖冢?．對于含有ｎ個頂點得帶權(quán)連通圖，它得最小生成樹就是指圖中任意一個＿____＿__。A．由ｎ—1條權(quán)值最小得邊構(gòu)成得子圖。Ｂ.由n－1條權(quán)值之與最小得邊構(gòu)成得子圖。Ｃ.由n—1條權(quán)值之與最小得邊構(gòu)成得連通子圖.Ｄ．由n個頂點構(gòu)成得邊得權(quán)值之與最小得生成樹.25。若一個有向圖中得頂點不能排成一個拓撲序列，則可斷定該有向圖_______。A。就是個有根有向圖Ｂ.就是個強連通圖C.含有多個入度為０得頂點Ｄ.含有頂點數(shù)目大于1得強連通分量26．判定一個有向圖就是否存在回路除了可以利用拓撲排序方法外，還可以用＿___。A．求關(guān)鍵路徑得方法?B．求最短路徑得Ｄijkｓｔrａ算法C．廣度優(yōu)先遍歷算法?D.深度優(yōu)先遍歷算法27。求最短路徑得Diｊｋstｒa算法得時間復(fù)雜度為__＿＿＿＿。A。O(n) B．O（n+e）C。O(n2)?D．O（ne）２８。求最短路徑得Floyd算法得時間復(fù)雜度為＿____＿。A．Ｏ（n） Ｂ.O（ne)C．Ｏ(ｎ2) D。O（n3)29．關(guān)鍵路徑就是事件結(jié)點網(wǎng)絡(luò)中_____＿.A.從源點到匯點得最長路徑?B。從源點到匯點得最短路徑C。最長得回路 D．最短得回路30.下面說法不正確得就是___＿__.Ａ.在AＯE網(wǎng)中,減少任一關(guān)鍵活動得權(quán)值后,整個工期也就相應(yīng)減少B．AOE網(wǎng)工程工期為關(guān)鍵活動得權(quán)值與C.在關(guān)鍵路徑上得活動都就是關(guān)鍵活動，而關(guān)鍵活動也必須在關(guān)鍵路徑上D．A與B31．下面說法不正確得就是_＿＿__＿.A．關(guān)鍵活動不按期完成就會影響整個工程得完成時間B.任何一個關(guān)鍵活動提前完成，將使整個工程提前完成C。所有關(guān)鍵活動都提前完成，則整個工程提前完成Ｄ.某些關(guān)鍵活動若提前完成,將使整個工程提前完成二、填空題1．對于具有n個頂點得無向圖Ｇ最多有________＿條邊。2。對于具有n個頂點得強連通有向圖G至少有_＿_＿_＿__＿條邊。3.對于具有ｎ個頂點得有向圖，每個頂點得度最大可達____＿______.4．若無向圖G得頂點度數(shù)最小值大于___＿___＿_＿＿時,Ｇ至少有一條回路。5．對于一個具有ｎ個頂點與e條邊得無向圖，若采用鄰接表表示,則表頭向量得大小為_______＿＿__，所有鄰接表中得結(jié)點總數(shù)就是_＿_＿__＿___。6。已知一個有向圖得鄰接矩陣表示，刪除所有從第ｉ個結(jié)點出發(fā)得弧得方法就是__＿＿_____＿__。7.對于n個頂點得無向圖,采用鄰接矩陣表示，求圖中邊數(shù)得方法就是__＿__＿_＿_＿,判斷任意兩個頂點i與j就是否有邊相連得方法就是________＿_,求任意一個頂點得度得方法就是_＿_________。８．對于ｎ個頂點得有向圖，采用鄰接矩陣表示，求圖中邊數(shù)得方法就是____＿_＿__，判斷任意兩個頂點i與j就是否有邊相連得方法就是＿＿＿_______,求任意一個頂點得度得方法就是_＿_＿＿＿__＿＿.9．無向圖得連通分量就是指＿___＿＿_____.10.已知圖Ｇ得鄰接表如圖7－3所示，從頂點ｖ1出發(fā)得深度優(yōu)先搜索序列為____＿＿＿_,從頂點1出發(fā)得廣度優(yōu)先搜索序列為______＿_____＿。vv1v2v3v4∧v5v6∧234∧35∧6∧463∧圖7－3圖G得鄰接表１1.n個頂點連通圖得生成樹一定有＿＿____＿___條邊。1２。一個連通圖得_＿＿_＿＿_____就是一個極小連通子圖。13.Prim算法適用于求________＿得網(wǎng)得最小生成樹,Ｋruskａl算法適用于求___＿__＿_得網(wǎng)得最小生成樹。1４.在ＡOＶ圖中,頂點表示＿＿_＿_＿__,有向邊表示__＿＿_＿＿_。1５.可以進行拓撲排序得有向圖一定就是＿____＿＿＿_。１6。從源點到匯點長度最長得路徑稱為關(guān)鍵路徑,該路徑上得活動稱為_＿＿＿____。17.Dijkstra算法從源點到其它各頂點得路徑長度按＿_＿_＿___次序依次產(chǎn)生,該算法在邊上得權(quán)出現(xiàn)_＿_＿____＿情況時,不能正確產(chǎn)生最短路徑。18.求從某源點到其余各項點得Ｄijkstra算法在圖得頂點數(shù)為１0，用鄰接矩陣表示圖時計算時間約為10ms,則在圖得頂點數(shù)為4０時，計算時間約為_______＿_ms。三、判斷題1.具有n個頂點得無向圖至多有n(ｎ-1)條邊。2。有向圖中各頂點得入度之與等于各頂點得出度之與.3。鄰接矩陣只儲存了邊得信息，沒有存儲頂點得信息。4。對同一個有向圖，只保存出邊得鄰接表中結(jié)點得數(shù)目總就是與只保存入邊得鄰接表中結(jié)點得數(shù)目一樣多.５．如果表示圖得鄰接矩陣就是對稱矩陣，則該圖一定就是無向圖。6。如果表示有向圖得鄰接矩陣就是對稱矩陣,則該有向圖一定就是有向完全圖。７．如果表示某個圖得鄰接矩陣不就是對稱矩陣,則該圖一定就是有向圖。8。連通分量就是無向圖得極小連通子圖.9。強連通分量就是有向圖得極大連通子圖。１０.對有向圖G，如果以任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每一個頂點，則該圖一定就是完全圖.11。連通圖得廣度優(yōu)先搜索中一般要采用隊列來暫時剛訪問過得頂點。1２.圖得深度優(yōu)先搜索中一般要采用棧來暫時剛訪問過得頂點。１3。有向圖得遍歷不可采用廣度優(yōu)先搜索方法。14。連通圖得生成樹包含了圖中所有頂點。15.設(shè)G為具有n個頂點得連通圖，如果其中得某個子圖有n個頂點，ｎ—1條邊，則該子圖一定就是G得生成樹。１６．最小生成樹就是指邊數(shù)最小得生成樹。17.從ｎ個頂點得連通圖中選取n—1條權(quán)值最小得邊,即可構(gòu)成最小生成樹。1８。只要無向網(wǎng)中沒有權(quán)值相同得邊，其最小生成樹就就是惟一得。1９.只要無向網(wǎng)中有權(quán)值相同得邊,其最小生成樹就可能不就是惟一得。20。有環(huán)圖也能進行拓撲排序。21.拓撲排序算法僅適用于有向無環(huán)圖。２２。任何有向無環(huán)圖得結(jié)點都可以排成拓撲排序，而且拓撲序列不惟一。23。關(guān)鍵路徑就是由權(quán)值最大得邊構(gòu)成得.24。在AＯE網(wǎng)中，減小任一關(guān)鍵活動上得權(quán)值后,整個工期也就相應(yīng)減小。25．在AＯE網(wǎng)中工程工期為關(guān)鍵活動上權(quán)值之與。２6.在關(guān)鍵路徑得活動都就是關(guān)鍵活動，而關(guān)鍵活動未必在關(guān)鍵路徑上.27。關(guān)鍵活動不按期完成就會影響整個工程得完成時間。28。所有關(guān)鍵活動都提前完成，則整個工程將提前完成。29．某些關(guān)鍵活動若提前完成，將可能使整個工程提前完成。30．求單源最短路徑得狄克斯特拉算法不適用于有回路得有向網(wǎng)。四、簡答題1.圖Ｇ就是一個非連通無向圖,共有2８條邊,則該圖至少有多少個頂點?2．用鄰接矩陣表示圖時,矩陣元素得個數(shù)與頂點個數(shù)就是否相關(guān)？與邊得條數(shù)就是否有關(guān)?3.對于稠密圖與稀疏圖，就存儲而言,采用鄰接矩陣與鄰接表哪個更好些？4.請回答下列關(guān)于圖得一些問題：（1）有n個頂點得有向強連通圖最多有多少條邊？最少有多少條邊？（２）表示一個有１00０個頂點,1０00條邊得有向圖得鄰接矩陣有多少個矩陣元素？就是否為稀疏矩陣？（３）對于一個有向圖，不用拓撲排序,如何判斷圖就是否存在環(huán)?5.對ｎ個頂點得無向圖與有向圖，采用鄰接表表示時,如何判別下列有關(guān)問題？（1）圖中有多少條邊？(2)任意兩個頂點ｉ與ｊ就是否有邊相連？(3）任意一個頂點得度就是多少？6.給出如圖7－4所示得無向圖G得鄰接矩陣與鄰接表兩種存儲結(jié)構(gòu)。并在給定得鄰接表基礎(chǔ)上，指出從頂點1出發(fā)得深度優(yōu)先遍歷與廣度優(yōu)先遍歷序列。112543圖7—4一個無向圖7.對于圖7-５所示得有向圖，試給出:（１）鄰接矩陣.(２）鄰接表（3)強連通分量(4）對照鄰接表，給出從頂點1出發(fā)得深度優(yōu)先遍歷序列。（5)對照鄰接表，給出從頂點3出發(fā)得深度優(yōu)先遍歷序列。1143256圖７－5一個有向圖８．什么樣得圖其最小生成樹就是惟一得？９.已知帶權(quán)連通圖G（V，E)鄰接表如圖7－6所示,請畫出該圖,并分別以深度優(yōu)先與廣度優(yōu)先遍歷該圖，寫出遍歷中結(jié)點得序列,并畫出該圖得一棵最小生成樹，其中表結(jié)點得3個域各為：頂點號邊上所帶得權(quán)指針v1v1v2v3v4v544∧418∧522∧510∧116112212118222316322234410∧2、3４、5圖7-6連通圖得鄰接表10.已知世界6大城市為：北京(B)紐約（N)巴黎(P）倫敦（L)東京（Ｔ）墨西哥城（M）試用由表１給出得交通網(wǎng)確定最小生成樹，并說明所使用得方法及其時間復(fù)雜度。BNPLTMＢ1Ｎ1P８２583９79２L81５５３958９T211089795113Ｍ124329２8９１1311．對于圖7—7所示得帶權(quán)有向圖,采用狄克斯特拉算法求從頂點１到其它頂點得最短路徑,要求給出求解過程。39398221271534265121215131344313204圖７—7一個有向圖圖7—8一個有向圖12．設(shè)圖7-8中得頂點表示村莊,有向邊代表交通路線，若要建立一家醫(yī)院，試問建在哪個村莊能使個村莊總體交通代價最小。13。表2所示給出了某工程各工序之間得優(yōu)先關(guān)系與各工序所需得時間.表2某工程各工序關(guān)系表工序代號ＡBCＤEFＧHIJＫLＭN所需時間15105081５40３0０15１２０６015３02040先驅(qū)工作—－A，BＢＣ,DBEG,IEIＦ,ＩH,J，KLＧ完成如下各小題：(1）畫出相應(yīng)得AOＥ網(wǎng)（2）列出事件得最早發(fā)生時間,最遲發(fā)生時間。（3)找出關(guān)鍵路徑并指明完成該工程所需得最短時間。1４。如圖7—９所示得AOＥ網(wǎng)，求:（１）每項活動ａi最早開始時間ｅ（aｉ）與最遲開始時間ｌ（aｉ）.（2）完成此工程最少需要多少天（設(shè)邊上權(quán)值為天數(shù)）。(3)哪些就是關(guān)鍵活動a13=2a13=2a1=5a2=6a3=3a4=6a5=3a6=3a7=4a12=4a11=2a10=5a9=4a8=113425678910圖7－9五、算法設(shè)計題1.假設(shè)圖Ｇ采用鄰接表存儲,分別設(shè)計實現(xiàn)以下要求得算法：（1）求出圖G中每個頂點得入度。（2）求出圖G中每個頂點得出度（３）求出圖G中出度最大得一個頂點,輸出該頂點得編號.（4)計算圖Ｇ中出度為０得頂點數(shù).(5)判斷圖Ｇ中就是否存在邊<ｉ，j>。2．假設(shè)圖G采用鄰接矩陣存儲,分別設(shè)計實現(xiàn)以下要求得算法：（1)求出圖G中每個頂點得入度。（2）求出圖G中每個頂點得出度（3)求出圖G中出度最大得一個頂點，輸出該頂點得編號。（４）計算圖G中出度為0得頂點數(shù)。（５）判斷圖G中就是否存在邊<i,ｊ>。３.設(shè)計一個將鄰接表轉(zhuǎn)換為鄰接矩陣得算法.4．一個連通圖采用鄰接表作為存儲機構(gòu)，設(shè)計一個算法實現(xiàn)從頂點ｖ出發(fā)得深度優(yōu)先遍歷得非遞歸過程。5。設(shè)計一個算法,求不帶權(quán)無向連通圖Ｇ中距離頂點ｖ得最遠頂點。6．設(shè)計一個算法,判斷無向圖G就是否就是一棵樹,若就是樹，返回1；否則返回0。７。假設(shè)圖采用鄰接表存儲，分別寫出基于DFＳ與BPS遍歷得算法來判別頂點ｉ與頂點j(ｉ!=j)之間就是否有路徑.８。假設(shè)圖G采用鄰接表存儲,設(shè)計一個算法,判斷無向圖G就是否連通，若連通則返回1；否則返回0。9。假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，輸出圖G中從頂點u到v得長度為１得所有簡單路徑。１0．假設(shè)圖G采用鄰接表存儲,設(shè)計一個算法，輸出圖G中從頂點ｕ到v得所有簡單路徑。11．假設(shè)圖G采用鄰接表存儲,設(shè)計一個算法，從如圖７-10所示得無向圖Ｇ中找出滿足如下條件得一條路徑：（1）給定起點ｖi與終點ｖj。(2)給定一組必經(jīng)點｛7,9｝,即輸出得路徑必須包含這些頂點。(3）給定一組必避點｛1，6｝,即輸出得路徑不能包含這些頂點。001234567891011121314圖7-１0１2。假設(shè)圖