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

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

1、设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。

A、 O（log₂n）

B、 O（n）

C、 O（nlog₂n）

D、 O（n²）

2、元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（  ）。

A、 3

B、 4

C、 5

D、 6

3、已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（  ）。

A、 0，0

B、 0，n-1

C、 n-1，0

D、 n-1，n-1

4、 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（  ）。

A、 257

B、 258

C、 384

D、 385

5、若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2，3，4和4，3，2，1，则该二叉树的中序遍历序列不会是（  ）。

A、 1，2，3，4

B、 2，3，4，1

C、 3，2，4，1

D、 4，3，2，1

6、已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是（  ）。

A、 115

B、 116

C、 1895

D、 1896

7、对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（  ）。

A、 95，22，91，24，94，71

B、 92，20，91，34，88，35

C、 21，89，77，29，36，38

D、 12，25，71，68，33，34

8、下列关于图的叙述中，正确的是（ ）。Ⅰ.回路是简单路径Ⅱ.存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ.若有向图中存在拓扑序列，则该图不存在回路

A、 仅Ⅱ

B、 仅Ⅰ、Ⅱ

C、 仅Ⅲ

D、 仅Ⅰ、Ⅲ

9、为提高散列（Hash）表的查找效率，可以采取的正确措施是（  ）。Ⅰ. 增大装填（载）因子Ⅱ. 设计冲突（碰撞）少的散列函数Ⅲ. 处理冲突（碰撞）时避免产生聚集（堆积）现象

A、 仅Ⅰ

B、 仅Ⅱ

C、 仅Ⅰ、Ⅱ

D、 仅Ⅱ、Ⅲ

10、为实现快速排序算法，待排序序列宜采用的存储方式是（  ）。

A、 顺序存储

B、 散列存储

C、 链式存储

D、 索引存储

1、试题答案：A

试题解析：

【考点】本题考查时间复杂度的计算。
【解析】本题中循环体中执行的程序为x=2*x;当循环执行1次，则x=2²；当循环执行2次，则x=2³……设循环执行Tn次，则x=2^Tn+1，带入循环条件中，2^Tn+1<n/2，解得Tn<log2n-2，根据时间复杂度的运算规则，忽略常数项，平均时间复杂度为O（log₂n）。

2、试题答案：B

试题解析：

【考点】本题考查栈的特性。
【解析】元素d进栈时，元素a，b，c已在栈中，d出栈后，则e可以在c，b，a任一元素的前面进栈并出栈，也可以在元素a后出栈，但是出栈顺序必为d_c_b_a_，其中，e的顺序不定，在任意一个“_”上都有可能。
其中入栈序列如下所示：

若d出栈后e入栈，则栈中序列为：

此时出栈顺序为d、e、c、b、a。

若d出栈后c出栈，e入栈，栈中序列为：

此时出栈顺序为d、c、e、b、a。

若d出栈后c出栈，b出栈，e入栈，此时栈中序列为：

此时出栈顺序为d、c、b、e、a。
若d出栈后c出栈，b出栈，a出栈，e入栈，此时栈中序列为：

此时出栈顺序为d、c、b、a、e。共有四种出栈序列，故本题选B。

3、试题答案：B

试题解析：

【考点】本题考查循环队列。
【解析】本题中循环队列非空时front和rear分别指向队头元素和队尾元素。因此，当第一个元素进入队列后，rear=front=0。根据此时的尾指针位置，倒推尾指针初始时的位置。已知当循环队列执行入队操作后，尾指针更新rear=（rear+1）%maxsize，本题maxsize=n，根据入队后rear=0可知，（rear+1）%n=0，因此rear=n-1。入队操作不改变头指针的位置，因此入队操作前后的头指针相等，即front=0。故本题选B。

4、试题答案：C

试题解析：

【考点】本题考查完全二叉树的计算。
【解析】由题意可知，这是完全二叉树。完全二叉树除最后一层的每一层上结点的个数都达到最大值，最后一层允许缺少若干右子结点。根据二叉树的性质，对任何一棵二叉树，若终端结点为n0，度为2的结点为n2，则n0=n2+1。在完全二叉树中，当结点个数n为偶数时，n1=1，当结点个数n奇数时，n1=0。本题n=768，因此n1=1。n=n0+n1+n2=n0+1+n0-1=2*n0=768，解得n0=768/2=384。故本题选C。

5、试题答案：C

试题解析：

