目录
前言
一、 选择题（本大题共 15小题，每小题 2分，共 30分）
1、当输入非法错误时一个“好”的算法会进行适当处理而不会产生难以理解的输出结果。这称为算法的（）。A可读性 B.健壮性 C.正确性 D.有穷性
2、当字符序列F4_作为一个栈的输入时，输出长度为3的且可用作C语言标识符的序列有（）个。A.4 B.5 C.3 D.6
3、若用一个大小为7的数组来实现循环队列，且当前rear和front的值分别为0和4，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。A.2和6 B.6和2 C.5和2 D.2和5
4、用一个栈求下列后缀表达式的值8 2 3 ^ / 2 3 * + 5 1 * -，其中：+、-、*、/、^分别是加、减、乘、除、幂运算符，当扫描到第一个*时，栈顶部2个元素是（）。A. 6, 1 B. 5, 7 C. 3, 2 D. 1, 5
5、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A.空或只有一个节点 B.高度等于其节点数C.任一节点无左孩子 D.任一节点无右孩子
6、一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是（）。A.不确定 B.0 C.1 D.2
7、( )占用的额外空间的空间复杂性为O(1)。A.堆排序算法 B.归并排序算法C.快速排序算法 D.以上答案都不对
这里也把十种排序的时间、空间复杂度放后面
8、在Huffman编码中，若编码长度只允许小于等于3，则除了已对两个字符编码为0和10外，还可以最多对（）个字符编码。A.2 B.3 C.4 D.5
9、设一个稀疏矩阵有1000行850列，其中有800个非0元素。设每个整数占2B，数据值占4B，则用三元组表存储该矩阵时所需字节数是（ ）。A.1600 B.3200 C.6400 D.9600
10、用于求无向图的所有连通分量的算法是（）。A.广度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径
11、若需在O(nlog2(n))的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序 B.堆排序 C.归并排序 D.直接插入排序
12、下列（）的邻接矩阵是对称矩阵。A.AOV网 B.AOE网 C.有向图 D.无向图
13、将元素71、65、84、69、67、83逐个插入空的二叉排序树(BST)中，最低层的元素为（）。A.65 B.67 C.69 D.83
14、具有12个关键字的有序表，折半查找的平均查找长度为（）。A.3.1 B.4 C.2.5 D.5
15、若在一棵m阶B树的结点中插入新关键码后该结点必须分裂为两个结点，那么在插入前结点的关键码数应为（）。A.m B.m-1 C.m+1 D.m-2
整个题目的解析过程算是我个人的思考思路，而不是正规的解题思路
1、当输入非法错误时一个“好”的算法会进行适当处理而不会产生难以理解的输出结果。这称为算法的（）。
A可读性 B.健壮性 C.正确性 D.有穷性
解析：从字面去理解的话，就马上能排除A、C、D（只要你学过数据结构的话）
对于 A. 可读性： 可读性指的是算法或代码的清晰度和易于理解的程度。它关注的是算法的表达方式，而不是算法如何处理非法或异常输入的能力。
对于C选项：正确性指的是算法能够按照预期正确地执行其设计的任务，并且对于所有合法的输入都能产生正确的输出。它不涉及算法如何处理非法输入，而是关注算法在正常情况下的执行结果。简单来说就是反映出输入与输出的关系 ，跟处理没关系
对于D：是指算法必须在有限的步骤内完成，不会无限循环。这是算法的基本属性之一，确保算法能够终止，但它并不涉及算法如何处理非法输入或错误情况。
2、当字符序列F4_作为一个栈的输入时，输出长度为3的且可用作C语言标识符的序列有（）个。
A.4 B.5 C.3 D.6
解析：首先，我们要知道能作为C的标识符的话，不能是数字开头，_和F都可以；其次，要注意栈这种数据结构的特性——先进后出。
因此，列举出来就有：F4_ 、F_4 、 _F4。
值得注意的是，是不存在_4F这种情况的，我不过多赘述。所以答案选C。
3、若用一个大小为7的数组来实现循环队列，且当前rear和front的值分别为0和4，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。
A.2和6 B.6和2 C.5和2 D.2和5
解析：首先要知道循环队列作为一种特殊的数据结构，也就是首尾相连，当元素满的时候，应该满足（rear+1）%MAXSIZE == front；此时题目给出的rear值是0，说明此时里面的空位还有3个；先删除一个，front++，为5，加入两个元素的话，rear+=2，为2；（不存在溢出，我前面分析还多想了），所以答案应该是选D
PS：卧槽好险，一开始选的C，把rear和front看反了，对不上答案的时候真的是呼吸一顿，吓死个人。一定多看两遍题！！！
4、用一个栈求下列后缀表达式的值8 2 3 ^ / 2 3 * + 5 1 * -，其中：+、-、*、/、^分别是加、减、乘、除、幂运算符，当扫描到第一个*时，栈顶部2个元素是（）。
A. 6, 1 B. 5, 7 C. 3, 2 D. 1, 5
解析：这道题我一开始都没看懂题意，没懂是在做弹栈操作还是入栈。看了答案才反推出来的：
一开始也入栈8、2、3，遇到了^，弹出3和2，然后又压入一个8，遇到/，弹出两个8，压入一个1，然后又压入2、3，紧接着就是遇到第一个*，此时的栈顶的两个元素就是3和2（从上往下看）。答案选C
5、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A.空或只有一个节点 B.高度等于其节点数
C.任一节点无左孩子 D.任一节点无右孩子
解析：这里是给出了二叉树的两个序列来让你构造二叉树，然后它说的是前序和后序是相反的，前序是中左右，后序是左右中。我只能自己随机假设一个了，
这样的话C就不符合了。答案选B
6、一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是（）。
A.不确定 B.0 C.1 D.2
解析：左子树为空的二叉树，首先，一个前序搜索树应该是这种条件：每个结点的左链域和右链域要么指向其前驱或后继，要么为空
然后才是题目的没有左子树， 根节点的左子树为空，所以它的左指针会被线索化指向它的前驱，但是在这个树中没有前驱，因此根节点的左指针会是一个空链域，第二个地方则是最后的一个节点，是没有右子树的，所以它的右指针也会指向空，类似这样：
所以答案选D，2个
7、( )占用的额外空间的空间复杂性为O(1)。
A.堆排序算法 B.归并排序算法
C.快速排序算法 D.以上答案都不对
解析：答案选A，这几个排序算法的时间复杂度和空间复杂度都是尝试死记的，至于空间复杂性，你就是看它有没有在原本的数组的前提下又创建新的的内存即可了，那显然，选C了，堆排并没有占用额外的内容
这里也把十种排序的时间、空间复杂度放后面
-
冒泡排序（Bubble Sort）
- 时间复杂度：最佳情况O(n)，平均情况O(n^2)，最坏情况O(n^2)
- 空间复杂度：O(1)
-
选择排序（Selection Sort）
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
-
插入排序（Insertion Sort）
- 时间复杂度：最佳情况O(n)，平均情况O(n^2)，最坏情况O(n^2)
- 空间复杂度：O(1)
-
希尔排序（Shell Sort）
- 时间复杂度：O(n log n) 到 O(n^2)，取决于间隔序列
- 空间复杂度：O(1)
-
归并排序（Merge Sort）
- 时间复杂度：O(n log n)
- 空间复杂度：O(n)
-
快速排序（Quick Sort）
- 时间复杂度：最佳情况O(n log n)，平均情况O(n log n)，最坏情况O(n^2)
- 空间复杂度：O(log n)（递归栈空间）
-
堆排序（Heap Sort）
- 时间复杂度：O(n log n)
- 空间复杂度：O(1)
-
计数排序（Counting Sort）
- 时间复杂度：O(n + k)，k是输入的数值范围
- 空间复杂度：O(n + k)
-
桶排序（Bucket Sort）
- 时间复杂度：O(n + k)，k是桶的数量
- 空间复杂度：O(n + k)
-
基数排序（Radix Sort）
- 时间复杂度：O(nk)，k是最大数字的位数
- 空间复杂度：O(n + b)，b是桶的数量
8、在Huffman编码中，若编码长度只允许小于等于3，则除了已对两个字符编码为0和10外，还可以最多对（）个字符编码。
A.2 B.3 C.4 D.5
解析：哈夫曼编码下的树 ，小于等于3的长度的话，左子树为0，右子树为1，0就是左边第一个节点，10就是先右再左，那现在就还剩下111、110两个情况（左边已经不能再出现了）。答案选A
9、设一个稀疏矩阵有1000行850列，其中有800个非0元素。设每个整数占2B，数据值占4B，则用三元组表存储该矩阵时所需字节数是（ ）。
A.1600 B.3200 C.6400 D.9600
解析：没做过这种题，先看了答案 ，选C，每一个数都会占2+2+4=8个字节，800个那就是800*8=6400，确实是C，对上了
（要是考试是给答案让我反推解答过程我会不会要更擅长些）
10、用于求无向图的所有连通分量的算法是（）。
A.广度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径
解析：无向图求连通，连通分量是指图中最大的连通子图。所以要找到所有连通的图，只有A是把每个连通的节点都走了一遍，这里如果选项里面有深度优先遍历，我感觉也是满足正确答案的。
11、若需在O(nlog2(n))的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序 B.堆排序 C.归并排序 D.直接插入排序
解析：前面也给出了几个排序的时间复杂度，由于要求稳定，所以快排就排除了，直接插入排序是O(n^2)，另外堆排序是O(nlog(n))，所以答案是选C
12、下列（）的邻接矩阵是对称矩阵。
A.AOV网 B.AOE网 C.有向图 D.无向图
解析：对称矩阵的本质就是一定要无向图， AOV和AOE指的也是有向图，只不过比较特殊，AOV不允许存在回路，那就一定不可能选它，AOE我有点讲不明白，但是也不能是它，总而言之答案就是D
13、将元素71、65、84、69、67、83逐个插入空的二叉排序树(BST)中，最低层的元素为（）。
A.65 B.67 C.69 D.83
解析： 构建整个树，
所以答案选B
14、具有12个关键字的有序表，折半查找的平均查找长度为（）。
A.3.1 B.4 C.2.5 D.5
解析：做不来
从牛客搜了一下，看完评论懂了。
链接：具有12个关键字的有序表,折半查找的平均查找长度()__牛客网
假如数组{1,2,3,4,5,6,7,8,9,10,11,12}，先找到中间位置后分两半，{1,2,3,4,5}{6}{7,8,9,10,11,12},然后再把{1,2,3,4,5}和{7,8,9,10,11,12 }做同样操作，继续找到中间位置划分，最终求平均查找长度就是求成功查到的平均长度：(1+2*2+4*3+5*4)/12 = 37/12 = 3.1
15、若在一棵m阶B树的结点中插入新关键码后该结点必须分裂为两个结点，那么在插入前结点的关键码数应为（）。
A.m B.m-1 C.m+1 D.m-2
解析： 没做过这种题型，有点大问题，在站内搜了一遍，得到了下面的定义，确实是第一次接触
B-树
B-树定义：一种平衡的多路查找树。用作索引组织文件，可减少访问外存次数，提高访问速度、减少时间。一棵m阶B-树或为空树，或满足下列特性：
1、树中每个结点至多有m个子树；(结点中的关键字个数最多m-1)
2、若根结点不是叶子结点，至少有两棵子树(根至少有一个关键字)
3、除根结点外，其余非叶子结点至少有m/2（下取整）棵子树。(比关键字个数多一个)
4.关键字的个数，范围是： m/2(下取整)-1≤n≤m-1
5、所有的叶子结点都出现在同一层上，不带信息（可看成是外部结点或查找失败的结点，并不存在）
6.节点的表示：（n,A0,K1, A1,K2, A2, ……… Kn, An），n：关键字的个数，A：指针，K：关键字
————————————————
转载请注明出处
原文链接：https://blog.csdn.net/i6223671/article/details/86761107