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

1、05圖【單選題】1. 設(shè)無向圖G中有五個(gè)頂點(diǎn)，各頂點(diǎn)的度分別為2、4、3、1、2，則G中邊數(shù)為（C）。、4條、5條、6條、無法確定2. 含n個(gè)頂點(diǎn)的無向完全圖有（D）條邊；含n個(gè)頂點(diǎn)的有向圖最多有（C）條弧；含n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有（C）條弧；含n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最少有（）條?。辉O(shè)無向圖中有n個(gè)頂點(diǎn)，則要接通全部頂點(diǎn)至少需（G）條邊。A、n2B、n(n+1)C、n(n-1)D、n(n-1)/2E、n+1F、nG、n-13. 對(duì)下圖從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷，則（A）是可能得到的遍歷序列。A、acfgdebB、abcdefgC、acdgbefD、abefgcd對(duì)下圖從頂點(diǎn)a出發(fā)進(jìn)行廣

2、度優(yōu)先遍歷，則（D）是不可能得到的遍歷序列。A、abcdefgB、acdbfgeC、abdcegfD、adcbgef4. 設(shè)圖G的鄰接矩陣A=，則G中共有（C）個(gè)頂點(diǎn)；若G為有向圖，則G中共有（D）條弧；若G為無向圖，則G中共有（B）條邊。A、1B、2C、3D、4E、5F、9G、以上答案都不對(duì)5. 含n個(gè)頂點(diǎn)的圖，最少有（B）個(gè)連通分量，最多有（D）個(gè)連通分量。A、0B、1C、n-1D、n6. 用鄰接表存儲(chǔ)圖所用的空間大?。ˋ）。A、與圖的頂點(diǎn)數(shù)和邊數(shù)都有關(guān)B、只與圖的邊數(shù)有關(guān)C、只與圖的頂點(diǎn)數(shù)有關(guān)D、與邊數(shù)的平方有關(guān)7. n個(gè)頂點(diǎn)的無向圖的鄰接表最多有（B）個(gè)表結(jié)點(diǎn)。A、n2 B、n(n-1

3、) C、n(n+1) D、n(n-1)/28. 無向圖G=(V,E)，其中：V=a,b,c,d,e,f，E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（D）。A、a,b,e,c,d,fB、a,c,f,e,b,dC、a,e,b,c,f,dD、a,e,d,f,c,b9. 圖的BFS生成樹的樹高比DFS生成樹的樹高（A）。A、小或相等 B、小 C、大或相等 D、大10. 下列不正確的是（C）。(1)求從指定源點(diǎn)到其余各頂點(diǎn)的迪杰斯特拉（Dijkstra）最短路徑算法中弧上權(quán)不能為負(fù)的原因是在實(shí)際應(yīng)用中無意義；(2

4、)利用Dijkstra求每一對(duì)不同頂點(diǎn)之間的最短路徑的算法時(shí)間是O(n3)；（圖用鄰接矩陣表示）(3)Floyd求每對(duì)不同頂點(diǎn)對(duì)的算法中允許弧上的權(quán)為負(fù)，但不能有權(quán)和為負(fù)的回路。A、(1),(2),(3)B、(1)C、(1),(3)D、(2),(3)11. 當(dāng)各邊上的權(quán)值（A）時(shí)，BFS算法可用來解決單源最短路徑問題。A、均相等B、均互不相等C、不一定相等12. 若一個(gè)有向圖具有拓?fù)渑判蛐蛄?，那么它的鄰接矩陣必定為（C）。A、對(duì)稱矩陣B、稀疏矩陣C、三角矩陣D、一般矩陣13. 在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（D）。A、G中有弧<Vi,Vj>

5、;B、G中有一條從Vi到Vj的路徑C、G中沒有弧<Vi,Vj>D、G中有一條從Vj到Vi的路徑14. 關(guān)鍵路徑是AOE網(wǎng)中（B）。A、從始點(diǎn)到終點(diǎn)的最短路徑B、從始點(diǎn)到終點(diǎn)的最長路徑C、人始點(diǎn)到終點(diǎn)的邊數(shù)最多的路徑D、從始點(diǎn)到終點(diǎn)的邊數(shù)最少的路徑15. 下面關(guān)于求關(guān)鍵路徑的說法不正確的是（C）。A、求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的B、一個(gè)事件的最早開始時(shí)間同以該事件為尾的弧的活動(dòng)最早開始時(shí)間相同C、一個(gè)事件的最遲開始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差D、關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上【填空題】1. 設(shè)無向連通圖G含n個(gè)頂點(diǎn)e條邊，則G的生成樹含個(gè)頂點(diǎn)條邊。2.

