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

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

1、下列程序段的时间复杂度是（ ）。

A、O（n）

B、O（logn）

C、O（nlogn）

D、O（n2）

2、设p指向一个非空双向链表中的某个结点，将一个q所指新结点插入到该双向链表中， 使其成为p所指结点的前驱结点，能正确完成此要求的语句段是（ ）。

A、q->next=p; q->prior=p->prior; p->prior=q; p->prior->next=q;

B、p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;

C、q->prior=p->prior; q->next=p; p->prior->next=q; p->prior=q;

D、q->prior=p->next; q->next=p; p->prior->next=q;p->prior=q;

3、一个栈的入栈序列为1，2，3，… ， n，其出栈序列是P1，P2， P3， … ，Pn 。若P1=4，则P3可能取值的个数是多少？（ ）。

A、n-3

B、n-2

C、n-1

D、无法确定

4、二维数组SA中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，且采用行优先顺序存储，元素A [4][5]的起始地址为（ ）。

A、SA+141

B、SA+ 111

C、SA+135

D、SA+ 165

5、一棵度为4的树T中，若有10个度为4的结点，20个度为3的结点，1个度为2的结点， 12个度为1的结点，则树T的叶子结点个数是（ ）。

A、63

B、81

C、105

D、72

6、设森林F中有4棵树T1，T2，T3，T4，其结点个数分别为10、15、12、19，将森林F转换成一棵二叉树BT，BT的根结点R为T1上的结点，则R的左子树上的结点个数是（ ）。

A、9

B、10

C、19

D、27

7、设哈夫曼编码的长度不超过4，若己对两个字符编码为1和01，则最多还可对（ ）个字符编码。

A、2

B、3

C、4

D、7

8、下列四个序列中，哪一个是堆（ ）。

A、65，55，40，10，30，25，20，15

B、65，55，30，15，25，40，20，10

C、65，40，55，10，25，30，20，15

D、65，55，40，30，15，25，20，10

9、在含有33个结点的二叉排序树上，查找关键字为34的结点，以下（ ）是可能的关键字比较序列？

A、25，37，16，45，34

B、45，37，16，25，34

C、45，25，16，37，34

D、16，37，25，45，34

10、序列（5，3，12，9，4，2，6，8）是某排序方法第一趟后的结果，该排序算法可能是（ ）。

A、冒泡排序

B、堆排序

C、归并排序

D、简单选择排序

1、试题答案：A

试题解析：

本题考查基本概念-时间复杂度的计算。
当i=1时，m=0+1；当i=2时，m=0+1+2；当i=3时，m=0+1+2+3；设循环体执行Tn次，则m=1+2+3+…+Tn； 由等差数列的求和公式可知，m=1/2*Tn2+1/2*Tn；忽略常数1/2，m=Tn2+Tn。又因为Tn2级数大于Tn，忽略Tn， m=Tn2。 套入循环中，Tn2<n2； 即 Tn<n； 所以时间复杂度为n。故本题选A。

2、试题答案：C

试题解析：

本题考查双向链表的插入方法。
对于A，p->prior=q;应当在p->prior->next=q; 之后执行，否则p的前驱结点会发生丢失，因此A错误。B与A同理。C选项执行正确。能够完成插入。D选项第一步执行错误，q->prior=p->prior，因此D错误。故本题选C。

3、试题答案：B

试题解析：

本题考查栈的特性。
栈是限定只能在表的一端进行插入和删除操作的线性表。在表中允许插入和删除的一端称为“栈顶”，不允许插入和删除的一端称为“栈底”。根据该特性可知，P3不可以为4，不可以为1，其余值均可以取到。故本题选B。

4、试题答案：C

试题解析：

本题考查顺序存储结构。
本题的地址从A[0][0]开始存储且按照行优先顺序存储，因此A[4][5]之前有4行，且每行有10个元素，则第5行有5个元素，元素A[4][5]之前共有元素10*4+5=45。每个元素占3个字节，则一共占据的存储空间为45*3=135。起始地址为SA，则A[4][5]的起始地址为SA+A[4][5]。故本题选C。

5、试题答案：D

试题解析：

本题考查树的基本概念。
将树的出度为i的结点个数设为ni，则总结点为n=n0+n1+…+ni；结点的每一个出度连接一条边，所以边的个数e=1*n1+2*n2+…+i*ni； 又因为在树中，n=e+1；e为树的边数。所以上述式子可以改写为n0+n1+…+ni=1+1*n1+…+i*ni； n0=1+n2+……+（i-1）*ni；n0=2+2*20+3*10=72。故本题选D。

6、试题答案：A

试题解析：

本题考查森林与二叉树的转换。
森林转为二叉树的步骤如下：
（1）将每棵树转为二叉树；
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。因此，最后得到的二叉树的根节点即为第一棵二叉树的根节点，其余结点为二叉树的左孩子结点，其余所有树为二叉树的右孩子结点。故本题选A。

7、试题答案：C

试题解析：

本题考查哈夫曼树和哈夫曼编码。
在哈夫曼编码中，左分支为0，右分支为1；每个字母对应的结点都是叶子结点，每个结点的编码不会是其他结点的前缀。编码长度最大为4，则哈夫曼树的最大高度为5。因为已经存在编码为1的树，所以右子树只有一个结点，若想得到最多的字符编码，则该树的子结点最多，因此该哈夫曼树如图所示：

因此最多还有四个字符编码，分别为0000，0001，0010，0011。故本题选C。

8、试题答案：D

试题解析：

本题考查堆的构造。
将堆看成一个完全二叉树，则堆的所有非叶子结点的值均不大于（不小于）其左右孩子结点的值，且根结点为整棵二叉树中的最大值（最小值）。按照该思想，将ABCD的序列转化成完全二叉树，则只有D符合堆得基本概念。将A转化为完全二叉树并验证其是否符合堆的性质如下：

将B转化为完全二叉树并验证其是否符合堆的性质如下：

将C转化为完全二叉树并验证其是否符合堆的性质如下：

将D转化为完全二叉树并验证其是否符合堆的性质如下：

综上所述，故本题选D。

9、试题答案：B

试题解析：

本题考查二叉排序树的性质。
二叉排序树的性质为二叉排序树或者为空树，或者为具有如下特性的树：

（1）若它的左子树不为空，则左子树上的所有结点的值均小于根结点的值；

（2）若它的右子树不为空，则右子树上的所有结点的值均大于或等于根结点的值；

（3）其左右子树也分别为二叉排序树。
A的查找序列如下：

16比25小，不应当出现在右子树中。
B的查找序列如下：

符合规定，正确答案。
C的查找排序如下：

34和25比较，34比25大，因此下一步应当是比25大的树，16比25小，因此错误。
D的查找排序如下：

二叉排序的的左右子树也应当分别为二叉排序树，显然D中的右子树中，45不应该出现在37的左子树中。故本题选B。

10、试题答案：C

试题解析：

本题考查排序的对比。
冒泡排序、堆排序、简单选择排序第一趟排序之后，其最大值应该在末尾或者最开头，因此上述序列不符合冒泡排序的第一趟排序结果。而归并排序第一趟结果并无规律，因此上述排序排除A B D，只可能是C。故本题选C。