2022年408计算机学科专业基础考研真题答案及解析

考研希赛网 2023-07-07 浏览 6483 来源：希赛网

考研真题，是用来研究考试规律的。考生可通过真题，来确定自己的复习范围，来研究考试的重点、难点是哪些内容。希赛网为大家整理2022年408计算机学科专业基础考研真题答案及解析，供大家参考!

本文提供2022年408计算机学科专业基础考研真题答案及解析，以下为具体内容

1、下列程序段的时间复杂度是（）。Int sum=0;for（int i=1;i<n;i*=2） for（int j=0;j<i;j++） sum++;

A、 O（logn）

B、 O（n）

C、 O（nlogn）

D、 O（n2）

2、给定有限符号集S、in和out均为S中所有元素的任意排列，对于初始为空的栈ST，下列叙述中，正确的是（）。

A、若in是ST的入栈序列，则不能判断out是否为其可能的出栈序列。

B、若out是ST的出栈序列，则不能判断in是否为其可能的入栈序列。

C、若in是ST的入栈序列，out是对应in的出栈序列，则in与out一定不同。

D、若in是ST的入栈序列，out是对应in的出栈序列，则in与out可能互为倒序。

3、若结点p与q在二叉树T的中序遍历序列中相邻，且p在q之前，则下列p与q的关系中，不可能的是（）。I.q是p的双亲II.q是p的右孩子III.q是p的右兄弟IV.q是p的双亲的双亲

A、仅I

B、仅III

C、仅II、III

D、仅II、IV

4、若三叉树T中有244个结点（叶结点的高度为1），则T的高度至少是（）。

A、 8

B、 7

C、 6

D、 5

5、对任意给定的含n（n>2）个字符的有限集S，用二叉树表示S的哈夫曼编码集和定长编码集，分别得到二叉树T1和T2。下列叙述中，正确的是（）。

A、 T1与T2的结点数相同

B、 T1的高度大于T2的高度

C、出现频次不同的字符在T1中处于不同的层

D、出现频次不同的字符在T2中处于相同的层

6、对于无向图G=（V，E），下列选项中，正确的是（）。

A、当|V|>|E|时，G一定是连通的

B、当|V|<|E|时，G一定是连通的

C、当|V|=|E|-1时，G一定是不连通的

D、当|V|>|E|+1时，G一定是不连通的

7、下图是一个有10个活动的AOE网，时间余量最大的活动是（）。

A、 c

B、 g

C、 h

D、 j

8、在下图所示的5阶B树T中，删除关键字260之后需要进行必要的调整，得到新的B树T1。下列选项中，不可能是T1根结点中关键字序列的是（）。

A、 60，90，280

B、 60，90，350

C、 60，85，110，350

D、 60，90，110，350

1、试题答案：B

试题解析：

2、试题答案：D

试题解析：

【考点】本题考查栈的应用
【解析】本题的重点在于深刻理解栈的“后进先出”的特性。当已知栈的入栈序列时，可以得到有限个可能的出栈序列，因此A错误。同理，当已知栈的出栈序列时，可以得到有限个可能的入栈序列，因此B错误。若元素每次入栈之后即实行出栈操作，则可以实现入栈和出栈序列相同，因此C选项错误。若先将所有元素入栈，之后再将元素出栈，则可以实现入栈和出栈互为倒序，因此D正确。故本题选D。

3、试题答案：B

试题解析：

【考点】本题考查二叉树的遍历
【解析】中序遍历首先遍历左子树，再遍历根结点，最后遍历右子树。由于根结点在中间，因此若p和q互为兄弟结点，则p和q之间必然有根结点的值，必然不会相邻。因此III错误。而I、II、IV均有可能，画出其可能的结果如下：

4、试题答案：C

试题解析：

5、试题答案：D

试题解析：

6、试题答案：D

试题解析：

【考点】本题考查图的连通性概念
【解析】无向图的连通性指从图的任一顶点出发即可访问所有顶点。因此，若要满足连通性，无向图的边数E至少为V-1，此时V个顶点串联。当E<V-1时，该无向图一定不连通，因此C错误，D正确。若要保证无向图一定是连通的，则V-1个顶点构成一个完全图，再增加任意一条边连接第V个顶点。因此当E>（V-1）*（V-2）/2，因此A和B选项错误。故本题选D。

7、试题答案：B

试题解析：