【考点】本题考查二叉树的遍历。
【考法】根据前序序列和后序序列分析可能的中序序列
【解析】前序遍历二叉树是先访问根结点，再遍历左子树，最后遍历右子树。而后序遍历二叉树先遍历左子树，再遍历右子树，最后访问根结点。已知二叉树的前序遍历序列与中序遍历序列可以唯一确定一棵二叉树，因此可以通过带入A、B、C、D各选项构造二叉树，再检查构造后的二叉树的后序遍历序列是否和题干中的后序序列相同。根据A选项和前序遍历序列构造二叉树如下：

后序遍历该二叉树得到序列：4321，与题干所给后序序列相同，因此A选项正确。
根据B选项和前序遍历序列构造二叉树如下：

后序遍历该二叉树得到序列：4321，与题干所给后序序列相同，因此B选项正确。
根据C选项和前序遍历序列构造二叉树如下：

后序遍历该二叉树得到序列：3421，与题干所给后序序列不相同，因此C选项错误。
根据D选项和前序遍历序列构造二叉树如下：

后序遍历该二叉树得到序列：4321，与题干所给后序序列相同，因此D选项正确。故本题选C。

6、试题答案：D

试题解析：

【考点】本题考查树与二叉树的转换。
【解析】本题可以采用特殊情况方法求解。根据题意，假设树的结构如下图所示：

上述图结构最后一层有116张叶子结点，其余结点串行连接。将树转换为二叉树的步骤为：（1）将树的根结点直接作为二叉树的根结点；（2）将树的根节点的第一个子节点作为二叉树根节点的左指针，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右指针。（3）树中的剩余节点按照上一步的方式（左孩子，右兄弟），依序添加到二叉树中。直到树中所有的节点都在二叉树中。依照这种方法转换后的二叉树无右子树。根据上述规则，将图中的树转换的二叉树，仅有最后一层的前115个结点有右孩子，其余结点均无右孩子。因此本题中无右孩子结点个数=2011-115=1896。故本题选D。

7、试题答案：A

试题解析：

【考点】本题考查二叉排序树的查找。
【解析】二叉排序树的基本概念为二叉排序树或者为空树，或者为具有如下特性的树：①若它的左子树不为空，则左子树上的所有结点的值均小于根结点的值；②若它的右子树不为空，则右子树上的所有结点的值均大于或等于根结点的值；③其左右子树也分别为二叉排序树。根据这个性质，画出各选项对应的二叉排序树的查找过程，检查是否符合上述特性。
画出A选项二叉排序树的查找路径如下所示：

从上图可知，94比91大，不应该出现在91的左子树中，A选项错误。
画出B选项二叉排序树的查找路径如下所示：

上图符合二叉排序树的特性，B选项正确。
画出C选项二叉排序树的查找路径如下所示：

上图符合二叉排序树的特性，C选项正确。
画出D选项二叉排序树的查找路径如下所示：

上图符合二叉排序树的特性，D选项正确。故本题选A。

8、试题答案：C

试题解析：

【考点】本题考查图的概念。
【解析】回路是指第一个顶点和最后一个顶点相同的路径称为回路。而简单路径表示序列中顶点不重复出现的路径，所以回路不是简单路径，故Ⅰ错误。稀疏图一般用于边比较少的时候，在考虑空间的选择上，因为邻接矩阵的空间复杂度为O（n²），而邻接表的空间复杂度为O（n+e）， 所以应该选用邻接表，故Ⅱ错误。一般判断图是否存在回路（环），有两种判断方式，即深度遍历和拓扑排序。若深度遍历中有结点被第二次访问到则证明有环。拓扑排序的思想为每次找入度为0的点，添加到输出队列，然后将与此点相连的结点入度减1，重复上述过程直至删除所有结点。若存在结点无法删除，则证明有环。即若存在拓扑序列，则该图不存在回路。所以，Ⅲ正确，故本题选C。

9、试题答案：D

试题解析：

【考点】本题考查提高散列表查找效率的方法。
【解析】离散表的查找效率取决于散列函数、处理冲突的方法和装填因子。装填因子指所有关键字填充哈希表后饱和的程度，它等于关键字的总数/表的长度。装填因子越大，哈希表越饱和，查找效率越低，故Ⅰ错误。通过设计冲突少的散列函数，也可以提高离散表的查找效率，故Ⅱ正确，使用适当的处理冲突的方式避免产生聚集现象，故 Ⅲ 正确。故本题选D。

10、试题答案：A

试题解析：

【考点】本题考查排序算法的存储。
【解析】快速排序需要进行比较和查询，顺序存储支持随机存取，适用于快速排序的特性，故本题选A。