2016年河南科技大学信息工程学院数据结构考研复试题库
● 摘要
一、选择题
1． 若某文件系统索引结点（inode ）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是（ ）
A. 索引结点的总数
B. 间接地址索引的级数
C. 地址项的个数
D. 文件块大小
答:A
【解析】根据文件长度与索引结构的关系可知，只有选项A 是与单个文件长度无关的。
2． 若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（ ）。
A. 在进程结束时能进行处理机调度
B. 创建新进程后能进行处理机调度
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度
答:C 。
【解析】对于A 、B 、D 显然是可以进行处理机调度的，对于C , 当进程处于临界区时，只要不破坏临界资源的使用规则，是不会影响处理机调度的，比如，通常访问临界资源可能是慢速的
，如果在进程访问打印机时，不能处理机调度，那么系统的性能将是非常低的。外设（如打印机）
几种不进行处理机调度的情况如下：①在处理机中断的过程中；②进程在操作系统内核程序临界区中；③其他需要完全屏蔽中断的原子操作过程中。
3． 数据序列只能是下列排序算法中的（ ）的两趟排序后的结果。
A. 选择排序
B. 起泡排序
C. 插入排序
D. 堆排序
答:C
【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。
4． 设X 是树T 中的一个非根结点，B 是T 所对应的二叉树。在B 中，X 是其双亲的右孩子，下列结论正确的是（ ）。
A. 在树T 中，X 是其双亲的第一个孩子
B. 在树T 中，X —定无右兄弟
C. 在树T 中，X —定是叶结点
D. 在树T 中，X —定有左兄弟
答:D
【解析】由树和二叉树的转换关系可知，X 一定有左兄弟，X 是其双亲的第二个孩子，不能确定在树T 中，X 是否有右兄弟，是否是叶结点。
5． 4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7
B.-8
C.15
D.16
答:C
【解析】Hanoi 问题总移动次数为：次。
6． 数组通常具有的两种基本操作是（ ）。
A. 查找和修改
B. 查找和索引
C. 索引和修改
D. 建立和删除
答:A
【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据数组的性质，数组通常具有的两种基本运算是排序和查找。
7． —个栈的入栈序列为其出栈序列是
的个数是（ ）
A.n-3
B.n-2
C.n-1
D. 无法确定
答:C
【解析】除了3本身以外，其他的值均可以取到，因此可能取值的个数为n-1。
8． 下列选项中，属于多级页表优点的是（ ）
A .加快地址变换速度
若，则则可能取值