当前位置：问答库＞考研试题

一、选择题

1． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（ ）。

A.12

B.20

C.32

D.33

【答案】B 。

【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的结点数是多少。表示深度为h 的平衡二叉树中含有的最少结点数，有

由此可得对应的平衡二叉树如下图所示。

2． 为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。

A. 顺序存储

B. 散列存储

C. 链式存储

D. 索引存储

【答案】A

【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。

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

A. 存储效率

B. 数列函数

C. 装填（装载）因子

D. 平均查找长度

【答案】D

【解析】哈希方法冲突会使在查找冲突的关键字时，还要根据冲突处理办法多次比较关键字，则直接影响了平均查找长度。

4． 先序序列为a , b ，c , d 的不同二叉树的个数是（ ）。

A.13

B.14

C.15

D.16

【答案】B

【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。本题中，结点a 为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bcd 为右子树；②b 为左子树，cd 为右子树；③bc 为左子树，d 为右子树；④bcd 为左子树，右子树为空。然后将左右子树继续分解，如第①种情况的右子树先序遍历（bcd ）可能有：a. 左子树为空，右子树为cd ; b. 左子树为c ，右子树为d ; c. 左子树为cd ，右子树为空。按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二叉树。

5． 和外存储器相比，内存储器的特点是（ ）。

A. 容量大，速度快，成本低

B. 容量大，速度慢，成本高

C. 容量小，速度快，成本高

D. 容量小，速度快，成本低

【答案】C

6． 假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack ）方式，则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。

A.146k

B.147K

C.148K

D.158K

【答案】B

【解析】Cache 和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache 的一个特定的块中。本题中，Cache 总共存放4K 字数据，块大小为4个字，因此cache 被分为4K/4=1K个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为

所以，Cache

的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容量为

：

7． 20世纪50年代，为了发挥_____的效率，提出了_____技术，从而发展了操作系统，通过它对_____进行管理和调度。（ ）

A. 计算机，操作系统，计算机

B. 计算，并行，算法

C. 硬设备，多道程序，硬软资源

D. 硬设备，晶体管，计算机

【答案】C

8． 若一棵二叉树的前序遍历序列为a ，e ，b , d ，c ，后序遍历序列为b ，c , d ，e , a ，则根结点的孩子结点（ ）.

A. 只有e

B. 有e 、b

C. 有e 、c

D. 无法确定

【答案】A 。

【解析】由题目可知，若一棵二叉树的前序遍历序列为a , e , b , d ，c , 后序遍历序列为b , c ，d ，e ，a ，其中a 为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e ，而后序遍历的倒数第二个结点为e ，说明a 的孩子结点只有e 。

9． —个C 语言程序在一台32位机器上运行。程序中定义了3个变量x 、Y 和z ，其中x 和z 为int 型，Y 为short 型。当x=127，Y=-9时，执行赋值语句z=x+Y后，x 、Y 和z 的值分别是 （ ）。

A.x=0000007FH，Y=FFF9H，z=00000076H

B.x=0000007FH，Y=FFF9H，z=FFFF0076H

C.x=0000007FH，Y=FFF7H，z=FFFF0076H

D.x=0000007FH，Y=FFF7H，z=00000076H

【答案】D

【解析】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”。例如，x 和z 为int 型，数据长32位，Y 为short 型，数据长16位，因此首先应将y 转换成32位的数据，然后再进行加法运算。

运算采用补码的形式，而x 的补码是0000007FH ，Y 的补码是FFFFFFF7H ，所以x+Y=00000076H。

10．进程P0和P1的共享变量定义及若进程P0和P1访问临界资源的类C 伪代码实现如下：