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、 操作系统的磁盘空闲块管理