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

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

1、已知一棵完全二叉树的第6层（设根为第1层）有8个结点，则该完全二叉树的结点个数是（ ）。

A、39

B、52

C、71

D、64

2、下列二叉排序树中，满足平衡二叉树定义的是（ ）。

A、

B、

C、

D、

3、已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中的元素，则关键字的比较次数最多为（ ）。

A、7

B、6

C、5

D、4

4、若采用递归方式对顺序表进行快速排序，关于递归次数的描述正确的是（ ）。

A、递归次数与初始数据的排列次序无关

B、递归次数与每次划分后得到的分区的处理次序无关

C、每次划分后先处理较长的分区可减少递归次数

D、每次划分后先处理较短的分区可减少递归次数

5、表达式a*(b-c)+d的后缀表达式是（ ）。

A、abcd*-+

B、abc-*d+

C、abc*-d+

D、+-*abcd

6、一个有N个顶点的无向图最多有（ ）条边。

A、N

B、N*(N-1)

C、N*(N-1)/2

D、2*N

7、对二叉排序树进行插入操作时，二叉排序树的高度（ ）。

A、一定不变

B、不一定变化

C、一定下降

D、一定增高

8、二维数组A的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，A的第8列和第5行共占（ ）个存储单元。

A、108

B、60

C、54

D、114

9、4个元素a1，a2，a3和a4依次通过一个堆栈，在a4进栈前，栈的状态是：可能的出栈序列是（ ）。

A、a3，a1，a4，a2

B、a3，a4，a1，a2

C、a4，a2，a3，a1

D、a3，a4，a2，a1

10、若一棵度为3的树T中，有A个度为1的结点，B个度为2的结点，C个度为3的结点，则该树有（ ）个叶结点。

A、1+2B+3C

B、A+2B+3C

C、2B+3C

D、1+B+2C

1、试题答案：A

试题解析：

该完全二叉树的第6层有8个节点，则该树的深度为6，前5层的节点数分别为1、2、4、8、16。因为是完全二叉树，第6层上方的所有层的节点数加起来恰好是15个。因此，这棵完全二叉树的节点总数为：1 + 2 + 4 + 8 + 16 + 8 = 39。故本题选A。

2、试题答案：B

试题解析：

平衡二叉树，也称为AVL树，是一种自平衡二叉搜索树。它的定义是：它是一棵空树或者具有以下性质的二叉搜索树：（1）左子树和右子树的高度差不超过1；（2）左子树和右子树都是平衡二叉树。故本题选B。

3、试题答案：C

试题解析：

折半查找法是一种基于有序序列的查找算法，每次将待查找区间折半，确定下一次需要查找的区间。由于16>1+2+4+8，因此长度为16的顺序表L的折半查找判定树的高度为5，最坏情况下关键字的比较次数为5。故本题选C。

4、试题答案：B

试题解析：

在对顺序表进行快速排序时，每次划分都会将待排序区间分为两个子区间，并将一个元素放置到它最终的位置。递归次数取决于划分出来的子区间的个数，而与每次划分后得到的分区的处理次序无关，因为最终排序的结果只与子区间的大小关系有关，而不涉及子区间之间的相对位置。故本题选B。

5、试题答案：B

试题解析：

将中缀表达式转换为后缀表达式的算法思想如下：
从左向右开始扫描中缀表达式；
遇到数字时，加入后缀表达式；
遇到运算符时：
（1）若为'('，入栈；
（2）若为')'，则依次把栈中的运算符加入后缀表达式，直到出现'('，从栈中删除'('；
（3）若为除括号外的其他运算符，当其优先级高于除'('外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或遇到了一个左括号为止。
当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。因此利用栈得到的表达式a*(b-c)+d的后缀表达式为abc-*d+。故本题选B。

6、试题答案：C

试题解析：

无向图中每个顶点最多与N-1个顶点相连，而对于N个顶点，总共可以有N*(N-1)条边，但每条边会被计算两次，因此最终结果为N*(N-1)/2。故本题选C。

7、试题答案：B

试题解析：

在对二叉排序树进行插入操作时，二叉排序树的高度可能会发生变化，具体变化取决于插入节点的位置。如果插入的节点在根节点的左子树或右子树中，而且插入节点的深度大于当前树的最大深度，则树的高度会增加。但是如果插入的节点的深度小于或等于当前树的最大深度，则树的高度不会发生变化。因此，二叉排序树的高度是否变化取决于插入节点的深度和当前树的最大深度。故本题选B。

8、试题答案：A

试题解析：

由题可知，二维数组A的第8列和第5行的交点就是要求的区域。因为每个字符占一个存储单元，所以只需计算出该区域中字符的个数即可。第8列共有9个元素，第5行共有10个元素，但该区域的交点位置被重复计算了一次，因此总共有9+10-1=18个元素，即18个成员，占18×6=108个存储单元。故本题选A。

9、试题答案：D

试题解析：

栈（stack）是一种具有特殊操作的线性数据结构，其特点是只允许在一端进行插入和删除操作。选项A和选项B中a1不可能在a2出栈之前出栈，选项C中a2不可能在a3出栈之前出栈。故本题选D。

10、试题答案：D

试题解析：

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