2017年沈阳航空航天大学计算机学院805数据结构考研强化模拟题
● 摘要
一、选择题
1． 下列选项中，能引起外部中断的事件是（ ）。
A. 键盘输入
B. 除数为0
C. 浮点运算下溢
D. 访存缺页
【答案】A
【解析】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断。
2． 某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90ns 、80ns 、70ns 和60ns , 则该计算机的CPU 时钟周期至少是（ ）。
A.90ns
B.80ns
C.70ns
D.60ns
【答案】A
【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU 时钟周期应当以最长的功能段执行时间为准。
3． 在参考摸型中，下列功能需由应用层的相邻层实现的是（ ）
A. 对话管理
B. 数据格式转换
C. 路由选择
D. 可靠数据传输
【答案】B
【解析】应用层的相邻层即为表示层，表示层负责管理数据的压缩、加密与解密、格式装换等，故答案为B 。
4． 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3, 当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）
A.1和5
B.2和4
C.4和2
D.5和1
【答案】B
【解析】入队操作的主要步骤
：
个后
，
加入一个后，再加入一删除一个后
，出队操作的主要步骤
：
5． 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继
B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱
D. 后序线索二叉树中求后序后继
【答案】D
【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。
6． 对一组数据（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
【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次
，待序列中的记录“基比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”
本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐増多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序
，直至整个序列为有序为止。 基数排序是分配排列合并为一个大的有序序列，然后“逐趟归并”
序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。 本
，显然使用的是起泡排序法。 题中，很容易看出大值逐渐“沉底”
7．
用户程序发出磁盘请求后，系统的处理系统的处理流程是：用户程序一系统调用处理程序一设备骆动程序一中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的，所以答案选C 。
8． 某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU
执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）
A.
B.
C.
D.
【答案】C
【解析】采用4级流水线执行100条指令，在执行过程中共用
条指令/秒，故答案为C 。
9． 稀疏矩阵一般的压缩存储方法有两种，即（ ）。
A. 二维数组和三维数组
B. 三元组和散列
C. 三元组和十字链表
D. 散列和十字链表
【答案】C
【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组（行标，列标，值）。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。
10．对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是:（ ）
A.05，46，13，55，94，17，42
B.05，13，17，42，46，55.94
C.42，13，94，05，55，46，17
D.05，13，46，55，17，42，94
【答案】C
【解析】基数排序有两种：最低位优先和最高位优先。
最低位优先的过程
先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向
条指令/秒
条指令/秒
条指令/秒
条指令/秒 个时钟周期。CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率
为
相关内容
相关标签