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

数据结构考试内部题库含答案解析（全考点）、下列关于广度优先算法的说法中，正确的是（）1工.当各边的权值相等时，广度优先算法可以解决单源最短路径问题当个边的权值不等时，广度优先算法可用来解决单n.源最短路径问题印.广度优先遍历算法类似于树中的后序遍历算法实现图的广度优先算法时，使用的数据结构是队列IV.・、•A:I IV・•口、、B miv・（！!、IV•・、印、•D:I IV解析广度优先搜索以起始结点为中心，一层一层地向外层扩展遍历图的顶点，因此无法考虑到边权值，只适合求边权值相等的图的单源最短路径广度优先搜索相当于树的层序遍历，印错误广度优先搜索需要用到队列，深度优先搜索需要用到栈，正确IV答案A、一个有条边的非连通无向图至少有（）个顶点228・•A:7・•B:8・•C:9・•D:10解析考虑非连通图最极端的情况，即它由一个完全图加一个独立的顶点构成，此时若再加一条边，则必然使图变成连通图在（）条边的完全无向图中总共有个28=n n-l/2=8x7/28顶点，再加上个不连通的顶点，共个顶点19答案C、无向图有条边，度为的顶点有个，度为的顶3G23453）点有个，其余都是度为的顶点，则图有（个顶42G•A:11•B:12•C:15•D:16由于在具有个顶点、条边的无向图中，有n enfTDgi=1=2e，可求得度为的顶点数为27,从而共有个顶点165+4+7答案D.设有无向，4和若是的生成树,G=V,E G=U,E G G则下列不正确的是为的连通分量为的无环子图为的极小I.G GH.G Gffl.G G连通子图且V=V•、□A:I•只有B m•、c nm•只有工D解析一个连通图的生成树是一个极小连通子图，显然它是无环的，故、印正确极大连通子图称为连通分量，I连通但非连通分量极大连通子图如果图本来G’就不是连通的，那么每个子部分若包含它本身的所有顶点和边，则它就是极大连通子图答案D、若具有个顶点的图是一个环，则它有（）棵生成树5n2n.•A:・•B:n・•C:n-1・•D:1解析个顶点的生成树是具有条边的极小连通子图，因为n n-1n个顶点构成的环共有条边，去掉任意一条边就是一棵生成n树，所以共有种情况，所以可以有棵不同的生成树n n答案B下列关于无向连通图特性的叙述中，正确的是（）

6.所有顶点的度之和为偶数边数大于顶点个数减至少i.n.1m.有一个顶点的度为1••只有A I•:只有•B II•和•C:I II••和D Iin解析无向连通图对应的生成树也是无向连通图，但此时边数等于顶点数减故口错误考虑一个无向连通图的顶点恰好构成1,一个回路的情况，此时每个顶点的度都是故错误在2,m无向图中，所有顶点的度之和为边数的倍，故工正确2答案A

7.若无向图中含有个顶点，要保证图在任何G=V,E7G情况下都是连通的，则需要的边数最少是.•A:6・•B:15・•C:16・•D:21答案一个有个顶点的图用邻接矩阵表示若图为有向c nA3Vj顶点’的入度是（）；若图为无向图，顶点,的度是（）在这里插入图片描述解析有向图的入度是其第列的非元素之和，无向图的度是第i0i行或第列的非元素之和i0答案B.D、个顶点的无向图的邻接表最多有（）个边表结点9n2n・A:•B:nn-l•C:nn+l个顶点的无向图最多有条边，每•D:nn-l/2n nn-l/2条边在邻接表中存储两次，所以边表结点最多为nn-l个答案B对邻接表的叙述中，是正确的

10.・:无向图的邻接表中，第个顶点的度为第个链表中•A i i结点数的两倍・:邻接表比邻接矩阵的操作更简便•B・:邻接矩阵比邻接表的操作更简便•C:求有向图结点的度，必须遍历整个邻接表.•D解析无向图的邻接表中，第个顶点的度为第个链表中的结点数，ii故错邻接表和邻接矩阵对于不同的操作各有优势，和A B都不准确有向图结点的度包括出度和入读，对于出度，C需要遍历顶点表结点所对应的边表；对于入读，则需要遍历剩下的全部边表，故正确D答案D、对一个有个顶点、条边的图采用邻接表表示时，进行2n e（）（）；遍历的时间复杂度为，空间复杂度为进行DFS BFS遍历的时间复杂度为（），空间复杂度为（）・（）•A:0n・（）•B:0e・（）•C:0n+e・（）•D:01解析深度优先遍历时，每个顶点表结点和每个边表结点均查找一次，每个顶点递归调用一次，需要借助一个递归工作栈；广度优先遍历时，也是每个顶点表结点和每个边表结点均查找一次，每个顶点进入队列一次所以都是选C,Ao答案uA.C.A对一个有个顶点、条边的图采用邻接矩阵表示时,

