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