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、简单选择排序