2017年青岛大学信息工程学院910数据结构考研冲刺密押题
● 摘要
一、选择题
1． —
组记录的关键码为
准得到的一次划分结果为（ ）。
【答案】C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为一次划分结束。
2． 下列程常段的时间复杂度是（ ）
A.
B.
C.
D. 【答案】C
【解析】外部循环的退出条件是内部循环的退出条件是
而对于k ，每次循环都执行
所以循环次数为
对于j ，每次循环都执行
所以每次循环次数为n 次。所以此程序
则利用快速排序的方法，以第一个记录为基
段的时间复杂度为O 即选C 。
3． 分区分配内存管理方式的主要保护措施是（ ）。
A. 界地址保护 B. 程序代码保护
C. 数据保护 D. 栈保护 【答案】A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护。通常的界地址保护方法采用软硬件结合的方法。考生要注意本题与虚拟存储方法的区别。
4． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个 【答案】C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
5． 广义表
【答案】D
head 操作就是得到广义表中第一个的原子。【解析】
操作就是得到除第一个原子外剩下元
素构成的表。也就是toil 得到的元素需要在外层再加一个（ ）。
6． 下列二叉排序树中查找效率最高的是（ ）。
A. 平衡二叉树 B. 二叉查找树
C. 没有左子树的二叉排序树 D. 没有右子树的二叉排序树 【答案】A
【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。这就保证了二叉树的深度是
级别的。二叉查找树或者是一颗空数；或者是具有下列性质的二叉树：①若左子树不
空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。B 、C 、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1，甚至很大，因此查找效率低。
则式子
的值为（ ）。
7． 若一个用户进程通过read 系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（ ）。
I. 若该文件的数据不在内存，则该进程进入睡眠等待状态；II. 请求read 系统调用会导致CPU 从用户态切换到核心态；III. read系统调用的参数应包含文件的名称
A. 仅 I 、II B. 仅 I 、III C. 仅 II 、III D.I 、II 和III 【答案】A
，原进程【解析】对于I ，当所读文件的数据不再内存时，产生中断（缺页中断、缺段中断），直到所需数据从外村调入内存后，将该进程唤醒，使其变为就绪进入睡眠等待状态（阻塞状态）
状态。对于II , read系统调 用CPU 将从用户态切换到核心态，从而获取操作系统提供的服务。对于III ，在操作系统中，要读一个文件首先要open 系统调用将该文件打开。Open 系统调用的参数需要包含文件的路径名与文件名，而read 系统调用只需使用open 返回的文件描述符，并不使用Read 系统调用要求用户提供三个输入参数：文件名作为参数。①文件描述 符；②buf 缓冲区首址；③传送的字节数n 。read 系统调用的功能是试图从fd 所指示的文件中读入n 个字节的数据，并将它们送至由指针buf 所指示的缓冲区中。
8． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 【答案】D
9． 在虚拟存储管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（ ）。
A. 编辑 B. 编译 C. 链接 D. 装载 【答案】B
【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本，不涉及到任何与计算机运 行相关的事；编译是由编译程序将用户源代码编译成若干个目标模块，源地址编译成目标程序时，会形成逻辑地址；链接是由链接程序将编译后形成的一组目标模块，以及所需库函数链接，形成完整的装入模块；装入是由装入程序将装入模块装入内存。