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

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

1、已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则“最坏情况”下的时间复杂度是（  ）。

A、 O（n）

B、 O（m*n）

C、 O（min（m，n））

D、 O（max（m，n））

2、一个栈的入栈序列为1，2，3… n，其出栈序列是p1，p2，p3...pn。若p2=3，则p3可能取值的个数是（  ）。

A、 n-3

B、 n-2

C、 n-1

D、 无法确定

3、若将关键字1， 2， 3， 4， 5， 6， 7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是（  ）。

A、 0

B、 1

C、 2

D、 3

4、已知三叉树T中6个叶结点的权分别是2，3， 4，5， 6， 7， T的带权（外部）路径长度最小是（  ）。

A、 27

B、 46

C、 54

D、 56

5、若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是（  ）。

A、 X的父结点

B、 以Y为根的子树的最左下结点

C、 X的左兄弟结点Y

D、 以Y为根的子树的最右下结点

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

A、 仅I、III

B、 仅I、IV

C、 仅II、III

D、 仅II、IV

7、设图的邻接矩阵A如下所示。各顶点的度依次是：

A、 1，2，1，2

B、 2，2，1，1

C、 3，4，2，3

D、 4，4，2，2

8、若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（  ）。

A、 h，c，a，b，d，e，g，f

B、 e，a，f，g，b，h，c，d

C、 d，b，c，a，h，e，f，g

D、 a，b，c，d，h，e，f，g

9、下列AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（  ）。

A、 c和e

B、 d和e

C、 f和d

D、 f和h

10、在一株高度为2的5阶B树中，所含关键字的个数最少是（  ）。

A、 5

B、 7

C、 8

D、 14

1、试题答案：D

试题解析：

【考点】本题考查合并链表的时间复杂度。
【解析】两个升序链表A、B进行合并时，两两比较表中的元素，遍历链表A和B，若B中的值小于A中当前元素的值，则使用头插法将B中的结点插入到A当前结点之前。在最坏情况下，两个链表中的元素需要依次进行比较，直到遍历完A、B两个链表，此时时间复杂度为O（m+n），时间复杂度的加法运算规则为：加法规则：T（n，m） = T1（n） + T2（n） = O （max （ f（n），g（m） ）。因此本题最终的时间复杂度为O（max（m，n）），故本题选D。

2、试题答案：C

试题解析：

【考点】本题考查栈的特性。
【解析】栈具有“后进先出”的特性。若p2=3，则证明1、2已经入栈。若1入栈，1出栈，2入栈，3入栈，3出栈，2出栈，此时p3=2；若1入栈，2入栈，2出栈，3入栈，3出栈，1出栈，此时p3=1；若1入栈，1出栈，2入栈，3入栈，3出栈，4入栈，4出栈，则p3=4；若1入栈，1出栈，2入栈，3入栈，3出栈，4入栈，5入栈，5出栈，则p3=5；由此类推，p3=6、7……n。因此，p3除了3以外，其余值均有可能取到，故本题选C。

3、试题答案：D

试题解析：

【考点】本题考查平衡二叉树的构造。
【解析】根据关键字序列，画出构造平衡二叉树的过程如下：

图中最后一棵二叉树即为最终构造的平衡二叉树。由于分支结点为非叶子结点，因此T中平衡因子为0的分支结点分别为4、2、6，故本题选D。

4、试题答案：B

试题解析：

【考点】本题考查哈夫曼树的带权路径。
【解析】本题要求带权路径最小，则想到构造一棵哈夫曼树。为了构造哈夫曼树形式的三叉树，需要添加权值为0的叶子结点，该叶子结点不影响最终权值的计算，由此构造出哈夫曼树形式的三叉树如下所示：

5、试题答案：A

试题解析：

【考点】本题考查后序线索二叉树
【解析】根据题干构造一棵二叉树如下图所示：

该树的后序遍历序列为YXZ，X在后序线索二叉树中其右线索指向Z，即X的父结点，故本题选A。

6、试题答案：C

试题解析：

【考点】本题考查二叉排序树的插入和删除。
【解析】二叉排序树的插入：当二叉排序树中不存在关键字给定的结点时再进行插入，新插入的结点一定是一个新添加的叶子结点，并且是查找不成功路径上访问的最后一个结点的左孩子或者右孩子。二叉排序树的删除：若删除叶子结点，直接删除；若删除带一个子树的结点，删除后子树挪动；若删除带有两个子树的结点，则将待删除节点左子树的最右结点或右子树的最左结点放在待删除的位置，之后调整二叉排序树。因此，在二叉排序树中删除叶结点，则直接删除，再插入该结点，也会是叶子结点。因此，若v是T1的叶结点，则T1与T3相同。若删除非叶子结点，则会引起树的调整，调整后插入结点为叶子结点，若v不是T1的叶结点，则T1与T3不同，故本题选C。

7、试题答案：C

试题解析：

【考点】本题考查图的邻接矩阵。
【解析】矩阵A为非对称矩阵，则该图为有向图。矩阵中的非零元素A[i][j]代表从顶点i到顶点j的存在一条有向弧。因此，在有向图的邻接矩阵中第i行非零元素个数为Vi的出度，第i列非零元素个数为Vi的入度。第i行非零元素个数+第i列非零元素的个数=顶点i的度。故本题选C。

8、试题答案：D

试题解析：

【考点】本题考查广度优先遍历。
【解析】广度优先遍历的方法为从某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若图中仍有未被访问的顶点，从该顶点出发重复上述过程。根据上述思想检验各选项，A、B、C均符合，而D选项混淆了广度优先遍历和深度优先遍历，故本题选D。

9、试题答案：C

试题解析：

【考点】本题考查关键路径。
【解析】AOE网指在一个带权有向图中，用顶点代表事件，用有向边表示活动，边上的权值表示活动的持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫做关键路径。利用关键路径算法可以求出上图中的关键路径有三条，分别为（b，d，c，g），（b，d，e，h），（b，f，h）。只有在关键路径上的活动加快才能使整个活动加快。因此选项中的活动必须包含在三个关键路径中。A选项不在（b，f，h），B选项不在（b，f，h），D 选项不在（b，d，c，g），故本题选C。

10、试题答案：A

试题解析：

【考点】本题考查B树的性质。
【解析】一棵m阶的B树或者为空树，或者具有这样的特性：（1）树中每个结点至多有m棵子树；（2）除根结点以外的所有非叶子结点至少有m/2向上取整棵子树，根结点若非叶子结点，则至少含有两棵子树。所有非终端结点（终端结点即为叶子结点，其关键字个数为0）中包含关键字的个数范围为[ m/2取上界-1，m-1]。因此，5个B树非终端结点的关键字范围是[2，4]，因此当根结点关键字达到5时，会引起根结点分裂，此时树的高度为2，因此高度为2的5阶B树至少有5个关键字。故本题选A。