2023数据结构考试内部题库含答案解析

数据结构考试内部题库含答案解析（全考点）

工、下列关于广度优先算法的说法中，正确的是（）。

I.当各边的权值相等时，广度优先算法可以解决单

源最短路径问题当个边的权值不等时，广度优先

算法可用来解决单源最短路径问题in.广度优先遍

历算法类似于树中的后序遍历算法IV.实现图的广

度优先算法时，使用的数据结构是队列

・•A:I、IV

・・B:口、印、IV

・・C:口、IV

・・D：I、m、iv

解析

广度优先搜索以起始结点为中心，一层一层地向外层

扩展遍历图的顶点，因此无法考虑到边权值，只适合

求边权值相等的图的单源最短路径。广度优先搜索相

当于树的层序遍历，in错误。广度优先搜索需要用到

队列，深度优先搜索需要用到栈，iv正确。

答案：A

2、对一个有n个顶点、e条边的图采用邻接表表示时，进

行DFS遍历的时间复杂度为（），空间复杂度为（）；进行

BFS遍历的时间复杂度为（），空间复杂度为（）。

・・A:0（n）

・・B:0（e）

・・C:0（n+e）

・・D:0（1）

解析

深度优先遍历时，每个顶点表结点和每个边表结点均

查找一次，每个顶点递归调用一次，需要借助一个递

归工作栈；广度优先遍历时，也是每个顶点表结点

和每个边表结点均查找一次，每个顶点进入队列一次。

所以都是选C,Ao

答案：C、A、C、A

3、对一个有n个顶点、e条边的图采用邻接矩阵表示时，

进行DFS遍历的时间复杂度为（），进行BFS遍历的时间

复杂度为（）。

・・B:0(e)

・・C:0(n+e)

e2

・•D:0()

解析

采用邻接矩阵表示时，查找一个顶点所有出边的时间

复杂度为0(n),共有n个顶点,故时间复杂度均为

n2

o()。

答案：A、A

4、如下图所示，在下面的5个序列中，符合深度优先遍历

的序列个数是()

在这里插入图片描述

1.aebfdc

2.acfdeb

3.aedfcb

4.aefdbc

5.aecfdb

・•A:5

・•B:4

・•C:3

・•D:2

解析

仅1和4正确。以2为例,遍历到c之后，与c邻

接且未被访问的结点为空集，所以应为a的邻接点b

或e入栈。以3为例，因为遍历要按栈退回，所以

是先b后c,而不能先c后b。

答案：D

5、用邻接表存储的图的深度优先遍历算法类似于树的（），

而其广度优先遍历算法类似于树的（）。

・・A:中序遍历

・・B:先序遍历

・・C:后序遍历

・•D:按层次遍历

解析

图的深度优先搜索类似于树的先根遍历，即先访问结

点，再递归向外层结点遍历，都采用回溯算法。图

的广度优先搜索类似于树的层序遍历，即一层一层向

外层扩展遍历，都需要采用队列来辅助算法的实现。

答案：B、D

6、一个有向图G的邻接表存储如下图所示从顶点1出发，

对图G调用深度优先遍历所得顶点序列是（）；按广度优先

遍历所得顶点序列是（）,.

在这里插入图片描述

・・A:125436

・・B:124536

・・C:124563

・・D:362514

解析

DFS（深度优先遍历）序列产生的路径为<L2>,

<2,5>,<5,4>,<3,6>;BFS（广度优先遍历）序

列产生的路径为<L2>,<1,4>,<2,5>,<3,6>。

答案：A、B

7、使用DFS算法递归地遍历一个无环有向图，并在退出递

归时输出相应顶点，这样得到的顶点序列是（）。

••A:逆拓扑有序

••B:拓扑有序

・•C:无序的

••D:都不是

解析

对一个有向图做深度优先遍历，并未专门判断有向图是否有

环（有向回路）存在，无论图中是否有环，都得到一个顶点

序列。若无环，在退出递归过程中输出的应是逆拓扑有序序

列。对有向无环图利用深度优先搜索进行拓扑排序的例子

如下：如下图所示，退出DFS（深度优先遍历）栈的顺序为

此图的一个拓扑序列为该方法的每

efgdcahb,bhacdgfeo

一步均是先输出当前无后继的结点，即对每个结点v,先递

归地求出v的每个后继的拓扑序列。对于一个AOV（）网，

按此方法输出的序列是一个逆拓扑序列。

在这里插入图片描述

答案：A

8、设无向图G=（V,E）和G'=（V'fE'），若G，是G的生成

树，则下列说法中错误的是（）。

••A:G'为G的子图

・•B:G'为G的连通分量

