|
|
拿答案：2937748743 来源 www.ybaotk.com第六章形成性考核六（5%）答案1、 任何无向网络拓扑排序的结果是唯一的。
对
错2、 边很多的图称为
回答
。
3、 边数很多的稠密图，适宜用邻接矩阵表示。
对
错4、 存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。
对
错5、 边很少的图称为
6、 设x，y是图G中的两顶点，则（x，y）与（y，x）被认为
回答
，
7、 具有n个顶点的无向图最多有（ ）条边。（难度系数：易 ）
n(n-1)/2
n(n+1)
n2
n/28、 对于有向图，顶点V的度分为入度和
回答
。
9、 n个顶点的强连通图的形状是（ ）。（难度系数：易 ）
树状
有回路
无回路
环状10、 邻接表是图的一种（ ）。（难度系数：易 ）
索引存储结构
散列存储结构
链式存储结构
顺序存储结构11、 设G为具有N个顶点的无向连通图，则G至少有
回答
条边。
12、 在无向图G的邻接矩阵A中，若A[i][j]等于1，A[j] [i]等于
回答
。
13、 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。
对
错14、 不存在拓扑序列的
回答
是图中存在回路。
15、 n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。
对
错16、 对于一个图G，若边集E（G）为有向边的集合，则该图为
回答
。
17、 深度优先遍历类似于二叉树的（ ）。（难度系数：易 ）
先序遍历
中序遍历
后序遍历
层次遍历18、 若图G中任意两个顶点都连通，则称G为
19、 在具有6个结点的无向简单图中，当边数最少为
回答
条时，才能确保该图一定的连通图。
20、 有向图是一种非线性结构。
对
错21、 无向图的邻接矩阵是一个（ ）。（难度系数：易 ）
对角矩阵
零矩阵
上三角矩阵
对称矩阵22、 设x，y是图G中的两顶点，〈x，y〉与〈y，x〉是
回答
的两条弧。
23、 具有n个顶点的有向图最多有（ ）条边。（难度系数：易 ）
n(n+1)
n(n-1)
n
n的平方24、 图的最小生成树的形状可能不唯一。
对
错25、 在有向图中每个顶点的度等于各顶点的入度与出度之和。
对
错26、 若连通网络上各边的权值均不相同，则该图的最小生成树有
回答
棵。
27、 无向图G中极大连通子图称为G的
回答
。
28、 广度优先遍历类似于二叉树的（ ）。（难度系数：易 ）
中序遍历
先序遍历
后序遍历
层次遍历29、 图的深度优先遍历算法类似于二叉树的（ ）遍历。（难度系数：易 ）
先序
层次
后序
中序30、 有向图顶点V的度等于其
回答
和出度之和。
31、 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。（难度系数：易 ）
一棵树
完全图
有回路
连通图32、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。（难度系数：易 ）
1
1/2
4
233、 用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。（难度系数：易 ）
图
队列
栈
树34、 邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。
对
错35、 具有N（N-1）/2条边的无向图成为
回答
。
36、 路径长度是指一条路径上经过的边的
37、 n个顶点的连通图用邻接矩阵表示时，该矩阵至少有
回答
范围非0元素。
38、 在有向图的邻接矩阵上，由第i行可得到第i个结点的出度，而由第j列可得到第
回答
个结点的入度。
39、 在一个无向图中，若存在一条边,则称Vi和Vj为该边的两个端点，并称他们互为
回答
。
40、 n个顶点的强连通图至少有（ ）条边。（难度系数：易 ）
n-1
n
n×(n-1)
n+141、 G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。（难度系数：易 ）
8
6
9
742、 具有N（N-1）/2条边的有向图成为
回答
。
43、 在无向图中，如果从顶点v到顶点v′有路径，则称v和v′是
回答
。
44、 在一个无向图中，所有顶点的度数之和等于所有边数的2倍。
对
错45、 一个具有n个顶点的无向完全图包含（ ）条边。（难度系数：易 ）
n（n-1）/2
n（n+1）/2
n（n-1）
n（n+1）46、 在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。（难度系数：易 ）
1/2
1
4
247、 用相邻矩阵表示图所用的存储空间大小与图的边数成正比。
对
错48、 入度是以该顶点为终点的入边
回答
。
49、 在无权图G的邻接矩阵A中，若（vi，vj）或〈vi，vj〉属于图G的边集，则对应元素A[i][j]等于
回答
。
50、 通常可以把某城市中各公交站点间的线路图抽象成（）状结构（难度系数：易 ）
表
栈
图
树51、 在一个图中每条边可以表上具有某种含义的数值，该数值称为
回答
。
52、 出度是以该顶点为起点的
回答
数目。
53、 对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。
对
错54、 任何有向网络（AOV-网络）拓扑排序的结果是唯一的。
对
错55、 下列有关图遍历的说法正确的是（ ）。（难度系数：易 ）
图的广度优先搜索中邻接点的寻找具有"先进先出”的特征
图的遍历要求每一顶点仅被访问一次
连通图的深度优先搜索是一个递归过程
非连通图不能用深度优先搜索法56、 缩短关键路径上活动的工期一定能够缩短整个工程的工期。
对
错57、 若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。（难度系数：易 ）
强连通
非连通
连通
有向58、 下面（）方法不可以判断出一个有向图是否有环。（难度系数：易 ）
求关键路径
求最短路径
深度优先遍历
拓扑排序59、 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。
对
错60、 n个顶点的连通图至少有
回答
条边。
61、 一棵有N个顶点的生成树有且仅有
回答
条边。
62、 对于一个图G，若边集E（G）为无向边的集合，则该图为
回答
。
63、 有向图G中极大强连通子图称为G的
回答
。
64、 对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。（难度系数：易 ）
（n-1）2
n-1
n2
n65、 已知一个图的邻接矩阵表示，删除所有从i个结点出发的边的方法是将矩阵的第i行全部置为
回答
。
66、 图的广度优先搜索算法通常采用递归算法求解。
对
错67、 用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。（难度系数：易 ）
栈
图
队列
树68、 在有向图G中，若任意两个顶点Vi和Vj都连通，从VI到Vj和从Vj到Vi都存在路径，则称该图为
回答
。
69、 为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为（）（难度系数：易 ）
表
栈
图
树70、 在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。（难度系数：易 ）
2
1/2
1
471、 在一个有向图中，所有顶点入度之和等于所有顶点出度之和的
回答
倍。
|
上一篇：广东开放大学形考任务数据结构（本，2021春）第八章形成性考核八（10%）答案下一篇：广东开放大学形考任务数据结构（本，2021秋）第一章形成性考核一（10%）答案
|
[复制链接]
发表于 2022-1-13 17:11:51
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
发表于 2022-3-13 14:45:16
QQ登录
