數(shù)據(jù)結(jié)構(gòu)第07章,圖習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)第07章,圖習(xí)題 第七章 圖 一、選擇題 1、對于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為（ ）。 a. n b. n 2 c. n-1 d. (n-1) 2 2、如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是（ ）。 a. 完全圖 b. 連通圖 c. 有回路 d. 一棵樹 3、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。 a. 從源點(diǎn)到匯點(diǎn)的最長路徑 b. 從源點(diǎn)到匯點(diǎn)的最短路徑 c. 最長的回路 d. 最短的回路 4、下面（ ）可以判斷出一個(gè)有向圖中是否有環(huán)（回路）。 a. 廣度優(yōu)先遍歷 b. 拓?fù)渑判?c. 求最短路徑 d. 求關(guān)鍵路徑 5、帶權(quán)有

2、向圖g用鄰接矩陣a存儲(chǔ)，則頂點(diǎn)i的入度等于a中（ ）。 a. 第i行非無窮的元素之和 b. 第i列非無窮的元素個(gè)數(shù)之和 c. 第i行非無窮且非0的元素個(gè)數(shù) d. 第i行與第i列非無窮且非0的元素之和 6、采用鄰接表存儲(chǔ)的圖，其深度優(yōu)先遍歷類似于二叉樹的（ ）。 a. 中序遍歷 b. 先序遍歷 c. 后序遍歷 d. 按層次遍歷 7、無向圖的鄰接矩陣是一個(gè)（ ）。 a. 對稱矩陣 b. 零矩陣 c. 上三角矩陣 d. 對角矩陣 8、當(dāng)利用大小為n的數(shù)組存儲(chǔ)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長度是（ ）。 a. n-2 b. n-1 c. n d. n+1 9、鄰接表是圖的一種（ ）。 a. 順序存儲(chǔ)結(jié)構(gòu) b

3、. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) c. 索引存儲(chǔ)結(jié)構(gòu) d. 散列存儲(chǔ)結(jié)構(gòu) 10、下面有向圖所示的拓?fù)渑判虻慕Y(jié)果序列是（ ）。 a. 125634 b. 516234 c. 123456 d. 521643 1235 6 4 11、在無向圖中定義頂點(diǎn) vi 與 vj 之間的路徑為從 vi 到 vj 的一個(gè)（ ）。 a. 頂點(diǎn)序列 b. 邊序列 c. 權(quán)值總和 d. 邊的條數(shù) 12、在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（ ）鄰接點(diǎn)。 a. 入邊 b. 出邊 c. 入邊和出邊 d. 不是出邊也不是入邊 13、設(shè)g1=(v1,e1)和g2=(v2,e2)為兩個(gè)圖，如果v1v2,e1e2則稱（ ）。 a

4、. g1是g2的子圖 b. g2是g1的子圖 c. g1是g2的連通分量 d. g2是g1的連通分量 14、已知一個(gè)有向圖的鄰接矩陣表示，要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)（ ）。 a. 將鄰接矩陣的第i行刪除 b. 將 鄰 接 矩 陣 的 第 i 行 元 素 全 部 置 為 0 c. 將鄰接矩陣的第i列刪除 d. 將鄰接矩陣的第i列元素全部置為0 15、任一個(gè)有向圖的拓?fù)湫蛄校?）。 a.不存在 b. 有一個(gè) c. 一定有多個(gè) d. 有一個(gè)或多個(gè) 16、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ ）倍。 a. 1/2 b. 1 c. 2 d. 4 17、下列關(guān)于圖遍歷的說法

5、不正確的是（ ）。 a. 連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程 b. 圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有先進(jìn)先出的特征 c. 非連通圖不能用深度優(yōu)先搜索法 d. 圖的遍歷要求每一頂點(diǎn)僅被訪問一次 18、帶權(quán)有向圖g用鄰接矩陣a存儲(chǔ)，則頂點(diǎn)i的入度為a中：（ ）。 a. 第i行非的元素之和 b. 第i列非的元素之和 c. 第i行非且非0的元素個(gè)數(shù) d. 第i列非且非0的元素個(gè)數(shù) 19、采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（ ）。 a. 先序遍歷 b. 中序遍歷 c. 后序遍歷 d. 按層次遍歷 20、一個(gè)具有n個(gè)頂點(diǎn)的有向圖最多有（ ）條邊。 a. n(n-1)/2 b. n(n-1

6、) c. n(n+1)/2 d. n 2 21、已知一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示，根據(jù)深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是（ ）。 123453 2 44 52 4 a. v1,v2,v3,v5,v4 b. v1,v2,v3,v4,v5 c. v1,v3,v4,v5,v2 d. v1,v4,v3,v5,v2 22、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。 a. 從源點(diǎn)到匯點(diǎn)的最長路徑 b. 從源點(diǎn)到匯點(diǎn)的最短路徑 c. 最長的回路 d. 最短的回路 23、以下說法正確的是（ ）。 a. 連通分量是無向圖中的極小連通子圖 b. 強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖 c. 在一個(gè)有向

