【数据结构】图的习题 PTA

以你之姓@ 2023-01-22 15:51 192阅读 0赞

# 判断题 #

1、无向连通图至少有一个顶点的度为1。

> 一个无向图围成的三角形就是每个顶点度都为2

2、无向连通图所有顶点的度之和为偶数。

> 顶点的度为顶点所连接的边的个数，无向连通图中的顶点的度之和为边数 \* 2所以顶点的度之和为偶数

3、在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。

> 一个结点的出度是相连结点的入度

4、对于带权无向图 G = (V, E)，M 是 G 的最小生成树，则 M 中任意两点 V1 到 V2 的路径一定是它们之间的最短路径。

> 最小生成树的总权最小，不是其中的任意路径最小

# 单选题 #

1、具有5个顶点的有向完全图有多少条弧？

> n个顶点，无向完全图的边n(n-1)/2，有向完全图n(n-1)

2、图的深度优先遍历类似于二叉树的：

> 深度优先遍历是先序遍历，广度优先遍历是层次遍历

3、给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：![在这里插入图片描述][20210520212135174.jpg_pic_center]

> 记得，DFS访问的时候，访问的顶点是第一个未被访问的邻接点

4、若一个有向图用邻接矩阵表示，则第 i 个结点的入度就是：

<table> 
 <thead> 
  <tr> 
   <th>A. 第i行的元素个数</th> 
   <th>B. 第i行的非零元素个数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>C. 第i列的非零元素个数</td> 
   <td>D. 第i列的零元素个数</td> 
  </tr> 
 </tbody> 
</table>

> 若一个有向图用邻接矩阵表示，则第i个结点的入度就是：第i列的非零元素个数；  
> 若一个有向图用邻接矩阵表示，则第i个结点的出度就是：第i行的非零元素个数；

5、下面关于图的存储的叙述中，哪一个是正确的？

<table> 
 <thead> 
  <tr> 
   <th>A. 用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关</th> 
   <th>B. 用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>C. 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关</td> 
   <td>D. 用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关</td> 
  </tr> 
 </tbody> 
</table>

> 用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关；  
> 用邻接表法存储图，占用的存储空间数只与图中边数和结点个数都有关；

6、已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 1]

7、给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 3]

[20210520212135174.jpg_pic_center]: /images/20221020/3c04af4018484453acf87e7d8d419f69.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/08bd910481534598b3a1071145e86b49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221020/c17cab9addf04f34ae8faa507817363f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221020/984c2e1cb28441ef8f746ef943faffd9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221020/1c065b37347040719704a07a55295e81.png