6、 連通分量是無向圖的子圖，生成樹是無向連通圖的子圖。3. 對(duì)稀疏圖而言，在鄰接矩陣和鄰接表這兩種存儲(chǔ)結(jié)構(gòu)中選擇更為適宜。4. 設(shè)無向圖G含n個(gè)頂點(diǎn)e條邊，則G的鄰接表表示中含個(gè)邊表結(jié)點(diǎn)。5. 設(shè)有向圖G含n個(gè)頂點(diǎn)e條弧，則G的鄰接表表示中含個(gè)邊表結(jié)點(diǎn)。【計(jì)算題】1. 設(shè)無向圖如下，寫出對(duì)該圖從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷可能得到的所有遍歷序列。解：abcdefg、abdcegf、acbdfeg、acdbfge、adbcgef、adcbgfe。2. 設(shè)有向圖如下，寫出對(duì)該圖從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可能得到的所有遍歷序列。解：abedc、acbed、acdbe。3. 設(shè)無向網(wǎng)如下，(1)寫出其鄰

7、接矩陣；(2)基于該鄰接矩陣求深度優(yōu)先生成樹和廣度優(yōu)先生成樹；(3)基于該鄰接矩陣按普里姆算法求最小生成樹；(4)寫出其鄰接表；(5)基于該鄰接表按克魯斯卡爾算法求最小生成樹。解：(1) (2)深度優(yōu)先生成樹：；廣度優(yōu)先生成樹：(3)最小生成樹：；求解過程：(4)鄰接表：(5)最小生成樹：4. 設(shè)AOV圖如下，寫出對(duì)該圖進(jìn)行拓?fù)渑判蚩赡艿玫降乃型負(fù)湫蛄?。解：abcdefg、abcdfeg、abcfdeg5. 設(shè)AOE網(wǎng)如下，試求關(guān)鍵路徑。解：關(guān)鍵路徑：v1v2v5v7關(guān)鍵路徑：v1v3v6v7。6. 設(shè)有向網(wǎng)如下，試用迪杰斯特拉算法求從頂點(diǎn)A出發(fā)到其余各頂點(diǎn)的最短路徑。解：ab：3af：5a

8、fe：7abc：11afed：147. 設(shè)有向網(wǎng)如下，試用弗洛伊德算法求圖中各對(duì)頂點(diǎn)間的最短路徑。解：【算法題】下列算法題中可能用到的類如下：public class MGraph private Object vexs; private int adj; private int vexnum; private int arcnum; public MGraph(int maxvn) int i, j; vexs=new Objectmaxvn; adj=new intmaxvnmaxvn; for(i=0;i<maxvn;i+) for(j=0;j<maxvn;j+) adjij

9、=0; vexnum=0; arcnum=0; /構(gòu)造函數(shù)/圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)類public class ALANode public int adj; public ALANode next;/圖的鄰接表存儲(chǔ)結(jié)構(gòu)中的表結(jié)點(diǎn)類public class ALVNode public Object data; /頂點(diǎn)信息 public ALANode firstarc;/圖的鄰接表存儲(chǔ)結(jié)構(gòu)中的頭結(jié)點(diǎn)類public class ALGraph private ALVNode vexs; private int vexnum; private int arcnum; public ALGraph(i

10、nt maxvn) vexs=new ALVNodemaxvn; vexnum=0; arcnum=0; /構(gòu)造函數(shù)/圖的鄰接表存儲(chǔ)結(jié)構(gòu)類1. 在ALGraph類中添加符合如下要求的構(gòu)造函數(shù)public ALGraph(Object v, ArcArray a)其中v為頂點(diǎn)向量，a為弧向量，類ArcArray的定義如下：public class ArcArray private int index1; /弧尾頂點(diǎn)下標(biāo) private int index2; /弧頭頂點(diǎn)下標(biāo)(2)public ALGraph(MGraph g)2. 在ALGraph類中添加實(shí)現(xiàn)如下功能的方法：(1)在無向圖中插入

11、一個(gè)頂點(diǎn)；(2)在無向圖中刪除一個(gè)頂點(diǎn)；(3)在無向圖中添加一條邊；(4)在無向圖中刪除一條邊。(5)判定無向圖中是否存在從頂點(diǎn)vi到頂點(diǎn)vj的路徑（ij）。(6)輸出無向圖中從頂點(diǎn)vi到頂點(diǎn)vj的所有簡單路徑。解：(5)public boolean path(int i, int j) /從頂點(diǎn)vi出發(fā)進(jìn)行深度優(yōu)先遍歷，調(diào)用完成時(shí)所有與vi有路徑相通的頂點(diǎn)都被訪問到 boolean visited =new booleanvexs.length; for(k=0;k<vexnum;k+) visitedk=false; dfs(i, visited); return visitedj;/pathvoid dfs(int i, boolean visited)/從頂點(diǎn)vi出發(fā)對(duì)圖G進(jìn)行深度優(yōu)先遍歷visitedi=true;for(p=vexsi.firstarc;p;p=p.next)if (!visitedp.adj) dfs(p.adj, visited);/dfs3. 在MGraph類中添加符合如下要求的構(gòu)造函數(shù)：(1)public class MGraph(Object v, EdgeArray e)其中v為頂點(diǎn)向量，e為邊向量，類EdgeArray的定義如下：public class EdgeArray public