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

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

1、下列函数的时间复杂度是（ ）。

A、

B、

C、

D、

2、下列关于栈的叙述中，错误的是（ ）。Ⅰ.采用非递归方式重写递归程序时必须使用栈Ⅱ.函数调用时，系统要用栈保存必要的信息Ⅲ.只要确定了入栈次序，即可确定出栈次序Ⅳ.栈是一种受限的线性表，允许在其两端进行操作

A、仅Ⅰ

B、仅Ⅰ、Ⅱ、Ⅲ

C、仅Ⅰ、Ⅲ、Ⅳ

D、仅Ⅱ、Ⅲ、Ⅳ

3、适用于压缩存储稀疏矩阵的两种存储结构是（ ）。

A、 三元组表和十字链表

B、 三元组表和邻接矩阵

C、 十字链表和二叉链表

D、 邻接矩阵和十字链表

4、要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是（ ）。

A、 只有左子树

B、 只有右子树

C、 结点的度均为1

D、 结点的度均为2

5、已知一棵二叉树的树形如下图所示，其后序序列为e， a， c， b， d， g， f，树中与结点a同层的结点是（ ）。

A、 c

B、 d

C、 f

D、 g

6、已知字符集{a， b， c ，d ， e， f， g， h}，若各字符的哈夫曼编码依次是0100，10，0000，0101，001，011，11，0001，则编码序列0100011001001011110101的译码结果是（ ）。

A、 a c g a b f h

B、 a d b a g b b

C、 a f b e a g d

D、 a f e e f g d

7、已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是（ ）。

A、 10

B、 11

C、 13

D、 15

8、下列二叉树中，可能成为折半查找判定树（不含外部结点）的是（ ）。

A、

B、

C、

D、

9、下列应用中，适合使用B+树的是（ ）。

A、 编译器中的词法分析

B、 关系数据库系统中的索引

C、 网络中的路由表快速查找

D、 操作系统的磁盘空闲块管理

1、试题答案：B

试题解析：

2、试题答案：C

试题解析：

【考点】本题考查栈的使用
【解析】斐波拉契数列的计算迭代实现只需要一个循环即可，因此I错误。函数调用时，系统需要保存栈的必要信息防止丢失，因此II正确。入栈序列为1、2，进行如下操作PUSH、POP、PUSH、POP，出栈次序为1、2；入栈序列为1、2，进行如下操作PUSH、PUSH、POP、POP，出栈次序为2、1，由此可知已知入栈顺序其出栈顺序有多种，同理已知出栈顺序其入栈顺序有多种，因此III错误。栈是一种受限的线性表，具有“后进先出”的特性，只允许在一端进行操作，因此IV错误。故本题选C。

3、试题答案：A

试题解析：

4、试题答案：B

试题解析：

【考点】本题考查二叉树的遍历
【解析】先序序列依次是根结点、左子树、右子树；中序序列依次是左子树、根结点、右子树。只有当所有的非叶结点只有右子树（即没有左子树）时，那么先序序列与中序序列遍历顺序依次都是根结点、右子树，两者相同。故本题选B。

5、试题答案：B

试题解析：

【考点】本题考查二叉树的遍历
【解析】后序序列遍历依次为左子树、右子树、根结点。为上述结点从上至下从左至右依次编号为1、2、3、4、5、6、7，即二叉树的树形如下图所示：

对该树进行后序遍历后可得后序序列为6427531，与题干所给的后序序列e， a， c， b， d， g， f一一对应，可得a的编号为4，与编号4同层的为编号5，对应序列中的d。综上，a与d同层，故本题选B。

6、试题答案：D

试题解析：

【考点】本题考查哈夫曼编码
【解析】哈夫曼编码是前缀编码，任意两个字符的编码都是不同的且每个结点的编码不会是其他结点的前缀。因此可以将编码序列直接与哈夫曼编码对应即可。原序列可以写成：0100 011 001 001 011 11 0101。则译码结果为：a f e e f g d。故本题选D。

7、试题答案：B

试题解析：

【考点】本题考查无向图
【解析】无向图的各顶点的度的总和是边数的两倍。那么本题中度的总和为32，若设度小于3顶点度为2，个数为x，则有2*x+4*3+3*4>=32，解得x>=4。当顶点个数最少时，x=4，此时总的顶点数=3+4+4=11。故选B。

8、试题答案：A

试题解析：

【考点】本题考查折半查找判定树
【解析】折半查找的判定树是平衡的二叉排序树，由mid所指元素将原有元素分割到左右子树中，只有最小层结点不满。若查找表有n个结点，则失败结点n+1个。树的高h不包括失败结点，h=log2（n+1）向上取整。mid取值可以采取向上取整的规则，也可以采取向下取整的规则，但同一棵折半查找判定树的规则应该一致。若采取向上取整的规则，则最后一层的叶子结点应当同为左子节点； 若采取向下取整的规则，则最后一层的叶子结点应当同为右子节点。折半查找判定树的最后一层的叶子结点不同出现既有左叶子结点又有右叶子结点的情况，因此排除B和C选项。为A和D选项的树赋值，检查其是否符合折半查找判定树的特性。
A选项对应的折半查找判定树如下：

检查上述折半查找判定树，各结点符合其特性，因此A正确。
D选项对应的折半查找判定树如下：

根结点左子结点个数为4，右子结点的个数为5，因此判断该树采用向下取整的规则。按照该规则，序列1、2、3、4的mid应该为2，但上图为3，该树混杂了两种取整规则，因此D选项错误。故本题选A。

9、试题答案：B

试题解析：

【考点】本题考查B+树的应用
【解析】B+树是应文件系统所需而产生的B-树的变形，B+树的磁盘读写代价更低，查询效率更加稳定，更加适用于操作系统的文件索引和数据库索引。编译器中的词法分析使用有穷自动机和语法树，因此选项A错误。网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法，因此C选项错误。操作系统的磁盘空闲块管理一般使用空闲空间链表，因此D选项错误。故本题选B。