
第6章 图习题参考答案.doc
9页习题六参考答案一、选择题1. 在一个有 个顶点的有向图中,若所有顶点的出度之和为 ,则所有顶点的入度之和为(A) n sA. B. C. D. s s-1 s+1 n2. 一个有向图有 个顶点,则每个顶点的度可能的最大值是(B) nA. B. C. D.𝑛‒1 2(𝑛‒1) 𝑛 2𝑛3. 具有 6 个顶点的无向图至少应有( A )条边才能确保是一个连通图A.5 B.6 C.7 D.84. 一个有 n 个顶点的无向图最多有( C )条边A. B. C. D.n n(n-1) n(n-1)/2 2n5. 对某个无向图的邻接矩阵来说,下列叙述正确的是(A) A.第 行上的非零元素个数和第 列上的非零元素个数一定相等i iB.矩阵中的非零元素个数等于图中的边数C.第 行与第 列上的非零元素的总数等于顶点 的度数i i 𝑣𝑖D.矩阵中非全零行的行数等于图中的顶点数6. 已知一个有向图的邻接矩阵,要删除所有以第 个顶点为孤尾的边,应该(B) iA.将邻接矩阵的第 行删除 B.将邻接矩阵的第 行元素全部置为 0i iC.将邻接矩阵的第 列删除 D.将邻接矩阵的第 列元素全部置为 0i i7. 下 面 关 于 图 的 存 储 的 叙 述 中 , 哪 一 个 是 正 确 的 ? ……( A)A.用邻接矩阵存储图,占用的存储空间只与图中顶点数有关,而与边数无关B.用邻接矩阵存储图,占用的存储空间只与图中边数有关,而与顶点数无关C.用邻接表存储图,占用的存储空间只与图中顶点数有关,而与边数无关D.用邻接表存储图,占用的存储空间只与图中边数有关,而与顶点数无关8. 对图的深度优先遍历,类似于对树的哪种遍历?……(A)A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历9. 任何一个无向连通图的最小生成树(B) 。
A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在10. 下面是三个关于有向图运算的叙述:(1)求两个指向结点间的最短路径,其结果必定是唯一的(2)求有向图结点的拓扑序列,其结果必定是唯一的(3)求 AOE 网的关键路径,其结果必定是唯一的其中哪个(些)是正确的?……( D )A.只有(1) B.(1)和(2) C.都正确 D.都不正确二、填空题1. 若 用 表 示 图 中 顶 点 数 , 则 有 条 边 的 无 向 图 称 为 完 全 图 n n(n-1)/22. 若一个无向图有 100 条边,则其顶点总数最少为 15 个3. 个顶点的连通无向图至少有 条边,至多有 条边n n-1 n(n-1)/24. 若 有 向 图 的 邻 接 矩 阵 为 :G𝑣0𝑣1𝑣2𝑣3𝑣4𝑣0𝑣1𝑣2𝑣3𝑣4 (0 11 00 10 1 01 1 10 1 10 00 0 0 0 11 0 0)则 顶 点 的 入 度 是 3 𝑣45. 对于一个有向图,若一个顶点的度为 ,出度为 ,则对应逆邻接表中该顶点单链表中的边k1 k2结点数为 。
k1‒k26. 图的遍历算法 BFS 中用到辅助队列,每个顶点最多进队 1 次7. 在求最小生成树的两种算法中, 克鲁斯卡尔 算法适合于稀疏图8. 数据结构中的迪杰斯特拉算法是用来求 某个源点到其余各顶点的最短路径 9. 除了使用拓扑排序的方法,还有 深度优先搜索 方法可以判断出一个有向图是否有回路10. 在用邻接表表示图时,拓扑排序算法的时间复杂度为 O(𝑛+𝑒)三、应用题1. 已知如图 6.28 所示的有向图,请给出该图的123456图 6.28 有向图(1) 每个顶点的出/ 入度;(2) 邻接矩阵;(3) 邻接表;(4) 逆邻接表答:(1) 每个顶点的出/ 入度是:出度 入度1 0 32 2 23 2 14 3 15 1 26 3 2(2) 邻接矩阵: 1 2 3 4 5 6123456 (0 01 0 0 00 1 0 00 00 10 0 0 01 0 0 11 11 01 1 0 00 0 0 01 0)(3) 邻接表:401231234Λ50 3 Λ12 45 65 Λ5 Λ0 Λ0 1 4 Λ(4) 逆邻接表:40123123452 5 Λ3 Λ1 Λ5 632 3 Λ1 4 5 Λ5 Λ2. 试对如图 6.29 所示的非连通图,画出其广度优先生成森林。
图 Error! No text of specified style in document..29 非连通图GI KHEDACFBLJM答:GI KHEDAC FB LJM3. 已知图的邻接矩阵如图 6.30 所示试分别画出自顶点 A 出发进行遍历所得的深度优先生成树和广度优先生成树 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐺 𝐻 𝐼 𝐽𝐴𝐵𝐶𝐷𝐸𝐹𝐺𝐻𝐼𝐽 (0 0 00 0 10 0 00 0 00 0 01 0 01 0 1 01 0 0 00 1 0 00 0 00 0 01 1 0 0 1 00 0 10 0 0 0 0 1 00 0 0 10 0 0 00 0 11 0 001 00 000 0 01 0 000 10 010 0 0 10 0 1 010 00 00 10)图 Error! No text of specified style in document..30 邻接矩阵答:IHEDABFGJCIHDABFGJC E4. 请对如图 6.31 所示的无向网:(1) 写出它的邻接矩阵,并按克鲁斯卡尔算法求其最小生成树;(2) 写出它的邻接表,并按普里姆算法求其最小生成树。
534655图 Error! No text of specified style in document..31 无向网5437ABEFDC9GH5 26答:(1) 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐺 𝐻𝐴𝐵𝐶𝐷𝐸𝐹𝐺𝐻 (0 4 34 0 53 5 0∞55∞5 5 0∞∞9 ∞∞∞∞∞∞∞∞57 6 5 4∞9 ∞7∞∞∞6∞∞∞∞∞5 540 33 0 ∞2 ∞∞∞2 0 6∞∞ 6 0)克鲁斯卡尔算法求其最小生成树ABEFDC GH23ABEFDC GH23ABEFDC GH23343ABEFDC GH23443ABEFDC GH234543ABEFDC GH234543ABEFDC9GH5 2(2)ABCD0123EFGH45671 4 Λ320 4 2 5 3 5 Λ941 5 2 5 4 7 5 6 6 5 Λ470 3 1 5 3 5 Λ571 9 3 7 Λ353 6 4 3 Λ263 5 5 2 Λ672 5 3 4 Λ66普里姆算法求其最小生成树,从 A 开始3ABEFDC GH43ABEFDC GH543ABEFDC GH4543ABEFDC GH4543ABEFDC GH54543ABEFDC GH5 234543ABEFDC GH5 25. 试列出图 6.32 中全部可能的拓扑有序序列。
abce图 6.32 有向图fd答:abcdef、abcef、abecdf 、 bacdef、bacedf、baecdf、beacdf四、算法设计题1. 编写算法,从键盘读入有向图的顶点和弧,创建有向图的邻接表存储结构参考答案:public static ALGraph createDG() {Scanner sc = new Scanner(System.in);System.out.println("请分别输入有向图的顶点数和边数 :");int vexNum = sc.nextInt();int arcNum = sc.nextInt();VNode[] vexs = new VNode[vexNum];System.out.println("请分别输入有向图的各个顶点 :");for (int v = 0; v = 0; w = G.nextAdjVex(u,w)) {if (!visited[w]) {// w 为 u 的尚未访问的邻接顶点visited[w] = true;P.offer(G.getVex(w));Q.offer(w);}}}System.out.println("图的第" + ++i + "个连通分量为: ");while (!P.isEmpty())System.out.print(P.poll().toString() + " ");System.out.println();}}}3. 编写算法判别以邻接表方式存储的无向图中是否存在由顶点 u 到顶点 v 的路径(u≠v) 。
可以采用深度优先搜索遍历策略当顶点 u 和顶点 v 在无向图的同一连通分量中时,从顶点u 到顶点 v 一定有路径,可从顶点 u(v)进行深度优先搜索,一定可以遍历至顶点 v(u) 否则,遍历不能成功,不存在由顶点 u 到顶点 v 的路径参考答案:private boolean[] visited;// 访问标志数组private boolean find = false;// 标示是否已找到了指定长度的路径public void findPath(IGraph G, int u, int v) throws Exception {visited = new boolean[G.getVexNum()];for (int w = 0; w = 0; w = G.nextAdjVex(u, w))if (!visited[w])find_DFS(G, w, v);// 对v的尚未访问的邻接顶点w递归调用find_DFS}}。












