2017年北京邮电大学软件学院807软件工程专业综合考研冲刺密押题
● 摘要
一、选择题
1． 用直接插入排序方法对下面4个序列进行排序
，（由小到大）元素比较次数最少的是（ ）。
【答案】C
2． 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。
【答案】D
【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息，解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b ; 结点b 无左子树，左链域指向其前驱结点山结点c 无左子树，左链域指向其前驱结点b ，无右子树，右链域指向其后继结点a 。所以正确选项为D 。
3． 采用简单选择排序，比较次数与移动次数分别为（ ）。
【答案】C
【解析】简单选择排序只在要交换的时候交换位置，及移动位置，共需移动n 次。而需要比较的次数为
4． 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为2字节，逻辑地址结构为：
字节，页表项大小为
逻辑地址空间大小为（ ）。
A.64 B.128 C.256 D.512
【答案】B
【解析】地址空间分为逻辑地址空间和物理地址空间。页的大小为采用二级页表，
一页可存放要
个页面来保存页表项，故本题答案为B 。
字节，页表项大小为2B ，
字节，故最少需
’个页表项，本题中逻辑地址空间大小为
页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是
5． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4 B.5 C.6 D.7
【答案】C
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个全二叉树的高度为
叉树的高度为
6． 若
A.x+y B.-x+y C.x-y D.-x-y
【答案】C
或
或
结点的完
由完全二叉树类推到完全三叉树可知，n 个结点的完全三
则下列表达式采用8位定点补码运算实现时，会发生溢出的是（ ）
【解析】8位定点补码能表示的数的范围为：
A 结果为78, B结果为-128, D结果为-78都在此范围内，只有C 结果128超过了8位定点补码能表示的数的范围，会发生溢出
7． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
【答案】C
【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
8． 处理外部中断时，应该由操作系统保存的是（ ）。
A. 程序计数器（PC ）的内容 B. 通用寄存器的内容 C. 快表（TLB ）的内容 D.Cache 中的内容 【答案】B
【解析】外部中断处理过程首先要保护现场，使得中断处理完后能够恢复程序的状态继续执；②由中断服务程序保行。保护现场有两个含义：①由中断隐指令保存程序的断点（程序计数器）存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
9． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进栈，然后再出栈。从中可以看出，push 的数目始终大于等于pop 的数目。
10．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序 B. 起泡排序 C. 简单选择排序 D. 快速排序 【答案】A
【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需
趟排序，也即时间复杂度仍为
而对
简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即间复杂度为0（nlog2n ）
n-1趟，
比较的时间复杂度由 降至
11．现有容量为10GB 的磁盘分区，磁盘空间以簇（cluster ）为单位进行分配，簇的大小为4KB , 若采用位图法管理该分区的空闲空间，即用一位（bit ）标识一个簇是否被分配，则存放该位图所需簇的个数为（ ）
A.80 B.320 C.80K D.320K 【答案】A