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

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

1、用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象。下列选项中，会受堆积现象直接影响的是（  ）。

A、 存储效率

B、 散列函数

C、 装填(装载)因子

D、 平均查找长度

2、冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是（ ）。

A、指令操作码的译码结果

B、指令和数据的寻址方式

C、指令周期的不同阶段

D、指令和数据所在的存储单元

3、在顺序表中访问第i个位置的元素和在第i个位置插入一个新元素的时间复杂度为（）。

A、O(1)，O(1)

B、O(1)，O(n)

C、O(n)，O(1)

D、O(n)，O(n)

4、下列叙述中，不符合m阶B树定义要求的是（）。

A、根结点最多有m棵子树

B、所有叶结点都在同一层上

C、叶结点之间通过指针连接

D、各结点内关键字均升序或降序排列

5、已知操作符包括'+'、'-'、'*'、'/'、'('和')'。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）。

A、5

B、7

C、8

D、11

7、如果T是由树F转换而来的二叉树，那么F中结点的后根序列就是T中结点的（）序列。

A、先序

B、中序

C、后序

D、层次

8、若一棵完全二叉树有998个结点，则该二叉树的叶结点个数是（）。

A、487

B、488

C、499

D、500

9、在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（）。Ⅰ.若v是T1的叶结点，则T1与T3不同Ⅱ.若v是T1的叶结点，则T1与T3相同Ⅲ.若v不是T1的叶结点，则T1与T3不同Ⅳ.若v不是T1的叶结点，则T1与T3相同

A、仅Ⅰ、Ⅲ

B、仅Ⅰ、Ⅳ

C、仅Ⅱ、Ⅲ

D、仅Ⅱ、Ⅳ

1、试题答案：D

试题解析：

【考点】本题考查哈希的堆积现象。
【解析】堆积现象即为哈希地址发生冲突。当存储效率不会直接受到影响，因此A选项错误。散列函数影响堆积，因果错了，因此B选项错误；装填因子指所有关键字填充哈希表后饱和的程度，它等于关键字的总数/表的长度。因子装填因子与堆积线性无关，因此C选项错误。每发生一次冲突，平均查找长度就增加，因此堆积现象会直接影响平均查找长度。故本题选D。

2、试题答案：C

试题解析：

指令和数据都存放在主存，它们都以二进制代码形式出现，区分的方式有：
（1）时间上：从主存中取出的机器周期不同。取指周期取出的是指令，分析取数或执行周期取出的是数据。
（2）空间上：取指令和取数据时地址的来源不同。指令地址来源于程序计数器PC，数据地址来源于地址形成部件。
故本题选C。

3、试题答案：B

试题解析：

在顺序表中，访问第i个位置的元素的时间复杂度为O(1)，因为在内存中直接通过计算可以得到其地址。插入一个新元素到第i个位置需要将第i个位置及之后的元素向后移动，因此需要O(n)的时间复杂度。故本题选B。

4、试题答案：C

试题解析：

一棵m阶的B树或者为空树，或者具有这样的特性：（1）树中每个结点至多有m棵子树；（2）除根结点以外的所有非叶子结点至少有⎾m/2⏋棵子树，根结点若非叶子结点，则至少含有两棵子树。所有非终端结点（终端结点即为叶子结点，其关键字个数为0）中包含关键字的个数范围为[⎾m/2⏋-1，m-1]。选项A、B、D都符合m阶B树的定义要求，而选项C不符合，因为m阶B树的叶结点不存储指向其他节点的指针。故本题选C。

5、试题答案：A

试题解析：

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

7、试题答案：B

试题解析：

对于一棵树，先根遍历的顺序是：先访问根节点，然后依次遍历子树。后根遍历的顺序是：先依次遍历子树，再访问根节点。当以二叉链表作树的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法实现之。故本题选B。

8、试题答案：C

试题解析：

根据完全二叉树的性质可以得知，度为1的结点个数最多为1。根据树的性质可知，结点个数n=n0+n1+n2（结点数量）=n1+2n2+1（边数量+1），则树中的叶子结点n0的个数是n2+1。因此含有998个结点的完全二叉树中有499个叶子节点、1个度为2的结点和498个度为2的结点。故本题选C。

9、试题答案：C

试题解析：

若p结点是叶子结点，直接删去该结点。因此重新插入后的T3与删除前的T1一致。若p结点不是叶子结点，不妨设p结点同时存在左、右子树。根据二叉排序树的特点，可以从其左子树中选择关键字最大的结点r，用结点r的值替代结点p的值（结点值替换），并删除结点r，其原理是用中序前驱替代被删结点。也可以从其右子树中选择关键字最小的结点，用结点r的值替代结点p的值，而且将它删除，其原理是用中序后继替代被删结点。因此删除后的T2结构已经发生了变化，重新插入后的T3与删除前的T1不一致。故本题选C。