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

一、单项选择题

1． 对一组数据(2, 12, 16, 88, 5, 10) 进行排序, 若前三趟排序结果如下:

第一趟:2, 12, 16, 5, 10, 88

第二趟:2, 12, 5, 10, 16, 88

第三趟:2, 5, 10, 12, 16, 88

则采用的排序方法可能是（ ）。

A. 起泡排序

B. 希尔排序

C. 归并排序

D. 基数排序

【答案】A

【解析】题目中所给的三趟排序过程, 显然是使用起泡排序方法, 每趟排序时从前往后依次比较, 使大值“沉底”。希尔排序的基本思想是:先对序列进行“宏观调整”, 待序列中的记录“基本有序”时再进行直接插入排序。宏观调整的方法是:通过某种规则将大的待排序序列分割为若干小的待排序序列, 再依次对这些小的序列直接插入排序。宏观调整可以多次, 每次分割的序列数逐渐增多, 而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序列合并为一个大的有序序列, 然后“逐趙归并”, 直至整个序列为有序为止。基数排序是分配排序的一种, 这类排序不是通过关键字比较, 而是通过“分配”和“收集”过程来实现排序的。本题中, 很容易看出大值逐渐“沉底”, 显然使用的是起泡排序法。

2． 在含有n 个关键字的小根堆(堆顶元素最小) 中，关键字最大的记录有可能存储在（ ）位置上。 A. B.

C.1 D.

【答案】D

【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于Ln/2」的结点上。

3． 假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态(系统态) 的是（ ）。 A.

B.

C. ; 产生软中断 ; 寄存器R0的内容取非

D.MOVRO , addr ; 把地址处的内存数据放入寄存器RO 中

【答案】C

【解析】A 项, 除法操作出现除数为零的情况时, 会产生内中断, CPU 切换为内核态进行中断处理; B 项, 直接产生中断, 会切换到内核态; D 项, addr 出现非法地址, 会出现中断, 进而切换到内核态。

4． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。

A.4

B.5

C.6

D.7

【答案】C

【解析】设度为0的结点数为x ，则度为3的树总结点数n ＝度为0的结点数＋度为1的结点数＋度为2的结点数＋度为3的结点数＝x ＋2＋l ＋2＝x ＋5；从每个结点所指向的结点数的和的角度来计算度为3的树总结点数n ＝2×3＋1×2＋2×1＋1＝11。两种方法所计算出来的n 相等，所以x ＝6。

5． 某CPU 主频为

A.

B.

C.

D.

【答案】C

【解析】采用4级流水线执行100条指令, 在执行过程中共用

CPU 的主频是, 也就是说每秒钟有

条指令/秒,

故答案为C 。

6． 在任意一棵非空二叉排序树T1中, 删除某结点v 之后形成二叉排序树T2, 再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中, 正确的是（ ）

Ⅰ. 若v 是T1的叶结点, 则T1与T3不同

Ⅱ. 若v 是T1的叶结点, 则T1与T3相同

Ⅲ. 若v 不是T1的叶结点, 则T1与T3不同

, 采用4级指令流水线, 每个段的执行需要1个时钟周期。假定CPU 执行了100条指令, 在其执行过程中没有发生任何流水线阻塞, 此时流水线的吞吐率为（ ） 条指令/秒 条指令/秒 条指令/秒 条指令/秒 个时钟周期。 个时钟周期。流水线的吞吐率为

Ⅳ. 若v 不是T1的叶结点, 则T1与T3相同

A. 仅Ⅰ、Ⅲ

B. 仅Ⅰ、Ⅳ

c. 仅Ⅱ、Ⅲ

d. 仅Ⅱ、Ⅳ

【答案】C

【解析】在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中, 如果删除的结点是叶子结点那么在插入结点后, 后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点, 那么再插入这个结点后, 后来的二叉树可能发生变化, 不完全相同。

7． 下列线索二叉树中(用虚线表示线索) , 符合后序线索树定义的是（ ）。

【答案】D

【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息, 解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树, 左链域空, 无右子树, 右链域指向其后继结点b ; 结点b 无左子树, 左链域指向其前驱结点d ; 结点c 无左子树, 左链域指向其前驱结点b , 无右子树, 右链域指向其后继结点a 。所以正确选项为D 。

8． 某计算机采用微程序控制器, 共有32条指令, 公共的取指令微程序包含2条微程序, 各指令对应的微程序平均由4条微指令组成, 采用断定法(下址字段法) 确定下条微指令的地址, 则微指令中下址字段的位数至少是:（ ）

A.5

B.6

C.8

D.9

【答案】C 【解析】, ,

所以至少需要8位才能表示完130个地址。