数据结构题目收录（九）

女爷i 2024-04-06 11:42 49阅读 0赞

#### 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条边的无向图中，有 ∑ i = 1 n \\displaystyle\\sum\_\{i=1\}^n i=1∑nTD( v i v\_i vi)=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： n 2 n^2 n2
 *  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表示，若图为有向图，顶点 v i v\_i vi的入度是（）；若图为无向图，顶点 v i v\_i vi的度是（）。 ####

![在这里插入图片描述][54e92ebcf3ef421f9dfbca6754ca4576.png]

###### 解析 ######

有向图的入度是其第i列的非0元素之和，无向图的度是第i行或第i列的非0元素之和。

###### 答案：B、D ######

#### 9、n个顶点的无向图的邻接表最多有（）个边表结点。 ####

*  A： n 2 n^2 n2
 *  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正确。

###### 答案：D ######

### 学海无涯苦作舟 ###

![请添加图片描述][3a8d30946f1246e79dba5bdb96ae3002.jpeg]

[54e92ebcf3ef421f9dfbca6754ca4576.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/e0a5b01b53234bfcb5fd8999380a92c5.png
[3a8d30946f1246e79dba5bdb96ae3002.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8a9e79d2ab8043f2a9ded0acbb3addbd.jpeg