注：本套试卷由强连通计算机考研完成解析，但难免有疏漏，如果发现错误请及时与我们反馈。
勘误：对微信公众号“强连通计算机考研”回复“重邮802勘误”。
2022年答案 一、 选择题（本大题共 15小题，每小题 2分，共 30分）
三、综合应用题（本大题共7小题，共60分） 
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(nlog 2 n)O(nlog_2 n)O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 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
二、填空题（本大题共10小题，每小题3分，共30分）16、对于具有144个记录的文件，若采用分块查找法，且每块长度为8，采用顺序查找确定所在的块，则平均查找长度为（）。 17、The seven elements A, B, C, D, E, F and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times and each element is inserted into a queue. Two elements are deleted from the queue and pushed back onto the stack. Now, one element is popped from the stack. The popped item is ( ). 18、有n个字符的字符串的非空子串个数最多有（ ）个。 19、用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为（ ）。 20、由3个结点可以构造出（ ）种不同的二叉树。 21、若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有（ ）棵树。 22、对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为（ ）。 23、（ ）是哈希表的一个重要参数，它反映哈希表的装满程度。 24、硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂度为n 2 n^2n2的算法，若用ABC公司的计算机能在1小时内解输入规模为n的问题，那么用XYZ公司的计算机在1小时内能解输入规模为（ ）的问题。 25、表达式A/B+D$E+F/H中，运算符的优先级由高到低依次为+，/，$，均右结合，则相应的后缀式是（ ）。
三、综合应用题（本大题共7小题，共60分）26、(5分）阅读代码，函数print()接收二叉查找树/二叉排序树(BST)的根和一个正整数k作为参数。请：
// a BST nodestruct node {int data;struct node *left, *right;};int count = 0;void print(struct node *root, int k){if (root != NULL && count right, k);count++;if (count == k)printf("%d ", root->data);print(root->left, k);}}(1) 简述该代码的功能 (2) print(root, 3)的输出是什么?其中root表示下图BST树的根。 
27、(5分)有一段代码：
int count = 0;for (int i = 0; i