2017年常州大学信息学院、数理学院858数据结构考研强化模拟题
● 摘要
一、选择题
1． 下列选项中，属于多级页表优点的是（ ）
A .加快地址变换速度 B. 减少缺页中断次数 C. 减少页表项所占字节数 D. 减少页表所占的连续内存空间 【答案】D
【解析】多级页表避免了把所有的页表一直保存在内存中
2． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257 B.258 C.384 D.385 【答案】C
【解析】由
：_
则
和
_
_可知
，
即
显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个
性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
3． 4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7 B.-8 C.15 D.16
【答案】C
【解析】Hanoi 问题总移动次数为：次。
4． 若数据元素序列11, 12, 13, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。
A. 起泡排序 B. 插入排序 C. 选择排序 D. 二路归并排序 【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确。
5． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。
【答案】D
【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。
6． 已知关键字序列5, 8, 12, 19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。
A.3, 5，12，8, 28，20, 15，22，19 B.3, 5, 12, 19, 20, 15, 22, 8, 28 C.3, 8, 12, 5, 20, 15, 22, 28, 19 D.3, 12, 5, 8, 28, 20, 15, 22, 19
【答案】A
【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）〜（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。
7． 在请求分页系统中，页面分配策略与页面置换策略不能组合使用的是（ ）。
A. 可变分配，全局置换 B. 可变分配，局部置换 C. 固定分配，全局置换 D. 固定分配，局部置换 【答案】
【解析】分配和置换策略有下面三个组合：①固定分配、局部置换；②可变分配、全局置换；，或根据程序员、③可变分配、局部置换。固定分配是指基于进程的类型（交互型或批处理型等）
程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间都不再改变，采用该策略时，如果进程在运行中发现缺页，则只能从该进程在内存的n 个页面中选出一个页换出，然后再调入一页，才能保证分配给该进程的内存空间不变，因此不能有固定分配，全局置换组合。
8． 偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是（ ）。
A. 间接寻址 B. 基址寻址 C. 相对寻址 D. 变址寻址 【答案】A
【解析】在四种不同的寻址方式中，间接寻址按指令的形式地址从主存中取出操作数的有效地址，然后再按此有效地址从主存中读出操作数。其余三种寻址方式可以统称为偏移寻址。
9． n 个结点的完全有向图含有边的数目（ ）。
A.n*n
B.n （n+l）
相关内容
相关标签