・・C:G'为G的极小连通子图且V=V,

・・D:G'是G的一个无环子图

解析

连通分量是无向图的极大连通子图，其中极大的含义

是将依附于连通分量中顶点的所有边都加上，所以连

通分量中可能存在回路，这样就不是生成树了。

注意：极大连通子图是无向图（不一定连通）的连通

分量，极小连通子图是连通无向图的生成树。极小和

极大是在满足连通的前提下，针对边的数目而言的。

极大连通子图包含连通分量的全部边；极小连通子图

（生成树）包含连通图的全部顶点，且使其连通的边

数最少。

答案：B

9、对有n个顶点、e条边且使用邻接表存储的有向图进行

广度优先遍历，其算法的时间复杂度是（）。

・・A:0(n)

・・B:0(e)

・・C:0(n+e)

・・D:0(ne)

解析

广度优先遍历需要借助队列实现。采用邻接表存储方

式对图进行广度优先遍历时，每个顶点均需入队一次

(顶点表遍历)，故时间复杂度为0(n),在搜索所

有顶点的邻接点的过程中，每条边至少访问一次(出

边表遍历)，所以时间复杂度为0(e),算法总的时

间复杂度为O(n+e)o

答案：C

10、平均直找速度而言，下列几种查找速度从慢至快的关系

是O

・•A:顺序折半哈希分块

・•B:JI质序分块折半哈希

.・C:分块折半哈希顺序

•・D:顺序哈希分块折半

解析

顺序查找的时间复杂度为0（n）分块查找的时间复杂

度为o/og?72）到o（n）之间二分查找的时间复杂

度为0（'°。272）哈希查找的时间复杂度为0（1）

答案：B

1、以下关于图的叙述中，正确的是（）。

・・A:强连通有向图的任何顶点到其他所有顶点都有弧

•・B:图的任意顶点的入度等于出度

・•C:有向完全图一定是强连通有向图

--D:有向图的边集的子集和顶点集的子集可构成原有

向图的子图

解析

强连通有向图的任何顶点到其他所有顶点都有路径，

但未必有弧；无向图任意顶点的入度等于出度，但有

向图未必满足；若边集中的某条边对应的某个顶点不

在对应的顶点集中，则有向图的边集的子集和顶点集

的子集无法构成子图。

答案：C

2、一个有28条边的非连通无向图至少有（）个顶点。

・•A:7

・•B:8

・•C:9

・­D:10

解析

考虑非连通图最极端的情况，即它由一个完全图加一

个独立的顶点构成，此时若再加一条边，则必然使图

变成连通图。在28=n（n-l）/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条边的无向图中，有

从而共有16个(5+4+7)顶点。

答案：D

4、设有无向图G=(V,E)和G=(U,E，)若G，是G的生成树，

则下列不正确的是()。

I.G'为G的连通分量H.G'为G的无环子图m.G'

为G的极小连通子图且V1=V

・・A:I、口

・・B：只有m

・•c:口、n

・•D:只有I

解析

一个连通图的生成树是一个极小连通子图，显然它是

无环的，故I、in正确。极大连通子图称为连通分量，

G’连通但非连通分量。极大连通子图：如果图本来

就不是连通的，那么每个子部分若包含它本身的所有

顶点和边，则它就是极大连通子图。

答案：D

5、若具有n个顶点的图是一个环，则它有（）棵生成树。

n2

・•A:

・•B:n

・・C:n-1

・•D:1

解析

n个顶点的生成树是具有n-1条边的极小连通子图，

因为n个顶点构成的环共有n条边，去掉任意一条

边就是一棵生成树，所以共有n种情况，所以可以有

n棵不同的生成树。

答案：B

6、下列关于无向连通图特性的叙述中，正确的是（）o

i.所有顶点的度之和为偶数n.边数大于顶点个

数减1m.至少有一个顶点的度为1

.・A：只有I

・・B:只有口

・・C:I和口

・•D：I和m

解析

无向连通图对应的生成树也是无向连通图，但此时边

数等于顶点数减1,故口错误。考虑一个无向连通图

的顶点恰好构成一个回路的情况，此时每个顶点的度

都是2,故m错误。在无向图中，所有顶点的度之和

为边数的2倍，故I正确。

答案：A

7、若无向图G=(V,E)中含有7个顶点，要保证图G在

任何情况下都是连通的，则需要的边数最少是()。

・•A:6

•B:15

•C:16

•D:21

解析

答案：c

8、一个有n个顶点的图用邻接矩阵A表示若图为有向图，

7?•7?•

顶点’的入度是()；若图为无向图，顶点’的度是()。

在这里插入图片描述

解析

有向图的入度是其第i列的非。元素之