【數(shù)據(jù)結(jié)構(gòu)期末試題及答案】樣卷7

1、2020學(xué)年數(shù)據(jù)結(jié)構(gòu)期末試題及答案（七）、選擇題1、12、對于具有n個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為（A. nB. n 2C. n-1D. （n-1）2、如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是 （ ）。A.完全圖B.連通圖C.有回路 D. 一棵樹 TOC o 1-5 h z 3、關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（）。A.從源點到匯點的最長路徑B.從源點到匯點的最短路徑C.最長的回路D.最短的回路4、下面（）可以判斷出一個有向圖中是否有環(huán)（回路）。A.廣度優(yōu)先遍歷B. 拓撲排序C.求最短路徑D.求關(guān)鍵路徑5、帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入

2、度等于 人中（）。A.第i行非無窮的元素之和B.第i列非無窮的元素個數(shù)之和C.第i行非無窮且非0的元素個數(shù)D.第i行與第i列非無窮且非0的元素之和 6、采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的（）。A.中序遍歷B.先序遍歷C.后序遍歷D.按層次遍歷7、無向圖的鄰接矩陣是一個（）。A.對稱矩陣B.零矩陣C.上三角矩陣D.對角矩陣 8、當(dāng)利用大小為 N的數(shù)組存儲循環(huán)隊列時，該隊列的最大長度是（）。A. N-2B. N-1C. ND. N+19、鄰接表是圖的一種（）。A.順序存儲結(jié)構(gòu)B.鏈式存儲結(jié)構(gòu) C.索引存儲結(jié)構(gòu)D.散列存儲結(jié)構(gòu)10、下面有向圖所示的拓撲排序的結(jié)果序列是（）。D. 521

3、643A. 125634B. 516234C. 12345611、在無向圖中定義頂點vi與vj之間的路徑為從 vi到vj的一個（）。A. 頂點序列 B.邊序列C.權(quán)值總和D.邊的條數(shù)12、在有向圖的逆鄰接表中，每個頂點鄰接表鏈接著該頂點所有（）鄰接點。A.入邊B,出邊C.入邊和出邊D,不是出邊也不是入邊 TOC o 1-5 h z 13、設(shè) G1=（V1,E1） 和 G2=（V2,E2）為兩個圖，如果 V1V2,E1E2 則稱（）。A. G1 是G2的子圖B. G2 是G1的子圖 C. G1 是G2的連通分量 D. G2 是G1的連通分量14、已知一個有向圖的鄰接矩陣表示，要刪除所有從第i個結(jié)

4、點發(fā)出的邊，應(yīng)（）。A.將鄰接矩陣的第i行刪除B.將鄰接矩B$的第i行元素全部置為0C.將鄰接矩陣的第i列刪除D.將鄰接矩陣的第i列元素全部置為015、任一個有向圖的拓撲序列（）。A.不存在B.有一個 C. 一定有多個D.有一個或多個16、在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。A. 1/2B. 1C. 2D. 417、下列關(guān)于圖遍歷的說法不正確的是（）。A.連通圖的深度優(yōu)先搜索是一個遞歸過程B.圖的廣度優(yōu)先搜索中鄰接點的尋找具有“先進先出”的特征C.非連通圖不能用深度優(yōu)先搜索法D.圖的遍歷要求每一頂點僅被訪問一次18、帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入度為A

5、中：（）。A.第i行非的元素之和B.第i列非的元素之和C.第i行非且非0的元素個數(shù)D.第i列非且非0的元素個數(shù)19、采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）。A.先序遍歷B.中序遍歷20、一個具有n個頂點的有向圖最多有（A. n x （n-1）/2B. n x （n-1）21、已知一個有向圖的鄰接表存儲結(jié)構(gòu)如圖所示，C.后序遍歷D.按層次遍歷條邊。C. n x （n+1）/2D. n2根據(jù)深度優(yōu)先遍歷算法,從頂點v1出發(fā),A. v1,v2,v3,v5,v4C. v1,v3,v4,v5,v222、關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（A.從源點到匯點的最長路徑B. v1,v2,v3,v4,v5

