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