2022年数据结构考研真题答案及解析（四）

本文提供2022年数据结构考研真题答案及解析，以下为具体内容

1、下列（ ）的邻接矩阵是对称矩阵。

A、AOV网

B、AOE网

C、有向图

D、无向图

2、当输入非法错误时，一个“好”的算法会进行适当处理，而不会产生难以理解的输出结果。这称为算法的（ ）。

A、可读性

B、健壮性

C、正确性

D、有穷性

3、当字符序列F4_作为一个栈的输入时，输出长度为3的且可用作C语言标识符的序列有（ ）个。

A、4

B、5

C、3

D、6

4、若用一个大小为7的数组来实现循环队列，且当前rear和front的值分别为0和4，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。

A、2和6

B、6和2

C、5和2

D、2和5

5、用一个栈求下列后缀表达式的值，8 2 3 ^ / 2 3 * + 5 1 * -其中：+、-、*、/、^分别是加、减、乘、除、幂运算符，当扫描到第一个*时，栈顶部2个元素是（ ）。

A、6，1

B、5，7

C、3，2

D、1，5

6、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。

A、空或只有一个节点

B、高度等于其节点数

C、任一节点无左孩子

D、任一节点无右孩子

7、一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是（ ）。

A、不确定

B、0

C、1

D、2

8、（ ）占用的额外空间的空间复杂性为O(1)。

A、堆排序算法

B、归并排序算法

C、快速排序算法

D、以上答案都不对

9、在Huffman编码中，若编码长度只允许小于等于3，则除了已对两个字符编码为0和10外，还可以最多对（ ）个字符编码。

A、2

B、3

C、4

D、5

10、设一个稀疏矩阵有1000行850列，其中有800个非0元素。设每个整数占2B，数据值占4B，则用三元组表存储该矩阵时所需字节数是（ ）。

A、1600

B、3200

C、6400

D、9600

1、试题答案：D

试题解析：

2、试题答案：B

试题解析：

【考点】本题考查数据结构--绪论--算法和算法分析--算法概念--算法设计的要求。
【解析】算法的可读性由代码的编写方式和注释决定，与代码的逻辑无关，故选项A错误。算法的健壮性要考虑算法执行过程中的各种特殊情况，并予以处理，故选项B正确。算法的正确性和有穷性都建立在输人合法的情况下，故选项C、D错误。故本题选B。

3、试题答案：C

试题解析：

【考点】本题考查数据结构--栈和队列--栈--栈的基本概念--栈的基本操作。
【解析】
栈具有“后进先出”的特性，根据该特点“F4_”的所有可能的输出结果有五种，分别是① “F4_”，② “F_4”，③ “4F_”；④ “4_F”；⑤ “_4F”。C语言标识符具有这样的特点：① 标识符只能由数字、字母、下划线组成；② 标识符的第一个字符必须是字母或下划线；③ 标识符区分大小写。因此上述5种栈的输出序列中，符合条件的只有3种，故本题选C。

4、试题答案：D

试题解析：

【考点】本题考查数据结构--栈和队列--队列--队列的应用--循环队列--循环队列的基本操作。
【解析】
将顺序队列首尾相接成环状空间即为循环队列。在循环队列中，删除元素时头指针加1；增加元素时尾指针加1。本题中，当从队列中删除一个元素时，front由4->5，再加入两个元素后，rear由0->2，故本题选D。

5、试题答案：A

试题解析：

【考点】本题考查数据结构--栈和队列--栈--栈的应用--表达式的计值--后缀表达式的计值。
【解析】
首先，根据后缀表达式的计算规则，我们从左到右扫描表达式，并将每个操作数压入栈中，遇到运算符时，弹出栈顶的两个操作数进行运算，并将运算结果压入栈中，直到最后得到表达式的值。根据上述方法，我们依次进行下列操作：
① 将8压入栈中：[8]；
② 将2压入栈中：[8，2]；
③ 将3压入栈中：[8，2，3]；
④ 弹出栈顶的两个元素2和3，进行幂运算2^3=8，将运算结果8压入栈中：[8，8]；
⑤ 进行除法8/8=1，弹出栈顶的两个元素8和8，将运算结果1压入栈中：[1]；
⑥ 将2压入栈中：[1，2]；
⑦ 将3压入栈中：[1，2，3]；
⑧ 弹出栈顶的两个元素2和3，进行乘法2*3=6，将运算结果6压入栈中：[1，6]。故本题选A。

6、试题答案：B

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--遍历二叉树。
【解析】
先序遍历二叉树先访问根结点，再遍历左子树，最后遍历右子树。后序遍历二叉树先遍历左子树，再遍历右子树，最后访问根结点。对于A，若树为空或只有一个结点时，二叉树的先序序列和后序序列相同，不符合题干要求，因此A错误。对于B，若树的结构如图1所示，该树的先序序列为ABC，后序序列为CBA，符合题干要求。对于C，若树的结构如图2所示，该树的先序序列为ABC，后序序列为CBA，符合题干要求。对于D，若树的结构如图3所示，该树的先序序列为ABC，后序序列为CBA，符合题干要求。B的表述包含C和D的情况，故本题选B。

7、试题答案：D

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--线索二叉树--线索二叉树的性质。
【解析】
对于一棵前序线索化二叉树，结点的左指针要么指向左孩子，要么指向前驱结点；结点的右指针要么指向右孩子，要么指向后继结点。题干中的二叉树左子树为空，因此根结点无左孩子结点也无前驱结点，是空的链域；前序遍历的最后一个叶子结点的右指针既无右孩子也无后继结点。是空的链域，故本题选D。

8、试题答案：A

试题解析：

【考点】本题考查数据结构--排序--内部排序--内部排序算法的综合比较--辅助存储空间的比较。
【解析】
堆排序的辅助存储空间为O(1)，归并排序的辅助存储空间为O(n)，快速排序的辅助存储空间为O(logn)。故本题选A。

9、试题答案：A

试题解析：

【考点】本题考查数据结构--树与二叉树--树与二叉树的应用--哈/赫夫曼树及其编码--哈/赫夫曼编码。
【解析】
哈夫曼编码具有前缀性，在本题中编码长度最大为3，则还有110、111两种编码，故本题选A。

10、试题答案：C

试题解析：

【考点】本题考查数据结构--数组与广义表--矩阵的压缩存储--稀疏矩阵的压缩存储。
【解析】
该三元组表需要存储800个非0元素所在的行数、列数、非0元素的值，一共有800个数据值，1600个整数，所需要的字节数为800*4B+1600*2B=6400，故本题选C。