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

《全2023数据结构考试内部题库含答案解析全考点.docx》由会员分享，可在线阅读，更多相关《全2023数据结构考试内部题库含答案解析全考点.docx（16页珍藏版）》请在第一文库网上搜索。

1、数据结构考试内部题库含答案解析（全考点）1、下列关于广度优先算法的说法中，正确的是（）。I.当各边的权值相等时，广度优先算法可以解决单源最短路径问题II当个边的权值不等时，广度优先算法可用来解决单源最短路径问题I广度优先遍历算法类似于树中的后序遍历算法IV.实现图的广度优先算法时，使用的数据结构是队列 A:IxIV.B:H田、IV C:xIV.D：I、m、IV解析广度优先搜索以起始结点为中心，一层一层地向外层扩展遍历图的顶点，因此无法考虑到边权值，只适合求边权值相等的图的单源最短路径。广度优先搜索相当于树的层序遍历，I错误。广度优先搜索需要用到队列，深度优先搜索需要用到栈，IV正确。2、对一个

2、有n个顶点、e条边的图采用邻接表表示时，进行DFS遍历的时间复杂度为（），空间复杂度为（）；进行BFS遍历的时间复杂度为（），空间复杂度为（）。.A:0（n） B:0（e） C:0（n+e） D:0（1）解析深度优先遍历时，每个顶点表结点和每个边表结点均查找一次，每个顶点递归调用一次，需要借助一个递归工作栈；广度优先遍历时，也是每个顶点表结点和每个边表结点均查找一次，每个顶点进入队列一次。所以都是选c,Ao答案：C.A、C.A3、对一个有n个顶点、e条边的图采用邻接矩阵表示时，进行DFS遍历的时间复杂度为（），进行BFS遍历的时间复杂度为（）。 B:0(e) C:0(n+e)2 D:0()解析

3、采用邻接矩阵表示时，查找一个顶点所有出边的时间复杂度为0(n),共有n个顶点，故时间复杂度均为n20()。答案：A、A4、如下图所示，在下面的5个序列中，符合深度优先遍历的序列个数是()在这里插入图片描述1. aebfdc2. acfdeb3. aedfcb4. aefdbc5. aecfdb A:5.B:4 C:3 D:2解析仅1和4正确。以2为例,遍历到C之后，与C邻接且未被访问的结点为空集，所以应为a的邻接点b或e入栈。以3为例，因为遍历要按栈退回，所以是先b后c,而不能先C后b。答案：D5、用邻接表存储的图的深度优先遍历算法类似于树的（），而其广度优先遍历算法类似于树的（）O A:中序

4、遍历B:先序遍历 C:后序遍历 D:按层次遍历解析图的深度优先搜索类似于树的先根遍历，即先访问结点，再递归向外层结点遍历，都采用回溯算法。图的广度优先搜索类似于树的层序遍历，即一层一层向外层扩展遍历，都需要采用队列来辅助算法的实现。答案：B、D6、一个有向图G的邻接表存储如下图所示从顶点1出发，对图G调用深度优先遍历所得顶点序列是（）；按广度优先遍历所得顶点序列是（）。在这里插入图片描述.A:125436 B:124536.C:124563 D:362514解析DFS（深度优先遍历）序列产生的路径为,;BFS（广度优先遍历）序列产生的路径为,o7、使用DFS算法递归地遍历一个无环有向图，并在退

5、出递归时输出相应顶点，这样得到的顶点序列是（）。A:逆拓扑有序.B:拓扑有序C:无序的D:都不是解析对一个有向图做深度优先遍历，并未专门判断有向图是否有环（有向回路）存在，无论图中是否有环，都得到一个顶点序列。若无环，在退出递归过程中输出的应是逆拓扑有序序列。对有向无环图利用深度优先搜索进行拓扑排序的例子如下：如下图所示，退出DFS（深度优先遍历）栈的顺序为efgdcahb,此图的一个拓扑序列为bhacdgfeo该方法的每一步均是先输出当前无后继的结点，即对每个结点V,先递归地求出V的每个后继的拓扑序列。对于一个AOV（）网，按此方法输出的序列是一个逆拓扑序列。在这里插入图片描述答案：A8、设

6、无向图G=（V,E）ff1G=（V,E）,若G是G的生成树，则下列说法中错误的是（）。 A:G为G的子图.B:G为G的连通分量 C:G为G的极小连通子图且V=V D:G是G的一个无环子图解析连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以连通分量中可能存在回路，这样就不是生成树了。注意：极大连通子图是无向图（不一定连通）的连通分量，极小连通子图是连通无向图的生成树。极小和极大是在满足连通的前提下，针对边的数目而言的。极大连通子图包含连通分量的全部边；极小连通子图（生成树）包含连通图的全部顶点，且使其连通的边数最少。答案：B9、对有n个顶点、e条边且使用

