没有合适的资源?快使用搜索试试~ 我知道了~
数据库系统l试题库及答案 第7章图.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 198 浏览量
2023-04-01
19:19:58
上传
评论
收藏 820KB PDF 举报
温馨提示
试读
11页
。
资源推荐
资源详情
资源评论
第七章 图
7.1 图的相关知识
一、
填空题
1. 完全无向图有 条边。
2. 有向完全图具有 条弧。
3. 图有 、 等存储结构。
, , , ,
4. 对于无向图 G=(V,{E}),如果边(v,v )∈E,则称顶点 v 和 v 互为 ,即 v 和 v 相邻。边(v,v )
, , ,
依附于顶点 v 和 v ,或者说(v,v )和顶点 v 和 v 。和顶点 v 相关联的边的数目称为顶点 v 的 。
顶点 v 为头的弧的数目称为v 的 ;以 v为尾的弧的数目称为v 的 。顶点v 的度为 。
5. 有向图 G 用邻接表矩阵存储,其第 i 行的所有元素之和等于顶点 i 的 。
6. n 个顶点 e 条边的图,若采用邻接矩阵存储,则空间复杂度为 。
7. n 个顶点 e 条边的图,若采用邻接表存储,则空间复杂度为 。
8. 设有一稀疏图 G,则 G 采用 存储较省空间。
9. 设有一稠密图 G,则 G 采用 存储较省空间。
10. 图的逆邻接表存储结构只适用于 图。
二、 选择题
1. ( )在一个图中,所有顶点的度数之和等于图的边数的 倍。
A.1/2 B. 1 C. 2 D. 4
2. ( )在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的 倍。
A.1/2 B. 1 C. 2 D. 4
3. ( )有 8 个结点的无向图最多有 条边。
A.14 B. 28 C. 56 D. 112
4. ( )有 8 个结点的无向连通图最少有 条边。
A.5 B. 6 C. 7 D. 8
5. ( )对于一个具有 n 个顶点的无向图,若采用邻接矩阵表示,则该矩阵大小是 。
2 2
A.n B. (n-1) C. n-1 D. n
6. ( )无向图的邻接矩阵是一个 。
A.对称矩阵 B. 零矩阵 C. 上三角矩阵 D. 对角矩阵
7. ( )在有向图的邻接表表示中,顶点 v 在边表节点中出现的次数是 。
A.顶点 v 的入度 B. 顶点 v 的出度 C. 顶点 v 的度 D. 依附于顶点 v 的边条数
8. ( )以下关于图的存储结构的叙述中正确的是 。
A.一个图的邻接矩阵表示唯一,邻接表表示唯一。
B. 一个图的邻接矩阵表示唯一,邻接表表示不唯一 。
C. 一个图的邻接矩阵表示不唯一,邻接表表示唯一 。
D. 一个图的邻接矩阵表示不唯一,邻接表表示不唯一。
三、 简答题
1.已知如图所示的有向图,请给出该图的:
(1)
(2)
(3)
(4)
每个顶点的入/出度;
邻接矩阵;
邻接表;
逆邻接表。
四、 算法设计
1.试在邻接矩阵存储结构上实现图的基本操作:DeleteArc(G,v,w) ,即删除一条边的操作。(如果要删
除所有从第 i 个顶点出发的边呢? 提示: 将邻接矩阵的第 i 行全部置 0 )
7.2 图的遍历与生成树
一、 填空题
1. n 个顶点 e 条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为 ;若采用邻接表存
储时,该算法的时间复杂度为 。
2. n 个顶点 e 条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为 ;若采用邻接表存
储,该算法的时间复杂度为 。
3. 一个连通图的生成树是一个极小连通子图,它含有图中全部n 个顶点,只有足以构成一棵树的 条
边。
4. 如果 n 个顶点的图是一个环,则它有 棵生成树。
5. 用普里姆(Prim)算法求具有 n 个顶点 e 条边的图的最小生成树的时间复杂度为 ;用克鲁斯卡
尔(Kruskal)算法的时间复杂度是 。
6. 求解带权连通图最小生成树的 Prim 算法适合于________图的情形,而 Kruskal 算法适合于________
图的情形。
二、 选择题
1. ( )用邻接表表示图进行广度优先遍历时,通常是采用 来实现算法的。
A.栈 B. 队列 C. 树 D. 图
2. ( )用邻接表表示图进行深度优先遍历时,通常是采用 来实现算法的。
A.栈 B. 队列 C. 树 D. 图
3. ( )已知图的邻接矩阵,根据算法思想,则从顶点0 出发按深度优先遍历的结点序列是 。
0
1
1
1
1
0
1
1 1 1 1 0 1
0 0 1 0 0 1
0 0 0 1 0 0
1 0 0 1 1 0
0 1 1 0 1 0
0 0 1 1 0 1
1 0 0 0 1 0
A. 0 2 4 3 1 5 6
B. 0 1 3 6 5 4 2
C. 0 1 3 4 2 5 6
D. 0 3 6 1 5 4 2
4. ( )已知图的邻接矩阵同上题 3,根据算法,则从顶点 0 出发按广度优先遍历的结点序列是 。
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 2 3 4 6 5
5. ( )已知图的邻接表如下所示,根据算法,则从顶点0 出发按深度优先遍历的结点序列是 。
A.0 1 3 2 B. 0 2 3 1
C. 0 3 2 1 D. 0 1 2 3
6. ( )已知图的邻接表如下所示,根据算法,则从顶点0 出发按广度优先遍历的结点序列是 。
A.0 3 2 1 B. 0 1 2 3
C. 0 1 3 2 D. 0 3 1 2
7. ( )深度优先遍历类似于二叉树的 。
A.先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历
8. ( )广度优先遍历类似于二叉树的 。
A.先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历
9. ( )任何一个无向连通图的最小生成树 。
A.只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在
三、 简答题
1.已知二维数组表示的图的邻接矩阵如下图所示。试
分别画出自顶点 1 出发进行遍历所得的深度优先生成
树和广度优先生成树。
剩余10页未读,继续阅读
资源评论
若♡
- 粉丝: 6203
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功