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

一、单项选择题

1． 假定不采用Cache 和指令预取技术, 且机器处于“开中断”状态, 则在下列有关指令执行的叙述中, 错误的是（ ）。.

A. 每个指令周期中CPU 都至少访问内存一次

B. 每个指令周期一定大于或等于一个CPU 时钟周期

C. 空操作指令的指令周期中任何寄存器的内容都不会被改变

D. 当前程序在每条指令执行结束时都可能被外部中断打断

【答案】C

【解析】本题涉及的概念比较多。首先, 如果不采用Cache 和指令预取技术, 每个指令周期中至少要访问内存一次, 即从内存中取指令。其次, 指令有的简单有的复杂, 每个指令周期总大于或等于一个CPU 时钟周期。第三, 即使是空操作指令, 在指令周期中程序计数器PC 的内容也会改变(PC值加“1”) , 为取下一条指令做准备。第四, 如果机器处于“开中断”状态, 在每条指令执行结束时都可能被新的更高级的中断请求所打断。所以应选择选项C 。

2． 单级中断系统中, 中断服务程序内的执行顺序是（ ）。

Ⅰ保护现场; Ⅱ开中断; Ⅲ关中断; Ⅳ保存断点; Ⅴ中断事件处理; Ⅵ恢复现场; Ⅶ中断返回 A. B. C. D.

【答案】A

【解析】程序中断有单级中断和多级中断之分, 单级中断在CPU 执行中断服务程序的过程中不能被打断, 即不允许中断嵌套。保存断点与关中断的任务是由硬件(中断隐指令) 完成的, 所以在单级中断系统中, 中断服务程序内应完成的任务有:

①保存现场; ②中断事件处理; ③恢复现场; ④开中断; ⑤中断返回。

3． 若某文件系统索引结点(inode)中有直接地址项和间接地址项, 则下列选项中, 与单个文件长度无关的因素是（ ）

A. 索引结点的总数

B. 间接地址索引的级数

C. 地址项的个数

D. 文件块大小

【答案】A

【解析】根据文件长度与索引结构的关系可知, 只有选项A 是与单个文件长度无关的。

4． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。

A.(100, 80, 90, 60, 120, 110, 130)

B.(100, 120, 110, 130, 80, 60，90)

C.(100, 60, 80, 90, 20, 110, 130)

D.(100, 80, 60, 90, 120, 130, 110)

【答案】C

【解析】二叉排序树:左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。

5． 对一组数据(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

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

6．

对个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中, 错误的是（ ）。

A. 该树一定是一棵完全二叉树

B. 树中一定没有度为1的结点

C. 树中两个权值最小的结点一定是兄弟结点

D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值

【答案】A

【解析】哈夫曼树为带权路径长度最小的二叉树, 但不一定是完全二叉树, 选项A 错误; 哈夫曼树中没有度为1的结点, 选项B 正确; 构造哈夫曼树时, 最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树, C 正确; 哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和, 其权值不小于其左右子树根结点的权值, 在与结点P 的左右子树根结点处于同一层的结点中, 若存在权值大于结点P 权值的结点Q , 那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树, 由此可知, 哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。

7． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中, 正确的是（ ）。

A. 递归次数与初始数据的排列次序无关

B. 每次划分后, 先处理较长的分区可以减少递归次数

C. 每次划分后, 先处理较短的分区可以减少递归次数

D. 递归次数与每次划分后得到的分区的处理顺序无关

【答案】D

【解析】快速排序是递归的, 递归过程可用一棵二叉树给出, 递归调用层次数与二叉树的深度一致。例如:待排序列{48, 62, 35, 77, 55, 14, 35, 98) , 采用快速排序方法, 其对应递归调用过程的二叉树如下图所示。

图

在最坏情况下, 若初始序列按关键码有序或基本有序时, 快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关, 即先处理较长的分区或先处理较短的分区都不影响递归次数。

8． 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。

A. 线性表的顺序存储结构

B. 队列

C. 线性表的链式存储结构

D. 栈

【答案】D