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

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

1、设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是（ ）。

A、

B、

C、

D、

2、若将一棵树 T 转化为对应的二叉树 BT，则下列对 BT 的遍历中，其遍历序列与 T 的后根遍历序列相同的是（ ）。

A、 先序遍历

B、 中序遍历

C、 后序遍历

D、 按层遍历

3、对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 n 的值是（ ）。

A、 56

B、 57

C、 58

D、 60

4、在任意一棵非空平衡二叉树（AVL 树）T1 中，删除某结点 v 之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3。下列关于T1与T3的叙述中，正确的是（ ）。I. 若v是T1的叶结点，则T1与T3可能不相同II. 若v不是T1的叶结点，则T1与T3一定不相同III. 若v不是T1的叶结点，则T1与T3一定相同

A、 仅I

B、 仅II

C、 仅I、II

D、 仅I、III

5、下图所示的 AOE 网表示一项包含 8 个活动的工程。活动 d 的最早开始时间和最迟开始时间分别是（ ）。

A、 3和7

B、 12和12

C、 12和14

D、 15和15

6、用有向无环图描述表达式(x+ y)((x+y)/x)，需要的顶点个数至少是（ ）。

A、 5

B、 6

C、 8

D、 9

7、选择一个排序算法时，除算法的时空效率，下列因素中，还需要考虑的是（ ）。I. 数据的规模II. 数据的存储方式 III. 算法的稳定性 IV. 数据的初始状态

A、 仅III

B、 仅I、II

C、 仅II、III、IV

D、 I、II、III、IV

8、现有长度为11且初始为空的散列表HT，散列函数是H(key)= key % 7，采用线性探查(线性探测再散列)法解决冲突。将关键字序列87，40，30，6，11，22，98，20依次插入HT后，HT查找失败的平均查找长度是（ ）。

A、 4

B、 5.25

C、 6

D、 6.29

9、设主串T = "abaabaabcabaabc"，模式串S = "abaabc"，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（ ）。

A、 9

B、 10

C、 12

D、 15

10、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是（ ）。

A、 5，2，16，12，28，60，32，72

B、 2，16，5，28，12，60，32，72

C、 2，12，16，5，28，32，72，60

D、 5，2，12，28，16，32，72，60