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

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

1、若栈S1中保存整数，栈S2中保存运算符，函数F( )依次执行下述各步操作：(1) 从S1中依次弹出两个操作数a和b；(2) 从S2中弹出一个运算符op；(3) 执行相应的运算b op a；(4) 将运算结果压人S1中。假定S1中的操作数依次是5,8,3,2 (2在栈顶)，S2 中的运算符依次是*,-,+ (+在栈顶)。调用3次F( )后，S1栈顶保存的值是（ ）。

A、 -15

B、 15

C、 -20

D、 20

2、现有队列Q与栈S，初始时Q中的元素依次是1，2，3，4，5，6 (1在队头)，S为空。若仅允许下列3种操作：①出队并输出出队元素；②出队并将出队元素入栈；③出栈并输出出栈元素，则不能得到的输出序列是（ ）。

A、 1，2，5，6，4，3

B、 2，3，4，5，6，1

C、 3，4，5，6，1，2

D、 6，5，4，3，2，1

3、设有一个12x12的对称矩阵M，将其上三角部分的元素mi，j (1<=i<=j<=12) 按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是（ ）。

A、 50

B、 51

C、 55

D、 66

4、设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是（ ）。

A、

B、

C、

D、

5、已知字符集{a， b，c，d，e，f}， 若各字符出现的次数分别为6，3， 8，2， 10， 4，则对应字符集中各字符的哈夫曼编码可能是（ ）。

A、 00， 1011， 01， 1010， 11， 100

B、 00， 100， 110， 000， 0010， 01

C、 10， 1011， 11， 0011， 00， 010

D、 0011， 10， 11， 0010， 01， 000

6、已知二叉排序树如下图所示，元素之间应满足的大小关系是（ ）。

A、 x1<x2<x5

B、 x1<x4<x5

C、 x3<x5<x4

D、 x4<x3<x5

7、下列选项中，不是如下有向图的拓扑序列的是（ ）。

A、 1，5，2，3，6，4

B、 5，1，2，6，3，4

C、 5，1，2，3，6，4

D、 5，2，1，6，3，4

8、高度为5的3阶B树含有的关键字个数至少是（ ）。

A、 15

B、 31

C、 62

D、 242

1、试题答案：B

试题解析：

【考点】本题考查栈的基本操作
【解析】根据题干，给出各步骤操作如下表所示：

根据上表，S1栈顶元素为15，故本题选B。

2、试题答案：C

试题解析：

【考点】本题考查队列和栈的基本操作
【解析】对选项进行逐个分析。对于A，1出队并输出，2出队并输出，3出队并入栈，4出队并入栈，5出队并输出，6出队并输出，4出栈并输出，3出栈并输出，因此A选项正确。对于B，1出队并入栈，2、3、4、5、6出队并输出，1出栈并输出，因此B选项正确。对于C，1、2出队并入栈，4、5、6出队并输出，2出栈并输出、1出栈并输出。栈中元素输出遵从“先进后出”的特性，因此2比1先输出，因此C选项错误。对于D，1、2、3、4、5、6出队并入栈，接着6、5、4、3、2、1出栈并输出，因此D选项正确。故本题选C。

3、试题答案：A

试题解析：

【考点】本题考查三角矩阵的存储
【解析】按照题意画出12阶上三角矩阵（实际做题中仅画前6行即可）如下，上三角部分用1代表，并将m6,6之前的元素用红色标出。

从图中可以看出，m6,6之前的元素个数为12+11+10+9+8=50。因此m6,6是第51个元素。将这51个元素存放在一位数组中，数组的下角标从0开始，因此第51个元素的下角标为50。故本题选A。

4、试题答案：A

试题解析：

5、试题答案：A

试题解析：

6、试题答案：C

试题解析：

【考点】本题考查二叉排序树的性质
【解析】二叉排序树的基本概念为二叉排序树或者为空树，或者为具有如下特性的树：① 若它的左子树不为空，则左子树上的所有结点的值均小于根结点的值；② 若它的右子树不为空，则右子树上的所有结点的值均大于或等于根结点的值；③ 其左右子树也分别为二叉排序树。根据该性质可知，根结点左子树的值小于根结点的值，右子树的值大于（有些情况可以等于，本题不考虑等于的情况）根结点的值。逐个选项进行分析，x1<x5<x2，因此A错误。x1<x5<x4，因此B错误。x3<x5<x4，因此C正确、D错误。故本题选C。

7、试题答案：D

试题解析：

【考点】本题考查有向图的拓扑排序
【解析】拓扑排序的针对有向图的排序方法，求拓扑排序的方法为：初始时拓扑序列为空；任选一个入度为0的点放入拓扑序列中，同时删除该顶点以及从该顶点出发的弧；重复上述操作直至不存在入度为0的顶点。根据该方法，对A、B、C、D四个选项带入后逐个判断，可以发现A、B、C均符合，而D选项中5进入拓扑序列后，删除5的出度所在的弧，此时2仍有来自顶点1的入度，不能加入拓扑序列，故本题选D。

8、试题答案：B

试题解析：

【考点】本题考查B树的性质
【解析】一棵m阶的B-树或者为空树，或者具有这样的特性：（1）树中每个结点至多有m棵子树；（2）除根结点以外的所有非叶子结点至少有m/2向上取整棵子树，根结点若非叶子结点，则至少含有两棵子树。所有非终端结点（终端结点即为叶子结点，其关键字个数为0）中包含关键字的个数范围为[ m/2取上界-1，m-1]。因此，m=3时，非叶节点最少1个关键字，最多2个关键字。又因为该树的高度为5，且为含最少关键字的个数，因此每个非叶子结点含有1个关键字，该树的形态与高度为5的满二叉树形态相同，关键字的个数至少为31个。故本题选B。