6、D. v1,v4,v3,v5,v2)所得到的頂點序列是（）。B.從源點到匯點的最短路徑D.最短的回路C.最長的回路23、以下說法正確的是（）。A.連通分量是無向圖中的極小連通子圖B.強連通分量是有向圖中的極大強連通子圖C.在一個有向圖的拓撲序列中若頂點a在頂點b之前，則圖中必有一條弧 D.對有向圖G,如果以任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個 頂點，則該圖一定是完全圖24、假設(shè)有向圖含n個頂點及e條弧，則表示該圖的鄰接表中包含的弧結(jié)點個數(shù)為（）。A. nB. eC. 2eD. n*evexsi);visitedi=TRUE;for(j=0;jvexnum;j+)if(g-ar

7、csij=1)&(!visitedj) function(j,g);答案：實現(xiàn)圖的深度優(yōu)先遍歷算法五、綜合題1、已知圖G的鄰接矩陣如下所示：(1)求從頂點1出發(fā)的廣度優(yōu)先搜索序列；(2)根據(jù)prim 算法，求圖G從頂點1出發(fā)的最小生成樹，要求表示出其每一步生成過程。 (用圖或者表的方式均可)。 TOC o 1-5 h z g6I6co515oc5oo5oo36ogo4588GO330564oo28g626qo答案：（1）廣度優(yōu)先遍歷序列：1； 2, 3, 4; 5; 6（2）最小生成樹（prim算法）2、設(shè)一個無向圖的鄰接矩陣如下圖所示：（1 ）畫出該圖； （2）畫出從頂點0出發(fā)的深度優(yōu)先生成

8、樹； TOC o 1-5 h z 0III（0I0I000110 110 10101100I1010001I0答案： （1）圖形態(tài)（2）深度優(yōu)先搜索樹3、寫出下圖中全部可能的拓撲排序序列。答案：1, 5, 2, 3, 6, 41 , 5, 6, 2, 3, 45, 1, 2, 3, 6, 45, 1, 6, 2, 3,5, 6, 1, 2, 3, 44、AOE網(wǎng)G如下所不（2）關(guān)鍵路徑:求關(guān)鍵路徑。（要求標明每個頂點的最早發(fā)生時間和最遲發(fā)生時間,并畫出關(guān)鍵路徑）答案：（1）最早發(fā)生時間和最遲發(fā)生時間:5、已知有向圖G如下所示，根據(jù)迪杰斯特拉算法求頂點 v0到其他頂點的最短距離。（給出 求解過程

9、）答案:終點從v0到各終點的d值和最短路徑的求解過程i=1i=2i=3i=4v112 (v0,v1)12 (v0,v1)7 (v0,v4,v1)v24 (v0,v2)v39 (v0,v3)8 (v0,v2,v3)7 (v0,v4,v3)7 (v0,v4,v3)v45 (v0,v4)5 (v0,v4)vjv2v4v1v3sv0,v2v0,v4v0,v4,v1v0,v4,v36、已知圖G如下所示，根據(jù) Prim算法，構(gòu)造最小生成樹。（要求給出生成過程）答案：prim算法求最小生成樹如下:7、已知有向圖如下所示，請寫出該圖所有的拓撲序列。答案：拓撲排序如下:v1, v2, v4, v6, v5, v

10、3, v7, v8 v1, v2, v6, v4, v5, v3, v7, v8 v1, v6, v2, v4, v5, v3, v7, v8 v1, v2, v4, v6, v5, v7, v3, v8 v1, v2, v6, v4, v5, v7, v3, v8 v1, v6, v2, v4, v5, v7, v3, v88、如下圖所示的 AOE網(wǎng)，求：(1)求事件的最早開始時間 ve和最遲開始時間vl ;事件123456789VeVl(2)求出關(guān)鍵路徑;L%如下所示的有向圖，回答下面問題:(1)該圖是強連通的嗎？若不是，給出強連通分量。(2)請給出圖的鄰接矩陣和鄰接表表示。答案：(1)是強連通圖(2)鄰接矩陣和鄰接表為:9、已知圖G的鄰接矩陣A=8 1 12 61 oc 912 8 oc oo693810 K 2 4試畫出它所表示的圖G,并根據(jù)Prim算法求出圖的的最小生成樹(給出生成過程) 答案：(1)圖形態(tài)：(2)prim算法求最小生成樹:10、如下圖所示的 AOV網(wǎng)，寫出其中三種拓撲排序序歹U。11、已知圖G如下，根據(jù)克魯斯卡爾算法求圖G的一棵最小生成樹。（要求給出構(gòu)造過程）答案：kruskal算法的最小生成樹12、已知圖G如下所