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

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

1、数据元素之间的关系称为（ ）。

A、操作

B、数据对象

C、结构

D、数据集合

2、已知表头元素为b的单链表在内存中的存储状态如下所示：现将f存放于1014H处并插入到单链表中。若f逻辑上位于a和e之间，则a、f、e的链接地址依次是（ ）。

A、1008H1010H1014H

B、1014H1010H1008H

C、1008H1014H1010H

D、1014H1008H1010H

3、将递归算法转变成对应非递归算法时，需要使用（ ）保存中间结果。

A、队列

B、栈

C、单链表

D、二叉树

5、已知程序如下：int S(int n){ return (n<=0)? 0: S(n-1)+n; }void main(){cout<<S(1); }程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（ ）。

A、main()→S(1)→S(0)

B、main()→S(0)→S(1)

C、S(1)→S(0)→main()

D、S(0)→S(1)→main()

6、一棵含有N个结点的树的所有结点的度数之和为（ ）。

A、N-1

B、N

C、N+1

D、2N

7、一棵具有520个结点的二叉树的高度为（ ）。

A、9

B、10

C、9~511

D、10~520

8、先序序列为a、b、c，后序序列为c、b、a的二叉树共有（ ）棵。

A、1

B、2

C、3

D、4

9、对序列{90，32，-5，0，41，22，5，9，10，8}采用希尔排序，下列序列（ ）是增量为4的一趟排序结果。

A、10，8，-5，0，41，22，5，9，90，32

B、-5，0，32，90，5，9，22，41，8，10

C、32，90，-5，0，22，41，5，9，8，10

D、以上都不对

1、试题答案：C

试题解析：

选项A的操作（Operation）指对数据的操作，例如插入、删除、修改、查询等。操作是对数据的一种处理方式。
选项B的数据对象（Data Object）指的是在某种抽象数据类型（Abstract Data Type，ADT）中定义的具体对象，例如在整型数组这种抽象数据类型中，数组就是一个具体的数据对象。选项C的结构（Structure）是数据对象中各个数据元素之间的关系。例如，在树形结构中，每个节点都有父节点和子节点，这些关系就构成了树形结构。选项D的数据集合（Data Set）是指具有某种特定规律的数据元素的集合，它们在某种程度上具有一定的关系。例如在整数集合{1, 2, 3, 4, 5}中，元素之间的关系是它们都是整数，并且它们是有限的，它们构成了一个数据集合。故本题选C。

2、试题答案：B

试题解析：

在将元素f插入单链表中时，需要找到f要插入的位置，这里规定f要插入到元素a和e之间。可以先找到a的结点，然后根据a的链接地址找到e的结点，最后在a的后面插入f即可。因此，将f插入到a和e之间需要修改a结点的链接地址为1014H，f结点的链接地址为1010H，e结点的链接地址为1008H。故本题选B。

3、试题答案：B

试题解析：

将递归算法转化为对应的非递归算法时，通常需要使用栈来保存中间结果。因为递归的本质就是函数调用的栈，所以使用栈可以较好地模拟递归的过程。故本题选B。

5、试题答案：A

试题解析：

程序运行时首先调用S(1)，然后S(1)会调用S(0)，最后S(0)的返回值返回到S(1)，再由S(1)返回到main()。因此，调用信息自栈底到栈顶的顺序是main()→S(1)→S(0)。故本题选A。

6、试题答案：A

试题解析：

树中每个结点除了根结点外都有一个父结点，因此所有结点的度数之和等于所有结点的父结点的数量。总共有N-1个父结点，因此所有结点的度数之和为N-1。故本题选A。

7、试题答案：D

试题解析：

当这棵二叉树是一棵完全二叉树时，此时高度最小，为log₂520+1≈10。当每层只有一个结点时，此时高度最大，为520。故本题选D。

8、试题答案：D

试题解析：

（1）当中序序列是a、b、c时，根据先序序列和中序序列构造的二叉树如下图(a)所示。对应的后序序列为c、b、a；
（2）当中序序列是a、c、b时，根据先序序列和中序序列构造的二叉树如下图(b)所示。对应的后序序列为c、b、a；
（3）当中序序列是b、a、c时，根据先序序列和中序序列构造的二叉树如下图(c)所示。对应的后序序列为b、c、a；
（4）当中序序列是b、c、a时，根据先序序列和中序序列构造的二叉树如下图(d)所示。对应的后序序列为c、b、a；
（5）当中序序列是c、a、b时，无法构造二叉树；
（6）当中序序列是c、b、a时，根据先序序列和中序序列构造的二叉树如下图(e)所示。对应的后序序列为c、b、a；

故本题选D。

9、试题答案：A

试题解析：

增量为4的希尔排序将原序列分为4个子序列，分别是{90，41，10}，{32，22，8}，{-5，5}和{0，9}。对这四个子序列进行插入排序，排序结果分别是{10，41，90}，{8，22，32}，{-5，5}和{0，9}。将四个子序列合并，得到新序列{10，8，-5，0，41，22，5，9，90，32}。故本题选A。