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

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

1、已知程序如下：程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（  ）。

A、 main（）→ S（1） →S（0）

B、 S（0）→S（1）→ main（）

C、 main（）→S（0）→S（1）

D、 S（1）→S（0）→main（）

2、先序序列为a， b， c， d的不同二叉树的个数是（  ）。

A、 13

B、 14

C、 15

D、 16

3、下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是（  ）。

A、 24，10，5和24，10，7

B、 24，10，5和24，12，7

C、 24，10，10和24，14，11

D、 24，10，5和24，14，6

4、现有一棵无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（  ）。

A、 根结点的度一定为2

B、 树中最小元素一定是叶结点

C、 最后插入的元素一定是叶结点

D、 树中最大元素一定是无左子树

5、设有向图G=（V， E），顶点集V = {v0，v1，v2，v3}， 边集E= {<v0，v1>， <v0，v2>， <v0，v3>，<v1，v3>}。若从顶点v0开始对图进行深度优先遍历则可能得到的不同遍历序列个数是（  ）。

A、 2

B、 3

C、 4

D、 5

6、求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（Kruskal）算法第2次选中但不是普里姆（Prim）算法（从V4开始）第2次选中的边是（  ）。

A、 （V1，V3）

B、 （V1，V4）

C、 （V2，V3）

D、 （V3，V4）

7、下列选项中，不能构成折半查找中关键字比较序列的是（  ）。

A、 500， 200， 450， 180

B、 500， 450， 200， 180

C、 180， 500， 200， 450

D、 180， 200， 500， 450

8、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”（s[i]≠t[j]）时，i=j=5，下次开始匹配时，i和j的值分别是（  ）。

A、 i=1，j=0

B、 i=5，j= 0

C、 i=5，j=2

D、 i=6，j=2

1、试题答案：A

试题解析：

【考点】本题考查程序运行时栈的存储。
【解析】程序从main函数开始执行，之后执行S(1)调用函数S，因为1>0，因此在函数S内递归调用S(0)。程序运行时自栈底到栈顶保存的信息依次为main()→S(1) →S(0)，故本题选A。

2、试题答案：B

试题解析：

【考点】本题考查二叉树的遍历。
【解析】方法一：分析法。已知二叉树出的前序和中序序列，可以唯一确定一棵树，本题可以转换为求已知先序序列的二叉树可能的中序序列个数。二叉树的先序序列相当于栈的入栈，而中序序列相当于栈的出栈，本题可以转换为已知入栈序列求出栈序列的个数。由栈的性质可知，当有n个元素入栈时，其出栈序列的个数。带入n=4，求得出栈个数=14。
方法二：画图法。首先画出含3个结点的二叉树的形态如下：

当含有4个结点时，若根结点只有左子树，则上述五种结构连接到根结点的左边；若根结点只有右子树，则上述五种结构连接到根结点的右边。若根结点A有左右两棵子树B、C，则第四个结点有可以在B的左右或C的左右。因此4个结点的情况下树的形态一共有5+5+4=14。故本题选B。

3、试题答案：D

试题解析：

【考点】本题考查哈夫曼树的性质。
【解析】在哈夫曼树中，根结点的值为其左右子结点的值之和，且除叶子结点以外，其余结点均含有左右子树。对于A选项，根结点为24，24的子树为10，则以10为根结点的左右子树之和为10。即可能是5+5或3+7，不可能是5和7，24、10、5和24、10、7不可能属于同一棵哈夫曼树。因此A选项错误。对于B选项，24为根结点，其左右子树为10、12，显然10+12！=24，因此B选项错误。对于C选项，根结点为24，左右子结点为10、14，以10为根结点时，其左右子树的值应当均小于10，不可能出现24、10、10的序列，因此C选项错误。对于D选项，24为根结点，其左右子树分别为10、14，10+14=24符合。检查10，其子结点小于10，检查14，其子结点小于6，符合哈夫曼树的性质，故本题选D。

