2017年太原理工大学软件学院833数据结构和计算机组成原理考研冲刺密押题
● 摘要
一、选择题
1． 下列关于RISC 的叙述中，错误的是（ ）。
A.RISC 普遍采用微程序控制器
B.RISC 大多数指令在一个时钟周期内完成
C.RISC 的内部通用寄存器数量相对CISC 多
D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少
【答案】A
【解析】B 项、C 项、D 项都是RISC 的特点之一，所以它们都是正确的，只有A 项是CISC 的特点，因为RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器。
2． 在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37 所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48
B.24、48
C.24、53
D.24、90
【答案】C
【解析】题目中，插入48以后，树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL （先右后左）型平衡旋转，需做两次（先右旋后左旋转）旋转操作。过程如下图所示：
显然，在调整后的新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是24, 53。
3． 对一组数据（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
【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次
，待序列中的记录“基比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”
本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐増多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序
，直至整个序列为有序为止。 基数排序是分配排列合并为一个大的有序序列，然后“逐趟归并”
序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。 本
，显然使用的是起泡排序法。 题中，很容易看出大值逐渐“沉底”
4． 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A. 逻辑设备名
B. 物理设备名
C. 主设备号
D. 从设备号
【答案】A
【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作系统内部管理设备使用的是设备编号。
5． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
【答案】A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语句
6． 下列选项中，不能构成折半查找中关键字比较序列的是（ ）。
A.500，200，450，180
B.500，450，200，180
C.180，500，200，450
D.180，200，500，450
【答案】A
【解析】折半查找的过程是：先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足：对每一个关键字，其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A 项错误，第三次比较的关键字为450，说明待查关键字位于200〜450间，所以第四次比较时不会遇到关键字180。
7． 已知三叉树T 中6个叶结点的权分别是2，3, 4, 5，6，7, T的带权（外部）路径长度最小是（ ）
A.27
B.46
C.54
D.56
【答案】B
【解析】利用三叉树的6个叶子结点的权构建最小带权生成树，
最小的带权路径长度为
8． 用邻接表存储图所用的空间大小（ ）。
A. 与图的顶点数和边数都有关 B. 只与图的边数有关
C. 只与图的顶点数有关 D. 与边数的平方有关
【答案】A
【解析】邻接表就是对图G 中的每个顶点Vi 建立一个单链表，第i 个单链表中的结点表示依附于顶点V i 的边，这个单链表就称为顶点Vi 的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。
，则有设其执行时间为T （n ）