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

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

1、一个递归算法必须包括（ ）。

A、递归部分

B、终止条件和递归部分

C、迭代部分

D、终止条件和迭代部分

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

A、12

B、13

C、14

D、15

3、对序列（8，12，23，56，29，41）从小到大进行基数排序，第一趟排序的结果是（）。

A、（41，12，23，56，8，29）

B、（12，23，56，41，8，29）

C、（8，12，23，29，41，56）

D、（29，56，8，41，23，12）

4、从N（N>100）个整数中求三个最小值，采用（）排序所需比较关键字的次数最少。

A、简单选择

B、归并

C、快速

D、直接插入

5、对14个记录的表进行2-路归并排序，共需移动（）次记录。

A、42

B、91

C、84

D、56

6、对有序单链表可使用（）查找法进行查找。

A、顺序

B、折半

C、分块

D、哈希

7、在平衡二叉树中插入一个节点后引起了不平衡，设最接近叶子的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是（）型旋转。

A、LL

B、LR

C、RL

D、RR

8、某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是（）。

A、43

B、79

C、198

D、200

1、试题答案：B

试题解析：

【考点】本题考查递归算法的概念。
【解析】一个递归算法包括终止条件和递归部分，结束条件不再进行递归调用，可以结束。递归部分将问题划分为子问题，多次递归从而解决问题。故本题选B。

2、试题答案：B

试题解析：

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

3、试题答案：A

试题解析：

基数排序的思想是根据数字位数从低到高依次对待排序元素进行排序。第一趟排序按个位数字进行排序，第二趟排序按十位数字进行排序，以此类推，直到按最高位排序结束。对序列（8，12，23，56，29，41）从小到大进行基数排序，按个位数字排序，得到：（41，12，23，56，8，29）；然后按十位数字排序，得到：（8，12，23，29，41，56）。故本题选A。

4、试题答案：A

试题解析：

5、试题答案：D

试题解析：

6、试题答案：A

试题解析：

折半查找要求待查找的数据结构必须是有序的数组，而题目中给出的是有序单链表，因此选项B是错误的；分块查找是一种针对有序表的查找方法，它需要预先将有序表分成若干块，并在每一块之中构建索引表，因此要求有序表是连续的存储结构。而题目中给出的是单链表，不具备连续存储结构，因此选项C是错误的；哈希查找是一种基于哈希表的查找方法，需要将关键字进行哈希映射，并根据哈希值在哈希表中进行查找。而题目中并没有给出需要使用哈希表的条件，因此选项D是错误的。在有序单链表中，可以按顺序遍历链表，逐个比较查找关键字和当前节点的关键字，直到找到目标节点或者遍历完整个链表。这种查找方法称为顺序查找或线性查找。故本题选A。

7、试题答案：B

试题解析：

（1）第一种情况：假设是因为A的左孩子的平衡因子发生变化而导致的不平衡，则A的左孩子的平衡因子只有可能是从0变为-1。这样进行的操作是在A节点的左孩子的右子树上插入节点，左子树的高度加一，最接近叶子的不平衡点是A的平衡因子由1变为2，则应进行的平衡旋转是LR型旋转。
（2）第二种情况：假设是因为A的右孩子的平衡因子发生变化而导致的不平衡，则A的右孩子的平衡因子只有可能是从-1变为0或1变为0。这样进行的操作可能是在A节点的右孩子的左子树或右子树上插入节点，右子树的高度并未发生变化，A的平衡因子也因此没有发生变化，不会导致不平衡。
故本题选B。

8、试题答案：A

试题解析：