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

1、试题答案：B

试题解析：

2、试题答案：B

试题解析：

【考点】本题考查树与二叉树的转换
【解析】（1） 将树转换为二叉树的步骤为：① 将树的根结点直接作为二叉树的根结点；② 将树的根节点的第一个子节点作为二叉树根节点的左指针，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右指针。③ 树中的剩余节点按照上一步的方式（左孩子，右兄弟），依序添加到二叉树中。直到树中所有的节点都在二叉树中。依照这种方法转换后的二叉树无右子树。举例如下：

（2）树的遍历与其对应的二叉树的遍历：
① 树的先根遍历对应二叉树的先序遍历；
② 树的后根遍历对应二叉树的中序遍历。故本题选B。

3、试题答案：C

试题解析：

【考点】本题考查哈夫曼树的性质
【解析】根据哈夫曼树的性质，有n个编码则有n个叶子结点。哈夫曼树是一棵二叉树，因此度为0的结点即为度为2的结点加1。哈夫曼树中没有度为1的结点，度为0的结点数为权值结点，因此总的结点数为n+n-1=2*n-1。带入题干的值，2*n-1=115，解得58。故本题选C。

4、试题答案：A

试题解析：

【考点】本题考查平衡树的插入和删除
【解析】对于I，若删除叶结点之后引起左右分支的不平衡，此时树会调整，在插入节点后形成叶子结点，此时T1与T3可能不同；若T1删除v后不引起调整，则T1与T3相同，因此I正确。对于II，v是非叶结点，则删除后引起树的调整，再插入v后可能不平衡再次调整，经过两次调整，树T1与树T3可能相同，因此II错误。同理，经过两次调整，树T1与树T3可能不同，因此III错误。故本题选A。

5、试题答案：C

试题解析：

【考点】本题考查AOE网求关键路径
【解析】AOE网指在一个带权有向图中，用顶点代表事件，用有向边表示活动，边上的权值表示活动的持续时间。事件的最早时间的求法：从前往后，前驱节点到当前结点所需时间，取最大值。事件的最晚时间的求法：从后往前，后继结点的最迟发生时间-边权值，取最小值。结束结点的最早发生时间和最晚发生时间相同。画出事件的最早发生时间和最晚发生时间如下表1所示：

活动的最早开始时间求解方法为：等于当前边起始结点的最早发生时间。活动的最晚开始时间求解方法：等于当前边指向结点的最迟发生时间-当前边的权值。画出活动的最早开始时间和最晚开始时间如下表2所示：

从表2可知活动 d 的最早开始时间和最迟开始时间分别是12、14，故本题选C。

6、试题答案：A

试题解析：

【考点】本题考查图的应用
【解析】分析表达式，出现的运算数为x、y，出现的运算符为+、*、/，将上述表达式转换为有向二叉树，其树结构如下所示：

将二叉树去掉重复结点，转化为有向图后的图结构如下所示：

根据上述图结构，分析可知至少需要5个顶点。故本题选A。

7、试题答案：D

试题解析：

8、试题答案：C

试题解析：

【考点】本题考查散列表失败查找的平均查找长度
【解析】根据散列法计算关键字存放地址的过程如下所示：
H(87)%7=3
H(40)%7=5
H(30)%7=2
H(6)%7=6
H(11)%7=4
H(22)%7=1
H(98)%7=0
H(20)%7=6，冲突。0~6已有关键字，因此存放在add(7)中。

根据散列函数是H(key)= key % 7，仅有add(0)~add(6)存在失败查找的情况。当地址为0时，查找到最近的空白地址需要比较9次，因此失败查找长度为9，以此类推，将地址、关键字以及失败查找次数三者的相对应关系展示在表1中。
根据表1，平均失败查找长度=（9+8+7+6+5+4+3）/7=6。故本题选C。

9、试题答案：B

试题解析：

【考点】本题考查KMP算法的应用
【解析】KMP算法是一种升级的暴力匹配算法。首先对模式串求next数组如下：

根据KMP算法，模式串与主串第一趟比较时，0至4号位均匹配成功，到模式串和字符串的5号位时发生不匹配。此时next=2，第二趟比较从模式串的2号位和主串的5号位开始进行比较，模式串的2号位至5号位分别和主串的5号位至8号位匹配成功。第一趟比较6次，第二趟比较4次，一共比较次数为10，故本题选B。

10、试题答案：D

试题解析：

【考点】本题考查快速排序的应用
【解析】根据快速排序的基本思想，快速排序的每一趟结果使得比基准小的元素位于基准一侧，比基准大的元素位于基准的另一侧。因此第二趟快速排序后，会有两个或三个基准值（若第一趟排序的基准值为最大值或最小值，则第二趟排序后只有两个值是基准值；否则有3个），其前后元素具有上述大小关系。逐个选项进行分析，A选项中28、72符合基准值的特性且72为极值，因此排除A。B选项中2、72符合基准值特性，且含极值，排除B。C选项中2、28、32符合，因此排除C。D选项中12、32符合，但不包含极值，因此D错误。故本题选D。