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、 平均查找长度