(好資料)第7章自測(cè)空題new--數(shù)據(jù)結(jié)構(gòu)課件(吳偉民-嚴(yán)蔚敏編著)

第7章 圖 自測(cè)卷 姓名 班級(jí) 題號(hào)一二三四五總分題分1620241030100得分一、單選題（每題1分，共16分） （ ）1. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。 A1/2 B. 1 C. 2 D. 4 （ ）2. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。 A1/2 B. 1 C. 2 D. 4 （ ）3. 有8個(gè)結(jié)點(diǎn)的無向圖最多有 條邊。 A14 B. 28 C. 56 D. 112 （ ）4. 有8個(gè)結(jié)點(diǎn)的無向連通圖最少有 條邊。 A5 B. 6 C. 7 D. 8 （ ）5. 有8個(gè)結(jié)點(diǎn)的有向完全圖有 條邊。 A14 B. 28 C. 56 D. 112 （ ）6. 用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用 來實(shí)現(xiàn)算法的。A棧 B. 隊(duì)列 C. 樹 D. 圖 （ ）7. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用 來實(shí)現(xiàn)算法的。A棧 B. 隊(duì)列 C. 樹 D. 圖 A0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 4 2 3 1 6 5D. 0 3 6 1 5 4 2（ ）8. 已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（ ）9. 已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6（ ）10. 已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6（ ）11. 已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6（ ）12. 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3（ ）13. 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2（ ）14. 深度優(yōu)先遍歷類似于二叉樹的A先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷（ ）15. 廣度優(yōu)先遍歷類似于二叉樹的A先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷（ ）16. 任何一個(gè)無向連通圖的最小生成樹A只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在二、填空題（每空1分，共20分）1. 圖有 、 等存儲(chǔ)結(jié)構(gòu)，遍歷圖有 、 等方法。2. 有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的 。3. 如果n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有 棵生成樹。4. n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為 。5. n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接表存儲(chǔ)，則空間復(fù)雜度為 。6. 設(shè)有一稀疏圖G，則G采用 存儲(chǔ)較省空間。7. 設(shè)有一稠密圖G，則G采用 存儲(chǔ)較省空間。8. 圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于 圖。9. 已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)的方法是 。10. 圖的深度優(yōu)先遍歷序列 惟一的。11. n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為 ；若采用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間復(fù)雜度為 。12. n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為 ；若采用鄰接表存儲(chǔ)，該算法的時(shí)間復(fù)雜度為 。13. 圖的BFS生成樹的樹高比DFS生成樹的樹高 。14. 用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹的時(shí)間復(fù)雜度為 ；用克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度是 。15. 若要求一個(gè)稀疏圖G的最小生成樹，最好用 算法來求解。16. 若要求一個(gè)稠密圖G的最小生成樹，最好用 算法來求解。17. 用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長(zhǎng)度 的次序來得到最短路徑的。18. 拓?fù)渑判蛩惴ㄊ峭ㄟ^重復(fù)選擇具有 個(gè)前驅(qū)頂點(diǎn)的過程來完成的。三、簡(jiǎn)答題（每題6分，共24分）1. 【嚴(yán)題集7.1】已知如圖所示的有向圖，請(qǐng)給出該圖的:頂點(diǎn)123456入度出度（1） 每個(gè)頂點(diǎn)的入/出度；（2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表。 2. 【嚴(yán)題集7.7】請(qǐng)對(duì)下圖的無向帶權(quán)圖：（1） 寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；（2） 寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。 3. 【嚴(yán)題集7.5】已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。4. 【嚴(yán)題集7.11】試?yán)肈ijkstra算法求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。四、給定下列網(wǎng)G: （10分）1 試著找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu)圖；2 用兩種不同的表示法畫出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖；3 用C語言（或其他算法語言）定義其中一種表示法（存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。五、算法設(shè)計(jì)題（每題10分，共30分）1. 【嚴(yán)題集7.14】編寫算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表。解：Status Build_AdjList(ALGraph &G) /輸入有向圖的頂點(diǎn)數(shù),邊數(shù),頂點(diǎn)信息和邊的信息，以建立鄰接表 return OK; /Build_AdjList 2. 【嚴(yán)題集7.15】試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。（如果要?jiǎng)h除所有從第i個(gè)頂點(diǎn)出發(fā)的邊呢？ 提示： 將鄰接矩陣的第i行全部置0 ）解： /設(shè)本題中的圖G為有向無權(quán)圖Status DeleteArc(MGraph &G, char v, char w) /在鄰接矩陣表示的圖G上刪除邊(v,w) return OK; /Delete_Arc 3. 【嚴(yán)題集7.22】試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