7、邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是（）。 A:0(n).B:O(e) C:O(n+e).D:O(ne)解析广度优先遍历需要借助队列实现。采用邻接表存储方式对图进行广度优先遍历时，每个顶点均需入队一次(顶点表遍历)，故时间复杂度为O(FI),在搜索所有顶点的邻接点的过程中，每条边至少访问一次(出边表遍历)，所以时间复杂度为0(e),算法总的时间复杂度为O(ne)o答案：C10、平均查找速度而言，下列几种查找速度从慢至快的关系是O A:J1砺折半哈希分块 B:J1质序分块折半哈希 C:分块折半哈希J1褥 D:顺序哈希分块折半解析顺序查找的时间复杂度为O(FI)分块查找的时间复

8、杂度为O(092)到0(n)之间二分查找的时间复杂度为OQOg271)哈希查找的时间复杂度为O(I)答案：B1、以下关于图的叙述中，正确的是()。.A:强连通有向图的任何顶点到其他所有顶点都有弧B:图的任意顶点的入度等于出度C:有向完全图一定是强连通有向图D:有向图的边集的子集和顶点集的子集可构成原有向图的子图解析强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧；无向图任意顶点的入度等于出度，但有向图未必满足，若边集中的某条边对应的某个顶点不在对应的顶点集中，则有向图的边集的子集和顶点集的子集无法构成子图。答案：C2、一个有28条边的非连通无向图至少有（）个顶点。.A:7B:8.C:9

9、D:10解析考虑非连通图最极端的情况，即它由一个完全图加一个独立的顶点构成，此时若再加一条边，则必然使图变成连通图。在28=n（n-1）2=8x72条边的完全无向图中总共有8个顶点，再加上1个不连通的顶点，共9个顶点。答案：C3、无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G有（）个顶.A:11.B:12.C:15解析由于在具有n个顶点、e条边的无向图中，有从而共有16个(547)顶点。答案：D4、设有无向图G=(V,E)和G=(UF)若G是G的生成树，则下列不正确的是()。I.G为G的连通分量I1G为G的无环子图I.G为G的极小连通子图且V=V.A:

10、IxB:只有In.c：xm.D:只有I解析一个连通图的生成树是一个极小连通子图，显然它是无环的，故I、In正确。极大连通子图称为连通分量，G连通但非连通分量。极大连通子图：如果图本来就不是连通的，那么每个子部分若包含它本身的所有顶点和边，则它就是极大连通子图。答案：D5、若具有n个顶点的图是一个环，则它有（）棵生成树。.B:n.C:n-1.D:1解析个顶点的生成树是具有n-1条边的极小连通子图，因为个顶点构成的环共有条边，去掉任意一条边就是一棵生成树，所以共有n种情况，所以可以有n棵不同的生成树。答案：B6、下列关于无向连通图特性的叙述中，正确的是（）。I.所有顶点的度之和为偶数.边数大于顶点

11、个数减1m.至少有一个顶点的度为1.a：只有IB:只有IIC:I和UD:I和IU解析无向连通图对应的生成树也是无向连通图，但此时边数等于顶点数减1,故II错误。考虑一个无向连通图的顶点恰好构成一个回路的情况，此时每个顶点的度都是2,故In错误。在无向图中，所有顶点的度之和为边数的2倍，故I正确。答案：A7,若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是()。.A:6.B:15.C:16解析答案：C8、一个有n个顶点的图用邻接矩阵A表示若图为有向图，顶点的入度是()；若图为无向图，顶点，的度是()。在这里插入图片描述解析有向图的入度是其第i列的非O元素

12、之和，无向图的度是第i行或第i列的非O元素之和。答案：B、D9、n个顶点的无向图的邻接表最多有()个边表结点。n2 A: B:n(n-1) C:n(n+1) D:n(n-1)2解析个顶点的无向图最多有(n-1)2条边，每条边在邻接表中存储两次，所以边表结点最多为n(n-1)个。答案：B10.对邻接表的叙述中，()是正确的。A:无向图的邻接表中，第i个顶点的度为第i个链表中结点数的两倍.B:邻接表比邻接矩阵的操作更简便C:邻接矩阵比邻接表的操作更简便D:求有向图结点的度，必须遍历整个邻接表解析无向图的邻接表中，第i个顶点的度为第i个链表中的结点数，故A错。邻接表和邻接矩阵对于不同的操作各有优势，B和C都不准确。有向图结点的度包括出度和入读，对于出度，需要遍历顶点表结点所对应的边表；对于入读，则需要遍历剩下的全部边表，故D正确。