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

一、选择题

1． 有

A.

B.

C.

D. 个分支结点的满二叉树的深度是（ ）。

【答案】C

【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树，所以非分支的结点总数为1，所以满二叉树共有个结点，所以满二叉树的深度为

2． 某数采用IEEE754单精度浮点数格式表示为C640 0000H, 则该数的值是（ ） A. B. C. D.

【答案】A

0000 0000 0000 0000, 转换为标准的格式为：

. 因此，浮点数的值为

3． 采用指令Cache 与数据Cache 分离的主要目的是（ ）

A. 减低Cache 的缺失损失

B. 提高Cache 的命中率

C. 减低CPU 平均访问时间

D. 减少指令流水线资源冲突

【答案】D

【解析】指令流水线不会断流，预取过来的都是指令

4． 下列不是设计一个“好”的算法应考虑达到的目标是（ ）。

A. 可行的

B. 健壮的

C. 无二义性的

D. 可读性好的

IEEE754单精度浮点数格式为C640 0000H表示为二进制格式为1100 0110 0100 0000 【解析】

【答案】A

【解析】设计一个“好”的算法应考虑以下目标：正确性；可读性；健壮性；效率和低存储量需求。可行性是算法的五个基本特征之一，不是一个好的算法该达到的目标。

5． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。

A. 选择排序法B. 插入排序法C. 快速排序法D. 堆排序法

【答案】A

【解析】选择排序的基本思想是：

第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录

和

6． 已知循环队列存储在一维数组

rear 的值分别是（ ）。

A.0, 0

B.0, n-1

C.n-1, 0

D.n-1, n-1

【答案】B

【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，且要求第1 个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。

7． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。

【答案】D

【解析】二叉树结点总数分别代表度为0，度为1，度为2的结点数）。

所

以因

此又在非空二叉树中

：且本题所给树为正则二叉树

，

8． 下列关于最小生成树的叙述中，正确的是（ ）。 分别变为新的有序区和新的无序区。 中，且队列非空时front 和rear 分别指向队头元素和和该趟排序交换，使

将它与无序区的第1个记录队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和

I . 最小生成树的代价唯一 II. 所有权值最小的边一定会出现在所有的最小生成树中III. 使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树一定相同IV. 使用普里姆算法和克鲁斯卡尔（Kruskal ）算法得到的最小生成树总不相同

A. 仅I

B. 仅II

C. 仅 I 、III

D. 仅 II 、IV

【答案】A 。

【解析】当图中存在相同权值的边时，其最小生成树可能是不唯一的，但最小生成树的代价

所以说法I 正确。一定是相同的，从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路，

所以说法II 错误。当某个顶点有权值相同的边，使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树并不一定相同，所以说法III 错误。当最小生成树不唯一时，使用普里姆算法和克鲁斯卡尔（Krnskal ）算法得到的最小生成树可能相同，也可能不同，所以说法IV 错误。由此可得出正确答案。

9． 在页式存储管理系统中，采用某些页面置换算法，会出现Belady 异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady 异常现象的是（ ）。

I . LRU 算法

A. 仅 II

B .仅 I II

C. 仅I III

D. 仅 II III

【答案】A

【解析】Belady 现象只有FIFO 算法才会出现

10．用邻接表存储图所用的空间大小（ ）。

A. 与图的顶点数和边数都有关 B. 只与图的边数有关

C. 只与图的顶点数有关 D. 与边数的平方有关

【答案】A

【解析】邻接表就是对图G 中的每个顶点Vi 建立一个单链表，第i 个单链表中的结点表示依附于顶点V i 的边，这个单链表就称为顶点Vi 的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。

II. FIFO 算法 III. OPT 算法

二、判断题

11．平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（ ）

【答案】×

【解析】平衡因子定义为该结点的左子树的深度减去右子树的深度，一个平衡二叉树中，某节点的左右孩子的平衡因子为0，说明左孩子的左子树和右子数的深度相同，而且右子树的左子树和右子数的深度相同，但这不能说明该节点的左子树和右子树的深度相同。