一、单项选择题第01~40小题每小题2分共80分。下列每题给出的四个选项中只有一个选项是最符合题目要求的。数据结构一般是第01~11小题。01.(99 封私信 / 94 条消息) 2022年408真题数据结构篇 - 知乎下列程序段的时间复杂度是 。int sum 0; for (int i 1; i n; i * 2) for (int j 0; j i; j) sum;A.B.C.D.解答方法一精确计算法本题为多层循环中嵌套循环指针相关类型题且指针变化非线性所以只能进行计算程序主要代价为sum设sum的代价为1这里统计sum的执行次数用 表示外层循环的迭代轮次设 的最大值为 则对于外层循环的 第一次迭代有 第 次迭代有 最后一次迭代有 其中 即 为满足 的最大整数推出 此时 。对于内层循环的 第一次迭代有 最后一次迭代有 。综上推出如下计算式本题选B。由于这里用到了不等式运算所以涉及 的定义描述渐近上界给定函数 , 。一般书写为 计算可转化为 。同时涉及取整符号性质一般情况下取整计算不会渐近改变算法的时间复杂度所以我们可以直接去掉取整符号或者将 视为 2 的自然数次幂上面的计算可以简化为结果不变。本题选 B。02.给定有限符号集 in和out均为 中所有元素的任意排列。对于初始为空的栈ST下列叙述中正确的是 。对于入栈和出栈关于入栈序列S1和出栈序列S2的说法正确的是A. 若in是ST的入栈序列则不能判断out是否为其可能的出栈序列B. 若out是ST的出栈序列则不能判断in是否为其可能的入栈序列C. 若in是ST的入栈序列out是对应in的出栈序列则in与out一定不同D. 若in是ST的入栈序列out是对应in的出栈序列则in与out可能互为倒序解答本题考察对栈的理解。简化下表述如下A. 入栈序列不能推导出栈序列B. 出栈序列不能推导入栈序列C. 入栈序列和出栈序列一定不同D. 入栈序列和出栈序列可以相反题目意思为给定 个互不相同的元素这些元素组成集合S。如果入栈序列由 个互不相同的元素组成出栈序列有 卡特兰数种可能而且入栈顺序推导出栈顺序可逆。给定入栈序列只要判断给定的出栈序列是否为 中的一个序列所以A选项错误。当然也可以不必要这复杂根据入栈序列检查出栈序列是否符合栈先进后出的性质。同理给定出栈序列只要判断给定的入栈序列是否为 中的一个序列B选项错误。当然也可以不必要这复杂根据入栈序列检查出栈序列是否符合栈先进后出的性质。关于C选项如果每个元素入栈后马上出栈得到的出栈序列与入栈序列完全相同所以C选项错误。也可以举特例假设入栈序列只有一个元素得到的入栈序列和出栈序列一定相同。关于D选项如果序列元素全部入栈后再依次出栈得到的出栈序列与入栈序列完全相反所以D选项正确。本题选D。评这道题主要考察栈先进后出的特性。408如果加大难度会考察入栈序列长度大于栈深度的情况即序列元素不可能全部入栈后再依次出栈只能部分入栈即需要执行出栈。03.若结点p与q在二叉搜索树T中的中序遍历中相邻且p在q之前则下列p与q的关系中不可能的是 。I. q是p的双亲II. q是p的右孩子III. q是p的右兄弟IV. q是p的双亲的双亲A. 仅IB. 仅IIIC. 仅II、IIID. 仅II、IV解答方法一性质由题意p是q的前驱q是p的后继则p是q的左子树的最右结点或者q是p的右子树的最左结点。很明显p和q只存在父子和祖孙关系不存在兄弟关系。反证法也可以证明假设p和q为兄弟则中序遍历为左根右p个q的双亲结点必然位于p和q之间与“结点p与q在二叉搜索树T中的中序遍历中相邻”的题目条件矛盾所以p和q为兄弟关系不成立III错误。下面分别讨论情况一p是q的左子树的最右结点那么p一定没有右孩子。此时p是q的子孙结点其中包含p是q的左孩子结点的情况此时q是p的双亲I正确。也包含q是p的祖父结点的情况此时q是p的双亲的双亲IV正确。情况二q是p的右子树的最左结点那么q一定没有左孩子。此时q是p的子孙结点其中包含q是p的右孩子结点的情况此时q是p的双亲II正确。综上只有III错误注意这里选不可能的。本题选B。方法二画图当然从二叉搜索树的性质入手过于复杂我们可以直接举例尽量保证p在q的左边。如图只有III错误注意这里选不可能的。本题选B。04.若三叉树T有244个结点叶结点的高度为1则T的高度至少是 。A. 4B. 5C. 6D. 7解答关键词“至少”很容易想到完全二叉树设树高 满三叉树结点数为 。最后一层只有一个结点的完全二叉树结点数为则 解得 。本题选C。评这道题一定不能直接套用完全二叉树高度公式 由于是三叉树用等比数列求和的时候最后分母有一个 计算一定小心。这里有一个有意思的地方题目标注叶结点的高度为1这是为了区别一些教材比如《算法导论》设定叶结点的高度为0所以考试时候一切标准以题目为准。05.对于任意给定的含 个字符集的有限集 用二叉树表示 的哈夫曼编码集和定长编码集分别得到二叉树T1和T2。下列叙述中正确的是 。A. T1和T2的结点数相同B. T1的高度大于T2的高度C. 出现频次不同的字符在T1中处于不同的层D. 出现频次不同的字符在T2中处于相同的层解答本题多出了一个概念等长编码。等长编码是一种简单且译码具有唯一性的编码方式这种编码方式的特点是每个字符的编码长度相同。由哈夫曼编码和等长编码两种方式生成的二叉树T1和T2。T1为哈夫曼树T2为等长编码树。但是哈夫曼树考虑了词频需要用到前缀编码按照词频从大到小排序一般词频越高的编码长度越短。例一假设字符集只含有4个字符A、B、C、D用两位二进制表示的编码分别为00011011。如图(a)所示。假设字符集只含有4个字符A、B、C、D对应词频为10、1、5、100。按照词频从大到小排序为D、A、C、B构造哈夫曼树为如图(b)所示。例二假设字符集只含有4个字符A、B、C用两位二进制表示的编码分别为000110。如图(c)所示。假设字符集只含有4个字符A、B、C对应词频为10、1、5。按照词频从大到小排序为A、C、B构造哈夫曼树为如图(d)所示。对于A选项例二中哈夫曼树的结点个数为5等长编码树的结点个数为6明显不相等错误。对于B选项例二中哈夫曼树的高度等于等长编码树的高度错误。对于C选项假设字符集只含有4个字符A、B、C对应词频为10、5、4。B和C词频不相等位于相同层错误。排除法已经可得D选项正确。D选项就是等长编码树的定义正确。本题选D。评当构造哈夫曼树的字符有 个且词频相等此时构造的哈夫曼树和构造的等长编码树一致。408喜欢总考一些新概念这些概念其实就是“望文生义”千万不要天马行空408是非常考验阅读理解的。构造二叉树用于举例的时候很容易想到要构造满二叉树同时构造非满二叉树进行对比这时候哈夫曼树和等长编码树的区别就出来了哈夫曼树只有度为0和2的结点。06.对于无向图 下列选项中正确的是 。A. 当 时 一定是连通的B. 当 一定是连通的C. 当 一定是不连通的D. 当 一定是不连通的解答根据贪心策略若 一定连通则需要即先分成两个连通分量 一个顶点数量为 结点之间两两相连边数为 另一个为一个顶点边数为 最后连接两个连通分量需要 条边。贪心策略的正确性是建立在单调性的基础上的选择题无需证明。B选项错误C选项错误。考虑 个顶点完全连通边最少的情况因为完全连通所以只有一个连通分量由贪心思路可知这个连通分量为最小生成树此时 此时 即 时一定不连通。A选项错误D选项正确。本题选D。07.下图是有 个活动的AOE网时间余量最大的活动是 。A. cB. gC. hD. j解答方法一完整推理找出一个拓扑序列。按拓扑序列从源点往汇点推导事件顶点 的最早发生时间 。按逆拓扑序列从汇点往源点推导事件顶点 的最晚发生时间 。推导活动有向边 的最早发生时间 即有向边 的起点 的最早发生时间 。推导活动有向边 的最晚发生时间 即有向边 的终点最晚发生时间 减去弧长 。计算活动时间余量 时间余量为 的活动为关键活动。拓扑序列1, 2, 3, 4, 5, 6。边很明显g 的活动余量最大。本题选B。方法二贪心如果在考场上你真这么老老实实画表格去解关键路径题那么你就真傻逼了原因是考场时间非常紧不允许你这么磨磨唧唧如何秒杀贪心找关键路径就是找从源点到汇点的最长路径。直接找出里面最长的几条边构造关键路径b5、i4、d3、e3、f3枚举到这边就差不多了我们发现b5、e3、i4已经能将源点到汇点连通了默认这就是从源点到汇点的最长路径下面开始看看从源点到汇点的最短边 a2、c3、g1我们观察反差最明显的明显路径有多条简单路径可以实现最短一条是 最长一条是 g的时间余量明显很大。虽然这种贪心做法正确率并非100%但足够高效就行毕竟一道选择题只值2分。本题选B。评掌握足够的秒题技巧是非常有效的。贪心策略是秒杀选择题的大杀器08.在下图所示的5阶B树 中删除关键字 之后需要进行必要的调整得到新的B树 。下列选项中不可能是 根结点中的关键字序列的是 。A.B.C.D.解答方法一搜索树性质B树是一棵多路平衡搜索树B树满足搜索树性质即关键字从左到右单调递增。阶B树每个结点除根结点外关键字数量 为 。本题5阶B树 。注意这道题考察不可能。我们可以正向推导删除关键字260然后对B树进行调整。这里提供逆向思维我们从选项出发构造出对应的搜索树。或是说我们并不需要构造出B树中删除操作的算法构造B树删除操作的算法有一个原则就是不能违反B树的性质所以我们只需要检查结果有没有违反B树性质。B树满足搜索树性质即关键字从左到右单调递增本题中叶结点的所有关键字范围在其父结点的两个关键字之间某结点的最左端叶结点可以视为该叶结点的前驱结点的最右关键字到该结点第一个关键字之间某结点的最右端叶结点可以视为最后一个关键字到该叶结点的后继结点的最左关键字之间。如果某结点的最左端叶结点没有前驱可以视为 到该结点第一个关键字之间如果某结点的最右端叶结点没有后继可以视为最后一个关键字到 之间。然后检查是否为构造的树是否为一棵5阶B树。很明显D中关键字100所在的结点只有一个关键字违反 。本题选D。方法二执行删除操作本题考察B树的性质以及删除操作后出现的情况。因为《数据结构C语言版》并未详细介绍B树中非叶结点中关键字的删除操作所以这道题从正面推导难度极大。方案一用直接后继替换《数据结构基础》第一版B树删除操作找到260的直接后继关键字280删除260将280上移到原先260所在的位置此时300所在结点只有一个关键字该结点的右兄弟结点关键字个数等于2即“兄弟不够借”将该结点和其右兄弟结点合并新的孩子结点并将350下移到该新的孩子结点。A选项正确。方案二用直接前驱替换《数据结构基础》第一版B树删除操作的镜像版找到260的直接前驱关键字110删除260将110上移到260原先所在的位置此时100所在结点只有一个关键字该结点的左兄弟结点关键字个数大于2即“兄弟够借”将90下移到100所在结点再将85上移到原先90所在的位置结束。C选项正确。方案三合并孩子结点《数据结构基础》第二版B树删除操作删除260后合并原260左右两个孩子结点形成新的孩子结点。B选项正确。只有D选项没有办法通过以上途径构造。本题选D。总结对于B树的删除操作一般解题步骤如下第一步检查B树中每个结点的度和包含关键字数量是否合规。第二步检查B树中是否满足搜索树性质。第三步观察B树的叶结点执行删除关键字操作后可能的情况有直接删除“兄弟够借”“兄弟不够借”三种情况。特别是“兄弟不够借”产生下溢需要迭代执行若下溢一直传递到根结点导致根结点变空则需要改变根结点B树高度减一。拓展《数据结构C语言版》仅简单介绍了B树中非叶结点中关键字的删除操作详见《数据结构基础》1976年版即《数据结构基础》的第一版10.2.3 节 Tree-Indexing: B-Trees。合并孩子结点参考《算法导论》中的B树删除操作的算法思想。参考《数据结构C语言版》的参考用书《数据结构基础》相关章节如下《数据结构C语言版》B树中的删除操作完整版解读本人整理如下408数据结构考点B树09.影响散列哈希方法平均查找长度的是 。I. 装填因子II. 散列函数III. 冲突解决策略A. 仅I、IIB. 仅I、IIIC. 仅II、IIID. I、II、III解答本题为送分题散列哈希表三要素全选。本题选D。10.使用二路归并排序对含 个元素的数组 进行排序时二路归并排序操作的功能是 。A. 将两个有序表合并为一个新的有序表B. 将 划分为两部分两部分的元素个数大致相等C. 将 分成 个部分每个部分中仅含有一个元素D. 将 划分为两部分一部分元素的值均小于另一部分元素值解答A选项正确归并排序中的归并merge操作就是将两个有序表合并成一个表。B选项错误这是快速排序的调优当枢轴进行平衡划分的时候即两部分元素数量大致相等快速排序的性能是最好的。C选项错误归并排序不一定要分成 部分使得最小归并段只有一个元素。其实最小归并段可以包含多个元素详见《算法导论》思考题2-1算法导论第四版第二章入门 思考题。D选项错误这是快速排序的性质枢轴将数组分成左右两侧如果所有元素互不相同调整后枢轴左侧元素小于枢轴右侧元素。本题选A。11.对数据进行排序时若采用直接插入排序而不采用快速排序则可能的原因是 。I. 大部分元素已有序II. 待排序元素数量很少III. 要求空间复杂度为IV. 要求排序算法是稳定的A. 仅I、IIB. 仅III、IVC. 仅I、II、IVD. I、II、III、IV解答这里考察直接插入排序和快速排序的对比枚举如下数据量较小适合直接插入排序数据量较大适合用快速排序。直接插入排序是稳定的快速排序是不稳定的。直接插入排序的空间复杂度为 快速排序的空间复杂度为 。直接插入排序的平均情况和最坏情况时间复杂度为 最好情况时间复杂度为 当数据基本有序时出现快速排序的最好情况时间复杂度和平均情况时间复杂度为 最差情况时间复杂度为 如果每次枢轴划分数组都非常不平衡就会出现例如数据基本有序且每次枢轴选择在最左或者最右时。综上很明显选I、II、III、IV虽然其它选项也对但是注意选最符合的所以全选。本题选D。例如Java中在对基本数据类型的数组排序时Arrays.sort()函数通过调用DualPivotQuicksort.sort()完成排序当数组长度达到QUICKSORT_THRESHOLD 286时并且不存在较多连续相等元素并且“高度结构化”时采用类似TimSort的算法进行排序当数组长度小于INSERTION_SORT_THRESHOLD 47时采用插入排序或双插入排序否则采用双轴快排进行排序。评这类多选型单选题在考场上如果因为水平有限只能排除部分选项的情况下宁多选不少选和做政治毛中特选择题的套路一致。二、综合应用题41~47小题共70分。数据结构一般是第41~42小题。41.13分已知非空二叉树T的结点值均为正整数采用顺序存储方式保存数据结构定义如下typedef struct { // MAX_SIZE为已定义常量 int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组 int ElemNum; // 实际占用的数组元素个数 }SqBiTree;T中不存在的结点在数组SqBiTNode中用-1表示。例如对于下图所示的两棵非空二叉树T1和T2请设计一个尽可能高效的算法判定一棵采用这种方式存储的二叉树是否为二叉搜索树若是则返回true否则返回false要求⑴ 给出算法的基本设计思想。⑵ 根据设计思想采用C或C语言描述算法关键之处给出注释。解答注意本题二叉树以静态数组的方式表示数组起始下标为0。先画出二叉树然后将其填充为完全二叉树按照层序遍历顺序填写编号如果根结点下标为0适用于C/C语言数组有 left_child_id parent_id * 2 1; right_child_id parent_id * 2 2;如果根结点下标为1这时候题目会写明条件。为了方便解答结构体中的Elemtype默认为int。方法一递归利用二叉搜索树的性质设 是二叉搜索树中的一个结点。如果是左子树中的一个结点那么如果是右子树中的一个结点那么。C代码如下含测试用例#include stdio.h #include string.h #include limits.h #define MAX_SIZE 20011 #define false 0 #define true 1 typedef int bool; typedef struct { // MAX_SIZE为已定义常量 int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组 int ElemNum; // 实际占用的数组元素个数 }SqBiTree; bool helper(SqBiTree T, int i, long long lower, long long upper) { if (i T.ElemNum || T.SqBiTNode[i] -1) { // 越界或者为空结点 return true; } if (T.SqBiTNode[i] lower || T.SqBiTNode[i] upper) { return false; } return helper(T, 2 * i 1, lower, T.SqBiTNode[i]) helper(T, 2 * i 2, T.SqBiTNode[i], upper); } bool isValidBST(SqBiTree T) { return helper(T, 0, LONG_MIN, LONG_MAX); } int main() { int a1[10] {40, 25, 60, -1, 30, -1, 80, -1, -1, 27}; SqBiTree bt1; memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode)); bt1.ElemNum 10; for (int i 0; i bt1.ElemNum; i) { bt1.SqBiTNode[i] a1[i]; } int ans1 isValidBST(bt1); if (ans1 true) { printf(T1 is a binary search tree\n); } else { printf(T1 is not a binary search tree\n); } int a2[11] {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35}; SqBiTree bt2; memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode)); bt2.ElemNum 11; for (int i 0; i bt2.ElemNum; i) { bt2.SqBiTNode[i] a2[i]; } int ans2 isValidBST(bt2); if (ans2 true) { printf(T2 is a binary search tree\n); } else { printf(T2 is not a binary search tree\n); } return 0; }复杂度分析时间复杂度 其中 为二叉树的结点个数。在递归调用的时候二叉树的每个结点最多被访问一次因此时间复杂度为 。空间复杂度 其中 为二叉树的结点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间所以这里需要额外的空间且该空间取决于递归的深度即二叉树的高度。最坏情况下二叉树为一条链树的高度为 递归最深达到 层故最坏情况下空间复杂度为 。方法二中序遍历利用二叉搜索树的性质的推论中序遍历为单调递增序列。只需要掌握递归遍历即可。考虑保存整个中序遍历序列最后进行检查。C代码如下含测试用例#include stdio.h #include stdlib.h #include string.h #define MAX_SIZE 20011 #define false 0 #define true 1 typedef int bool; typedef struct { // MAX_SIZE为已定义常量 int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组 int ElemNum; // 实际占用的数组元素个数 }SqBiTree; void inorder(SqBiTree T, int i, int *a, int *j) { if (i T.ElemNum || T.SqBiTNode[i] -1) { // 越界或者为空结点 return; } inorder(T, 2 * i 1, a, j); a[(*j)] T.SqBiTNode[i]; inorder(T, 2 * i 2, a, j); } bool isValidBST(SqBiTree T){ int *a (int *)malloc(sizeof(int) * MAX_SIZE); int j 0; inorder(T, 0, a, j); for(int k 0; k j - 1; k) { if(a[k] a[k 1]) { return false; } } return true; } int main() { int a1[10] {40, 25, 60, -1, 30, -1, 80, -1, -1, 27}; SqBiTree bt1; memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode)); bt1.ElemNum 10; for (int i 0; i bt1.ElemNum; i) { bt1.SqBiTNode[i] a1[i]; } int ans1 isValidBST(bt1); if (ans1 true) { printf(T1 is a binary search tree\n); } else { printf(T1 is not a binary search tree\n); } int a2[11] {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35}; SqBiTree bt2; memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode)); bt2.ElemNum 11; for (int i 0; i bt2.ElemNum; i) { bt2.SqBiTNode[i] a2[i]; } int ans2 isValidBST(bt2); if (ans2 true) { printf(T2 is a binary search tree\n); } else { printf(T2 is not a binary search tree\n); } return 0; }复杂度分析时间复杂度 其中 为二叉树的结点个数。二叉树的每个结点最多被访问三次因此时间复杂度为 。空间复杂度 其中 为二叉树的结点个数。递归栈最深为 中序遍历数组大小为 因此需要额外的 的空间。42.10分现有 个数保存在一维数组 中需要查找 中最小的个数请回答下列问题。⑴ 设计一个完成上述查找任务的算法要求平均情况下的比较次数尽可能少简单描述其算法思想不需要程序实现。⑵ 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。解答本题考查外部排序。题目要求对有大量数据的数组进行排序暗示数组无法一次性全部读入内存需要使用外部排序思想。构造一个大小可容纳10个数的区域用于保存已经遍历的数据流中最小的10个数如果后面到来的数比这10个数中最大的数还要小则和这10个数中最大的数进行交换。方法一插入插入排序思想用 a[0:9] 用来保存数组M中最小的 10 个数。先将a[0:9]M[0:9]进行排序依次后面的数M[i]其中i10,11,…若M[i]a[9]则将M[i]插入到a[0:9]中最后 a[0:9] 存储的是数组M中最小的 10 个数。复杂度分析时间复杂度 每个数插入时间代价为 总计 个数总代价为 。空间复杂度 中间过程额外需要常数个辅助变量。方法二大根堆堆排序思想用 a[0:9] 用来保存数组M中最小的 10 个数。先将a[0:9]M[0:9]进行构建为大根堆依次后面的数M[i]其中i10,11,…若M[i]a[0]a[0]大根堆堆顶元素则将M[i]置换大根堆堆顶元素并调整堆。最后 a[0:9] 存储的是数组M中最小的 10 个数。复杂度分析时间复杂度 初始建堆代价为 后面每个数插入堆后调整的时间代价为 总计 个数总代价为 。空间复杂度 中间过程额外需要常数个辅助变量。