数据结构错题收录（九）
1、以下关于图的叙述中，正确的是（）。
- A：强连通有向图的任何顶点到其他所有顶点都有弧
- B：图的任意顶点的入度等于出度
- C：有向完全图一定是强连通有向图
- D：有向图的边集的子集和顶点集的子集可构成原有向图的子图
解析
强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧；无向图任意顶点的入度等于出度，但有向图未必满足；若边集中的某条边对应的某个顶点不在对应的顶点集中，则有向图的边集的子集和顶点集的子集无法构成子图。
答案：C
2、一个有28条边的非连通无向图至少有（）个顶点。
- A：7
- B：8
- C：9
- D：10
解析
考虑非连通图最极端的情况，即它由一个完全图加一个独立的顶点构成，此时若再加一条边，则必然使图变成连通图。在28=n(n-1)/2=8x7/2条边的完全无向图中，总共有8个顶点，再加上1个不连通的顶点，共9个顶点。
答案：C
3、无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G有（）个顶点。
- A：11
- B：12
- C：15
- D：16
解析
由于在具有n个顶点、e条边的无向图中，有TD(
)=2e，可求得度为2的顶点数为7，从而共有16个（5+4+7）顶点。
答案：D
4、设有无向图G=(V,E)和G'=(V',E')，若G'是G的生成树，则下列不正确的是（）。
Ⅰ.G'为G的连通分量
Ⅱ. G'为G的无环子图
Ⅲ. G'为G的极小连通子图且V'=V
- A：Ⅰ、Ⅱ
- B：只有Ⅲ
- C：Ⅱ、Ⅲ
- D：只有Ⅰ
解析
一个连通图的生成树是一个极小连通子图，显然它是无环的，故Ⅰ、Ⅲ正确。极大连通子图称为连通分量，G'连通但非连通分量。
极大连通子图：如果图本来就不是连通的，那么每个子部分若包含它本身的所有顶点和边，则它就是极大连通子图。
答案：D
5、若具有n个顶点的图是一个环，则它有（）棵生成树。
- A：
- B：n
- C：n-1
- D：1
解析
n个顶点的生成树是具有n-1条边的极小连通子图，因为n个顶点构成的环共有n条边，去掉任意一条边就是一棵生成树，所以共有n种情况，所以可以有n棵不同的生成树。
答案：B
6、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ. 所有顶点的度之和为偶数
Ⅱ. 边数大于顶点个数减1
Ⅲ. 至少有一个顶点的度为1
- A：只有Ⅰ
- B：只有Ⅱ
- C：Ⅰ和Ⅱ
- D：Ⅰ和Ⅲ
解析
无向连通图对应的生成树也是无向连通图，但此时边数等于顶点数减1，故Ⅱ错误。考虑一个无向连通图的顶点恰好构成一个回路的情况，此时每个顶点的度都是2，故Ⅲ错误。在无向图中，所有顶点的度之和为边数的2倍，故Ⅰ正确。
答案：A
7、若无向图G=（V，E）中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是（）。
- A：6
- B：15
- C：16
- D：21
解析
答案：C
8、一个有n个顶点的图用邻接矩阵A表示，若图为有向图，顶点
的入度是（）；若图为无向图，顶点的度是（）。
在这里插入图片描述
解析
有向图的入度是其第i列的非0元素之和，无向图的度是第i行或第i列的非0元素之和。
答案：B、D
9、n个顶点的无向图的邻接表最多有（）个边表结点。
- A：
- B：n(n-1)
- C：n(n+1)
- D：n(n-1)/2
解析
n个顶点的无向图最多有n(n-1)/2条边，每条边在邻接表中存储两次，所以边表结点最多为n(n-1)个。
答案：B
10、对邻接表的叙述中，（）是正确的。
- A：无向图的邻接表中，第i个顶点的度为第i个链表中结点数的两倍
- B：邻接表比邻接矩阵的操作更简便
- C：邻接矩阵比邻接表的操作更简便
- D：求有向图结点的度，必须遍历整个邻接表
解析
无向图的邻接表中，第i个顶点的度为第i个链表中的结点数，故A错。
邻接表和邻接矩阵对于不同的操作各有优势，B和C都不准确。
有向图结点的度包括出度和入读，对于出度，需要遍历顶点表结点所对应的边表；对于入读，则需要遍历剩下的全部边表，故D正确。