4、试题答案：D

试题解析：

【考点】本题考查平衡二叉树的性质。
【解析】平衡二叉树的本质是一棵二叉排序树。本题明确表明中序遍历可以得到降序序列。中序遍历为左
->根->右。因此左子结点值>=根结点值>右子结点值。对于A选项举出其反例，若该树含2个结点，则根的度为1，A选项错误。对于B选项，若树仅含有两个结点，根结点和右孩子结点，此时树中最小的结点是根结点，而根结点不是叶子结点，因此B选项错误。对于C选项，在二叉排序树中最后插入的元素一定是叶子结点，但平衡树中若插入结点后进行调整，调整后不一定是叶子结点。对于D选项树中最大的元素若存在根结点，则左子结点>=根结点，此时左子结点称为最大元素，树中最大元素无左子树。故本题选D。

5、试题答案：D

试题解析：

【考点】本题考查深度优先搜索。
【解析】根据有向图的边集，构造出图如下所示：

深度优先搜索的方法为从图中某顶点v出发，访问顶点v，依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问。若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。按照上述方法从v0出发，深度优先遍历的序列为：

v0->v1->v3->v2
v0->v2->v1->v3
v0->v2->v3->v1
v0->v3->v1->v2
v0->v3->v2->v1

根据上述分析，深度优先遍历序列共5个，故本题选D。

6、试题答案：C

试题解析：

【考点】本题考查最小生成树的两种算法。
【解析】构造最小生成树有两种算法，一种是kruskal算法，一种是Prim算法，kruskal算法主要针对边进行操作，其算法的时间复杂度为O(eloge)。Kruskal算法的基本思想为：首先构造一个只含n个顶点的森林，然后依照权值从小到大从连通网中选择边加入到森林中，并使得森林不产生回路，直至该森林成为一棵树为止。Prim算法的思想为首先选取图中任一顶点v作为生成树的根，之后往树中添加顶点w，w v之间必须有边，且该边的权值应在所有和v相连接的边中最小，之后在w v相连的顶点中添加顶点，保证边权值最小，重复上述过程，直至所有的顶点添加到树中。其主要是对顶点进行操作，时间复杂度为O(n2)。按照上述算法思想，kruskal算法是选择边的算法，第一次选的边必为（V1,V4），第二条边必从（V1,V3），（V2,V3），（V3,V4）中选择一条。Prim算法是选择顶点的算法，从V4出发，第一次选择（V1,V4），第二次从（V1,V3），（V3,V4）中选择一条，可能是克鲁斯卡（Kruskal） 算法第2次选中但不是普里姆（Prim）算法（从V4开始）第2次选中的边是（V2,V3），故本题选C。

7、试题答案：A

试题解析：

【考点】本题考查折半查找。
【解析】折半查找判定树的本质是二叉排序树，二叉排序树或者为空树，或者为具有如下特性的树：① 若它的左子树不为空，则左子树上的所有结点的值均小于根结点的值；② 若它的右子树不为空，则右子树上的所有结点的值均大于或等于根结点的值；③ 其左右子树也分别为二叉排序树。构造出A选项对应的折半查找路径如下：

检查上述各点，180在200的右子树上，但180<200，显然上述路径不符合二叉排序树的定义，因此A错误。
构造出B选项对应的折半查找路径如下：

检查上述各点,上述路径符合二叉排序树的定义，因此B正确。
构造出C选项对应的折半查找路径如下：

检查上述各点,上述路径符合二叉排序树的定义，因此C正确。
构造出D选项对应的折半查找路径如下：

检查上述各点,上述路径符合二叉排序树的定义，因此D正确。故本题选A。

8、试题答案：C

试题解析：

【考点】本题考查KMP算法。
【解析】首先给出模式串的next数组如下：

第一次匹配失败时i=j=5，对应的模式串的next数组为2,下次开始匹配时，i=5，j=2。故本题选C。