2016年计算机组成原理考研真题答案及解析（一）

本文提供2016年计算机组成原理考研真题答案及解析，以下为具体内容

1、给定二叉树如下图所示，设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。如遍历后的结点序列为7、6、5、4、3、2、1，则其遍历方式是（ ）。

A、LRN

B、NRL

C、RLN

D、RNL

2、若数据元素序列8，10，15，5，7，9，31，2，6是下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。

A、起泡

B、选择

C、插入

D、二路归并

3、一棵度为5的树中有度为1的结点2个，度为2的结点3个，度为3的结点2个，度为4的结点1个，度为5的结点2个，则度为0的结点（ ）个。

A、19

B、21

C、10

D、9

4、若一个具有N个顶点、E条边的无向图是一个森林（N>E），则该森林中必有（ ）棵树。

A、1

B、N

C、E

D、N-E

5、深度为K（K>1）的完全二叉树，若按自上而下、自左向右的次序给结点编号（从1开始），则编号最小的叶子结点编号是（ ）。

A、

B、

C、

D、

6、设a，b为一棵二叉树的两个结点，在中序遍历时，a在b的前面的条件是（ ）。

A、a在b的左方

B、a在b的右方

C、a是b的祖先

D、a是b的子孙

7、对于三个结点A、B、C，可构成（ ）棵不同的二叉树。

A、4

B、5

C、30

D、6

8、如果T是哈夫曼最优二叉树且各叶结点的权值分别为1，2，3，4，5，6，则最优二叉树T的带权路径长度是（ ）。

A、51

B、30

C、45

D、27

9、二维数组A的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围是从0到4，列下标j的范围是从0到5，A按行存储时，元素A[3][5]的起始地址与A按列存储时元素（ ）的起始地址相同。

A、A[2][4]

B、A[3][5]

C、A[3][4]

D、A[4][4]

1、试题答案：D

试题解析：

当遍历方式是LRN时，遍历后的结点序列为2、1、4、6、5、7、3；当遍历方式是NRL时，遍历后的结点序列为3、7、5、6、4、1、2；当遍历方式是RLN时，遍历后的结点序列为6、4、5、7、2、1、3；当遍历方式是RNL时，遍历后的结点序列为7、6、5、4、3、2、1。故本题选D。

2、试题答案：C

试题解析：

起泡排序和选择排序第二趟排序后的结果中最大或最小的两个元素以及位于对应的位置上；起泡排序第二趟排序后的结果中每四个元素是有序的；插入排序第二趟排序后的结果中前两个元素是有序的。故本题选C。

3、试题答案：A

试题解析：

根据树的性质可知，结点个数n=n0+n1+n2+n3+n4+n5（结点数量）=n1+2n2+3n3+4n4+5n5+1（边数量+1）。则树T中的叶子结点n0的个数是n2+2n3+3n4+4n5+1=3+2×2+3×1+4×2+1=19。故本题选A。

4、试题答案：D

试题解析：

5、试题答案：B

试题解析：

6、试题答案：A

试题解析：

在中序遍历中，先遍历左子树的所有结点，然后是根节点，最后是右子树的所有结点。当且仅当a在b的左方时，能确保a在b的前面。故本题选A。

7、试题答案：B

试题解析：

对于三个结点A、B、C，可构成5棵不同的二叉树。具体形态如下图所示。

故本题选B。

8、试题答案：A

试题解析：

构造的最优二叉树如下图所示。

因此最优二叉树T的带权路径长度是4*2+5*2+6*2+3*3+1*4+2*4=41。故本题选A。

9、试题答案：C

试题解析：

不妨设二维数组的起始地址为0，按行优先存储时，先存储第一行，再存储第二行，以此类推，A[3][5]的地址为=4*3*6+4*5=92；按列优先存储时，先存储第一列，再存储第二列，以此类推，起始地址为92的元素A[i][j]的j值为92/(4*5)=4，i值为(92-4*5*4)/4=3。因此元素A[3][5]的起始地址与A按列存储时元素A[3][4]的起始地址相同。故本题选C。