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