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

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

1、当执行函数时，其局部变量的存储一般采用（）进行存储。

A、静态链表

B、栈结构

C、队列结构

D、树形结构

2、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A、n

B、2n-1

C、2n

D、n-1

4、若A中有1000个元素，如果仅要求选出其中最大的5个元素，则采用（）排序方法最省时间。

A、起泡排序

B、快速排序

C、简单选择排序

D、希尔排序

5、设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数为（）。

A、n+1

B、m-n

C、m-n-1

D、无法确定

6、向一棵m阶B-树进行关键字插入，当结点的关键字数目在插入之前为（）时，插入关键字时需要分裂该结点。

A、m

B、m-1

C、m+1

D、m-2

7、有二维数组B[1...20,0...5]按行优先顺序存放，设B[1,0]的存储地址为300，每个元素占3个存储单元，则B[3,2]的地址是（）。

A、336

B、330

C、345

D、342

8、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用（）的方法。

A、分块

B、二分法

C、顺序

D、基于属性

9、若一棵度为3的树T中，有x个度为1的结点，y个度为2的结点，z个度为3的结点，则该树有（）个叶结点。

A、1+2y+3z

B、x+2y+3z

C、2y-3z

D、1+y+2z

10、一组记录的关键字为{46，79，56，38，40，84}，则利用快速排序方法，以第一个记录为枢轴得到的一次划分结果为（）。

A、38，40，46，56，79，84

B、40，38，46，79，56，84

C、40，38，46，56，79，84

D、40，38，46，84，56，79

1、试题答案：B

试题解析：

当执行函数时，其局部变量的存储一般采用栈结构进行存储。函数执行时，系统会为其分配一段连续的栈空间，用于存储函数的局部变量、参数、返回地址等信息。每当函数被调用时，系统会将其活动记录（activation record）压入栈顶，当函数执行结束后，会从栈顶弹出该活动记录，释放栈空间。因为栈结构的特点是先进后出，因此可以很方便地记录函数调用的嵌套关系，同时也保证了局部变量的作用域和生命周期。故本题选B。

2、试题答案：A

试题解析：

当将两个有序表合并为一个有序表时，具体来说，从两个有序表中各取一个元素比较大小，较小的元素放入新表中，同时将该元素所在的表的指针向后移动一位，重复此过程直到某一个表遍历完毕。最后，将未遍历完毕的表中的元素直接复制到新表中。当其中一个有序表的最大元素小于另一个有序表的最小元素时，此时比较次数为少，为n。故本题选A。

4、试题答案：A

试题解析：

起泡排序（Bubble Sort）是一种基本的排序算法，它的基本思想是对于相邻的两个元素，如果它们的顺序错误，则交换它们的位置，直到没有再需要交换的元素为止。因此需要进行5趟起泡排序即可以选出其中最大的5个元素。最好情况下可能一趟起泡排序即可以选出其中最大的5个元素，因此起泡排序相较于简单选择排序会更好。故本题选A。

5、试题答案：B

试题解析：

森林F对应的二叉树B中有m个结点，根为p，右子树结点个数为n，则左子树结点个数为m-1-n，因为二叉树的性质，左子树的结点数就是森林F中第一棵树的结点数，即m-1-n+1=m-n。故本题选B。

6、试题答案：B

试题解析：

在m阶B-树中，每个结点最多有m-1个关键字，每个结点最多有m个子节点。当要向一个结点插入关键字时，如果该结点的关键字数目小于m-1，则可以直接将关键字插入该结点中。但如果该结点已经有了m个关键字，则必须将该结点分裂成两个结点，同时将一个关键字上推到该结点的父节点中，以保证父节点的关键字数目不超过m-1。因此，当一个结点的关键字数目为m-1时，插入一个新的关键字需要进行结点的分裂操作。故本题选B。

7、试题答案：D

试题解析：

按行优先存储时，先存储第一行，再存储第二行，以此类推。因此，B[3][2]的地址为=300+3*(3-1)*6+3*2=342。故本题选D。

8、试题答案：A

试题解析：

分块查找确实可以在较快的时间内进行查找，并且适应于动态变化的要求。在分块查找中，将线性表划分为若干个块，每个块内部元素有序，不同块之间元素大小顺序不要求。同时，在块内进行顺序查找，在块间进行二分查找，从而达到快速查找和适应动态变化的目的。故本题选A。

9、试题答案：D

试题解析：

10、试题答案：C

试题解析：

以第一个记录46为枢轴，进行一次划分的过程如下：
（1）将84与46比较，84比46大，将79放在右边；
（2）将40与46比较，40比46小，将40放在左边；
（3）将79与46比较，79比46大，将79放在右边；
（4）将38与46比较，38比46小，将38放在左边；
（5）将56与46比较，56比46大，将56放在右边。
划分结果为：{40，38，46，56，79，84}。故本题选C。