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

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

1、在顺序存储的线性表（a1，a2，...，an）中，删除一个元素的平均移动次数为（ ）。

A、n/2

B、(n-1)/2

C、(n+1)/2

D、n

2、设栈S和队列Q的初始状态均为空，元素1，2，3，4，5，6依次进入栈S。若每个元素出栈后立即进入队列Q，且6个元素出队的顺序是2，4，3，6，5，1，则栈S的容量至少是（ ）。

A、4

B、3

C、2

D、1

3、图的广度优先搜索遍历要用到（ ）数据结构。

A、顺序表

B、线性链表

C、堆栈

D、队列

4、对于有N个结点的完全二叉树（结点编号为1到N），当2*K<=N时，编号为K的结点的左子女编号为（ ）。

A、2*K

B、2*K+1

C、2*K+2

D、K+2

5、队列操作的特点是（ ）。

A、先进先出

B、后进先出

C、顺序存储

D、用于递归实现

6、含有11个结点的完全二叉树中，度为1的结点个数为（ ）。

A、0

B、1

C、2

D、5

7、对于三个结点A、B、C，可构成（ ）不同形态的二叉树。

A、4

B、5

C、30

D、6

8、当初始序列已按键值有序，则用简单选择排序算法对其进行排序，需要进行的比较次数为（ ）。

A、N²

B、N-1

C、N*log₂N

D、N*(N-1)/2

1、试题答案：B

试题解析：

在顺序存储的线性表中，删除一个元素需要将该元素之后的所有元素向前移动一位。设删除的元素在位置i（1≤i≤n），则移动的次数为n-i。对于任意的i，该元素被删除的概率为1/n，因此平均移动次数为((n-1)+(n-2)+...+1+0)/n=(n-1)/2。故本题选B。

2、试题答案：B

试题解析：

栈的执行过程为1进栈、2进栈、2出栈、3进栈、4进栈、4出栈、3出栈、5进栈、6进栈、6出栈、5出栈、1出栈，因此操作过程中栈中元素个数最多时为3个。故本题选B。

3、试题答案：D

试题解析：

队列的特点是先进先出（FIFO），即先加入队列的元素先被取出。在图的广度优先搜索中，我们需要先访问与起始顶点直接相连的所有顶点，然后才能访问与这些顶点相连的其他顶点。因此，我们需要使用队列来存储待访问的顶点，以保证先访问与起始顶点相邻的顶点。故本题选D。

4、试题答案：A

试题解析：

对于编号为K的结点，其左子节点的编号应该是2K，右子节点的编号应该是2K+1。故本题选A。

5、试题答案：A

试题解析：

队列是一种数据结构，它具有先进先出（First In First Out，FIFO）的特点，即先进入队列的元素先被取出，后进入队列的元素后被取出。故本题选A。

6、试题答案：A

试题解析：

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

7、试题答案：B

试题解析：

对于三个结点A、B、C，可构成5棵不同的二叉树。具体形态如下图所示。

8、试题答案：D

试题解析：

简单选择排序的基本思路是在待排序的序列中选择最小的元素，将其与序列的第一个元素交换位置，然后在剩下的元素中选择最小的元素，将其与序列的第二个元素交换位置，以此类推，直到整个序列有序。当初始序列已按键值有序时，并不会影响比较次数。第i次选择最小元素时，不需要对前i-1个元素进行比较，只需比较第i个元素与后面的元素，这样每一次选择最小元素时只需比较n-i次，共需要比较1+2+...+n-1=(n-1)n/2次，即N(N-1)/2次比较。故本题选D。