7、圖的拓?fù)湫蛄兄腥繇旤c(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧a,b d. 對有向圖g，如果以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個(gè)頂點(diǎn)，則該圖一定是完全圖 24、假設(shè)有向圖含n個(gè)頂點(diǎn)及e條弧，則表示該圖的鄰接表中包含的弧結(jié)點(diǎn)個(gè)數(shù)為（ ）。 a. n b. e c. 2e d. n*e 25、設(shè)圖的鄰接矩陣為0 1 01 0 01 1 0，則該圖為（ ）。 a. 有向圖 b. 無向圖 c. 強(qiáng)連通圖 d. 完全圖 26、為便于判別有向圖中是否存在回路，可借助于（ ）。 a. 廣度優(yōu)先搜索算法 b. 最小生成樹算法 c. 最短路徑算法 d. 拓?fù)渑判蛩惴?27、任何一個(gè)無向連通圖的最小生成

8、樹（ ）。 a. 只有一棵 b. 有一棵或多棵 c. 一定有多棵 d. 可能不存在 28、已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示，根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是（ ）。 a. v1,v2,v3,v4,v5 b. v1,v3,v2,v4,v5 c. v1,v2,v3,v5,v4 d. v1,v4,v3,v5,v2 29、對于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1、出度為k2，則對應(yīng)鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為（ ）。 a. k1 b. k2 c. k1+k2 d. k1-k2 30、無向圖中一個(gè)頂點(diǎn)的度是指圖中（ ）。 a. 通過該頂點(diǎn)的簡單路徑數(shù) b. 與該頂點(diǎn)

9、相鄰接的頂點(diǎn)數(shù) c. 與該頂點(diǎn)連通的頂點(diǎn)數(shù) d. 通過該頂點(diǎn)的回路數(shù) 二、填空題 1、n個(gè)頂點(diǎn)的連通圖至少有_邊。 2、一個(gè)連通圖的生成樹是一個(gè)_，它包含圖中所有頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。 3、一個(gè)圖的_表示法是惟一的。 4、遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，其中_是一個(gè)遞歸過程。 5、在無向圖g的鄰接矩陣a中，若aij等于1，則aji等于_。 6、判定一個(gè)有向圖是否存在回路，可以利用_。 7、已知一個(gè)圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是_。 8、n個(gè)頂點(diǎn)的無向圖最多有_邊。 9、已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是_。 10、若以

10、鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個(gè)數(shù)即為頂點(diǎn)vi的_。 三、判斷題 1、圖的連通分量是無向圖的極小連通子圖。 2、一個(gè)圖的廣度優(yōu)先搜索樹是惟一的。 3、圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。 4、鄰接表只能用于存儲(chǔ)有向圖，而鄰接矩陣則可存儲(chǔ)有向圖和無向圖。 5、存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。 6、aov網(wǎng)是一個(gè)帶權(quán)的有向圖。 7、從源點(diǎn)到終點(diǎn)的最短路徑是唯一的。 8、鄰接表只能用于存儲(chǔ)有向圖，而鄰接矩陣則可存儲(chǔ)有向圖和無向圖。 9、圖的生成樹是惟一的。 10、一個(gè)具有8個(gè)頂點(diǎn)的有向圖中，所有頂點(diǎn)的入度之和與所有頂點(diǎn)的出度之和的差等于0。 四、綜合題 1、寫出下圖中全部可能的拓?fù)渑判蛐蛄小?1 2 3 45 6 2、aoe網(wǎng)g如下所示，求關(guān)鍵路徑。（要求標(biāo)明每個(gè)頂點(diǎn)的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間，并畫出關(guān)鍵路徑） v0v1v2v3v4v53 32 23 34 42 22 23 32 2 3、如下圖所示的 aoe 網(wǎng)，求： （1）求事件的最早開始時(shí)間 ve 和最遲開始時(shí)間 vl； 事件 1 2 3 4 5 6 7 8 9 ve vl （2）求出關(guān)鍵路徑； v 1v 2 v 7v 5v 3v 4 v 6v 8v 9a 1a 2a 3645a 5a 4a 7