2011年计算机组成原理考研真题答案及解析

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

1、设n，m是二叉树的两个结点，且n是m的祖先，下列（ ）序列中，n在m前面是不可能的。

A、先序序列

B、中序序列

C、后序序列

D、层次遍历序列

2、对下图的顶点进行拓扑排序，（ ）是不可能的拓扑序列。

A、①③⑨⑦④⑤②⑧⑥

B、⑨②⑤⑧①③⑦④⑥

C、⑨②①③⑦⑤⑧④⑥

D、①③⑦⑨②⑤⑧④⑥

3、若一棵度为3的树T中，有a个度为1的结点，b个度为2的结点，c个度为3的结点，则该树有（ ）个叶结点。

A、1+2b+3c

B、a+2b+3c

C、2b-3c

D、1+b+2c

4、下列四个关键字序列中，（ ）不是堆。

A、{05，23，16，68，94，72，71，73}

B、{05，16，23，68，94，72，71，73}

C、{05，23，16，73，94，72，71，68}

D、{05，23，16，68，73，71，72，94}

5、在一棵深度为H的完全二叉树中，所含结点的个数不少于（ ）。

A、

B、

C、

D、

6、若以{4，5，6，7，8}作为权值构造Huffman树，则该树的带权路径长度为（ ）。

A、68

B、69

C、70

D、71

7、向一棵m阶B-树进行关键字插入，当结点的关键字数目在插入之前为（ ）时，插入关键字时需要分裂该结点。

A、m-1

B、m-2

C、m

D、m+1

8、有二维数组B[1...20][0...5]按行优先顺序存放，设B[1][0]的存储地址为600，每个元素占3个单元，则B[3][2]的地址是（ ）。

A、636

B、630

C、642

D、645

9、设数组A[0...M-1]作为循环队列Q的存储空间，F为头指针，R为尾指针，删除队头元素的语句为（ ）。

A、F = (F+1) % M

B、F = (F+1) % (M+1)

C、F = (R+1) % M

D、F = F+1

10、设有5列火车编号为1，2，3，4，5，顺序开进一个栈式结构的站台，下列输出序列中不可能出现的序列为（ ）。

A、1，2，3，4，5

B、5，4，3，2，1

C、1，2，5，3，4

D、3，2，1，5，4

1、试题答案：C

试题解析：

因为在二叉树的后序序列中，先输出左右子树结点，最后输出根结点，因此n一定在m的后面输出。故本题选C。

2、试题答案：B

试题解析：

拓扑排序（Topological Sorting）是对有向无环图（DAG）进行排序的一种算法。它将有向无环图中的结点按照一定的顺序排列，使得图中任意一条有向边所指向的结点都排在它自己前面。拓扑排序可以用来解决任务调度、依赖关系等问题。在输出5的时候，此时5的入度不为0，因此⑨②⑤⑧①③⑦④⑥是不可能的拓扑序列。故本题选B。

3、试题答案：D

试题解析：

根据树的性质可知，结点个数n=n0+n1+n2+n3（结点数量）=n1+2n2+3n3+1（边数量+1）。则树T中的叶子结点n0的个数是n2+2n3++1=1+b+2c。故本题选D。

4、试题答案：C

试题解析：

根据堆的定义，一个堆需要满足父节点的值大于等于子节点的值（大根堆）或者小于等于子节点的值（小根堆）。因此，我们可以检查每一个序列是否满足这个条件。在序列C中，节点为73的左子节点为68，68大于73，不符合前面最大堆的设定，因此序列C不是堆。故本题选C。

5、试题答案：D

试题解析：

6、试题答案：B

试题解析：

构造Huffman树如下图所示。

该树的带权路径长度=2×6+2×7+2×8+3×4+3×5=69。故本题选B。

7、试题答案：A

试题解析：

在m阶B-树中，每个结点最多有m-1个关键字，每个结点最多有m个子节点。当要向一个结点插入关键字时，如果该结点的关键字数目小于m-1，则可以直接将关键字插入该结点中。但如果该结点已经有了m个关键字，则必须将该结点分裂成两个结点，同时将一个关键字上推到该结点的父节点中，以保证父节点的关键字数目不超过m-1。因此，当一个结点的关键字数目为m-1时，插入一个新的关键字需要进行结点的分裂操作。故本题选A。

8、试题答案：C

试题解析：

按行优先存储时，先存储第一行，再存储第二行，以此类推。因此，B[3][2]的地址为=600+3*(3-1)*6+3*2=642。故本题选C。

9、试题答案：A

试题解析：

循环队列的删除队头元素实际上是将头指针往后移一位，同时释放原队头所在的位置。因为是循环队列，头指针需要循环，即如果头指针已经指向数组的最后一个位置，那么删除队头元素之后需要把头指针重置到数组的第一个位置。故本题选A。

10、试题答案：C

试题解析：

选项C中编号为5的火车出栈以后，此时栈顶为编号为4的火车，编号为3的火车不可能在编号为4的火车出栈之前出栈。故本题选C。