3.n e进行遍历的时间复杂度为（），进行遍历的时间复DFS BFS杂度为（）•B:0e・2•C:0n+e e・•D:0解析采用邻接矩阵表示时，查找一个顶点所有出边的时间复杂度为共有个顶点，故时间复杂度均为20n,n n0答案、A A如下图所示，在下面的个序列中，符合深度优先遍历

4.5的序列个数是在这里插入图片描述

1.aebfdc

2.acfdeb

3.aedfcb

4.aefdbc

5.aecfdb・•A:5・•B:4・•C:3・•D:2解析仅和正确以为例，遍历到之后，与邻接且未被142c c访问的结点为空集，所以应为的邻接点或入栈以a be3为例，因为遍历要按栈退回，所以是先后而不能先后b c,cb答案D用邻接表存储的图的深度优先遍历算法类似于树的（），

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

7、使用算法递归地遍历一个无环有向图，并在退出递归DFS时输出相应顶点，这样得到的顶点序列是（）:逆拓扑有序••A:拓扑有序••B:无序的••C:都不是••D解析对一个有向图做深度优先遍历，并未专门判断有向图是否有环（有向回路）存在，无论图中是否有环，都得到一个顶点序列若无环，在退出递归过程中输出的应是逆拓扑有序序列对有向无环图利用深度优先搜索进行拓扑排序的例子如下如下图所示，退出（深度优先遍历）栈的顺序为DFS此图的一个拓扑序列为该方法的每一efgdcahb,bhacdgfeo步均是先输出当前无后继的结点，即对每个结点,先递归地v求出的每个后继的拓扑序列对于一个（）网，按v AOV此方法输出的序列是一个逆拓扑序列□在这里插入图片描述，、设无向图（）和（）,若是的8G=V,E G=V FG G生成树，则下列说法中错误的是（）・为的子图•A:G G・为的连通分量•B:G G・为的极小连通子图且•C:G GV=V・是的一个无环子图•D:GG解析连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以连通分量中可能存在回路，这样就不是生成树了注意极大连通子图是无向图（不一定连通）的连通分量，极大是在满足连通的前提下，针对边的数而言的极小连通子图是连通无向图的生成树极小和极大连通子图包含连通分量的全部边；极小连通子（生成树）包含连通图的全部顶点，且使其连通的边数最少答案B对有个顶点、条边且使用邻接表存储的有向图进行

9.n e广度优先遍历，其算法的时间复杂度是（）O・•A:0n・•B:0e・•C:0n+e・•D:0ne解析广度优先遍历需要借助队列实现采用邻接表存储方式对图进行广度优先遍历时，每个顶点均需入队一次顶点表遍历，故时间复杂度为在搜索所有顶点的邻接点的过程中，每0n,条边至少访问一次出边表遍历，所以时间复杂度为算0e,法总的时间复杂度为On+eo答案C、平均查找速度而言，下列几种查找速度从慢至快的关系是10O:顺序折半哈希分块.•A:顺序分块折半哈希••B・:分块折半哈希顺序•C:顺序哈希分块折半解析顺序查找的时间复杂度为••D分块查找的时间复杂度为到之间二分查找0n00g2on的时间复杂度为72哈希查找的时间复杂度为o/og201答案B以下关于图的叙述中，正确的是

1.O・:强连通有向图的任何顶点到其他所有顶点都有弧•A・图的任意顶点的入度等于出度•B:・:有向完全图一定是强连通有向图•C・:有向图的边集的子集和顶点集的子集可构成原有向图•D的子图解析强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧；无向图任意顶点的入度等于出度，但有向图未必满足；若边集中的某条边对应的某个顶点不在对应的顶点集中，则有向图的边集的子集和顶点集的子集无法构成子图。