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