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

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

1、下列程序段的时间复杂度是（  ）。count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;

A、 O(log₂n)

B、 O(n)

C、 O(nlog₂n)

D、 O(n²)

2、假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是（  ）。

A、 +(*-

B、 +(-*

C、 /+(*-*

D、 /+-*

3、循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是（  ）。

A、 队空：end1==end2；队满：end1==(end2+1)modM

B、 队空：end1==end2；队满：end2==(end1+1)mod(M-1)

C、 队空：end2==(end1+1)modM；队满：end1==(end2+1)modM

D、 队空：end1==(end2+1)modM；队满：end2==(end1+1)mod(M-1)

4、若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是（  ）。

A、 e、c

B、 e、a

C、 d、c

D、 b、a

5、将森林F转换为对应的二叉树T，F中叶结点的个数等于（  ）。

A、 T中叶结点的个数

B、 T中度为1的结点个数

C、 T中左孩子指针为空的结点个数

D、 T中右孩子指针为空的结点个数

6、5个字符有如下4种编码方案，不是前缀编码的是（  ）。

A、 01，0000，0001，001，1

B、 011，000，001，010，1

C、 000，001，010，011，100

D、 0，100，110，1110，1100

7、对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（  ）。

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

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

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

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

8、用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象。下列选项中，会受堆积现象直接影响的是（  ）。

A、 存储效率

B、 散列函数

C、 装填(装载)因子

D、 平均查找长度

1、试题答案：C

试题解析：

【考点】本题考查时间复杂度的运算。
【解析】这是一道典型的双层for循环问题，分析程序段，外层for循环与内层for循环之间不会互为循环条件，因此时间复杂度与外层for循环执行次数*内层for循环执行次数。分析外层for循环，设外层循环执行Tn1次，当循环执行一次时，k=1=2⁰；当循环执行两次时，k=2=2¹；当循环执行三次，k=4=2²；……；当循环执行Tn1次，k=2^Tn-1。带入到循环结束条件中，2^Tn1-1<=n，Tn1<=log₂n+1。设内层for循环执行次数为Tn2，当循环执行一次时，j=1；当循环执行两次时，j=2；当循环执行三次，j=3；……；当循环执行Tn2次，j=Tn2。带入到循环结束条件中，Tn2<=n，因此执行次数=（log₂n+1）*n。根据时间复杂度的运算规则，忽略常数项，因此时间复杂度为O(nlog₂n)。解得故本题选C。

2、试题答案：B

试题解析：

【考点】本题考查栈的应用。
【解析】从中缀式的左端开始取字符，逐步进行如下步骤：
① 若取出的字符是操作数，则该操作数直接送入S2栈。
② 若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符(不包括括号运算符)优先级高于S1栈栈顶运算符（包括左括号）优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符（包括左括号）低于（不包括等于）该运算符优先级时停止弹出运算符，最后将该运算符送入S1栈。
③ 若取出的字符是“（”，则直接送入S1栈顶。
④ 若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
⑤ 重复上面的1~4步，直至处理完所有的输入字符。
⑥ 若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。如果表达式结束，但栈中还有元素，将所有元素出栈，添加到后缀表达式中
根据上述操作步骤对中缀表达式a/b+(c*d-e*f)/g分析过程如下表所示：

故本题选B。

3、试题答案：A

试题解析：

【考点】本题考查循环队列判空判满的条件。
【解析】将顺序队列首尾相接成环状空间，在循环队列中，队头指针指向头元素，队尾指针指向尾元素的下一个位置。若循环队列中存放n个元素，则rear==front，此时无法判断是队空的条件还是队满的条件。为了区分这两者，规定循环队列中当元素个数为n-1个时，判定队列已满的条件为队头指针front在队尾指针rear的下一个位置上，因此最大容量为s的循环队列，本题中最大容量为M，因此队满条件为（end2+1）%s==end1；队空条件为end2=end1；入队操作队尾指针应该更新为：end2==e;
end2==(end2+1)%M; 出队操作队首指针应该更新为：e==end1; end1==(end1+1)%M。故本题选A。

4、试题答案：D

试题解析：

【考点】本题考查中序线索化。
【解析】创建线索二叉树的思路为：按照一定的规则将二叉树中的结点排列成一个线性序列，该线性序列可以为前序序列、中序序列、后序序列；在二叉链表的结点中添加两个指针域，左线索域指向该结点的前驱结点，右线索域指向该结点的后继结点，指针成为线索，加上线索的二叉树即为线索二叉树。因此本题考查二叉树的中序遍历， x的左指针指向中序序列的前驱结点，x的右指针指向中序序列的后继序列。对上述二叉树中序遍历后的结果为：debxac。因此x的左右线索分别指向b，a。故本题选D。

5、试题答案：C

试题解析：

【考点】本题考查森林转换为二叉树的步骤。
【解析】森林转为二叉树的步骤如下：（1）将每棵树转为二叉树；（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。因此森林转换为二叉树时，森林的叶子结点没有左右子树，按照“左孩子右兄弟”的转换理论，森林的叶子结点转换二叉树后没有左孩子。但由于无法确定叶子结点是否有右兄弟结点，因此无法判断叶子结点转换为二叉树是否有右孩子。故本题选C。

6、试题答案：D

试题解析：

【考点】本题考查哈夫曼编码的特性。
【解析】判定某字符集的不等长编码是否具有前缀特性的过程描述为字符集的每一个编码应该对应一条路径。初始时，二叉树仅含有一个根结点，其左右指针为空。依次读入字符集中的编码，每读入一个编码从根结点开始，若为0则沿左子针向下移动，若为1则沿右指针向下移动，当指针指向的下一个结点为空且当前结点未标记，则创建一个结点并标记；若编码至最后一位且指针指向的是非空结点，则不具有前缀特性，返回；若当前编码没有至最后一位且遇到已标记的叶子结点，则不具有前缀特性，返回。当所有编码读入完毕且通过验证则具有前缀性。按照上述方法将ABCD选项分别转换为一棵树，根据创建树的过程是否符合哈夫曼树的特性来判断是否为前缀编码。A选项创建树如下：

上述编码创建的树符合哈夫曼树的特性，因此A正确。
B选项创建树如下：

上述编码创建的树符合哈夫曼树的特性，因此B正确。
C选项创建树如下：

上述编码创建的树符合哈夫曼树的特性，因此C正确。
D选项中的110是110的缀。而在一棵哈夫曼树中，树的叶子结点表示字符，因此110在树中不是叶子结点，因此该字符集不具有前缀性。故本题选D。

7、试题答案：D

试题解析：

【考点】本题考查拓扑排序。
【解析】拓扑排序的针对有向图的排序方法，求拓扑排序的方法为：
初始时拓扑序列为空；任选一个入度为0的点放入拓扑序列中，同时删除该顶点以及从该顶点出发的弧；
重复上述操作直至不存在入度为0的顶点。按照上述方法，初始时3的入度为0，加入拓扑序列。将从3出发的弧删除，此时1的入度为0，将1加入拓扑序列。将从1出发的弧删除，此时4的入度为0，将4加入拓扑序列。将从4出发的弧删除，此时2和6的入度为0，若选择2，则拓扑序列为3、1、4、2、6、5；若选择6，则拓扑序列为3、1、4、6、2、5。故本题选D。

8、试题答案：D

试题解析：

【考点】本题考查哈希的堆积现象。
【解析】堆积现象即为哈希地址发生冲突。当存储效率不会直接受到影响，因此A选项错误。散列函数影响堆积，因果错了，因此B选项错误；装填因子指所有关键字填充哈希表后饱和的程度，它等于关键字的总数/表的长度。因子装填因子与堆积线性无关，因此C选项错误。每发生一次冲突，平均查找长度就增加，因此堆积现象会直接影响平均查找长度。故本题选D。