2016年南京航空航天大学科技信息研究所589情报学应用技术基础综合之数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。
A. 数据元素过多 B. 负载因子过大 C. 哈希函数选择不当 D. 解决冲突的算法选择不好 答:D
【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。
2． 在一个文件被用户进程首次打开的过程中，操作系统需做的是（ ）
A. 将文件内容读到内存中 B. 将文件控制块读到内存中 C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程 答:B
【解析】概念
3． 某计算机有五级中断的顺序为
A.11110 B.01101 C.00011 D.01010 答:D
【解析】由于需要对
4． 数据序列结果。
A. 选择排序 B. 起泡排序
第 2 页，共 43 页
中断屏蔽字为则
表示对级中断进行
屏蔽。若中断响应优先级从高到低的顺序是且要求中断处理优先级从高到低
的中断处理程序中设置的中断屏蔽字是（ ）。
B
排除掉。的中断处理优先级下降，屏蔽字中需要3个0, 所以可以将选项A 、开放，所以相应位应该为
即为01010。
只能是下列排序算法中的（ ）的两趟排序后的
C. 插入排序 D. 堆排序 答:C
【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。
5． 下列选项中，操作系统提供的给应用程序的接口是（ ）。
A. 系统调用 B. 中断 C. 库函数 D. 原语 答:A
【解析】操作系统提供给用户应用程序的接口只有两种：命令输入和系统调用。其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口复杂调用（例如多种
，
以及包含在）
自然命令用户接口
等，而系统调用中除了常规的一些传统的系统调用（例如read （ ））以外，还有经过扩展的
库中的各种封装好的过程调用（最终都是通过系统调
用陷入到操作系统中去的）等。
6． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个 答:C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
7． 若某通信链路的数据传输速率为
A.600波特 B.1200波特 C.4800波特 D.9600波特 答:B
【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系：B = 2xH （Baud ）, 而奈奎斯特公式一无噪信道传输能力公式是
第 3 页，共 43 页
采用4相位调制，则该链路的波特率是（ ）。
N 为一个码元所取的离散值个数。从
而可以得到波特率与数据传输速率的关系，即在本题中数据传输速率C = 2400,
N=4，因此波特率是1200, 答案是B 。
8． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
答:C
【解析】两个循环嵌套，那么语句x :=x＋l :
则被执行了次。
9． 设置当前工作目录的主要目的是（ ）。
A. 节省外存空间 B. 节省内存空间 C. 加快文件的检索速度 D. 加快文件的读/写速度 答:C
【解析】工作目录只是指出了当前操作的默认目录，使得在每次访问的时候不需要由根目录 一层一层地解析，在文件路径比较长时，可以节省许多解析的时间，从而加快了文件的检索速度。
10．在一株高度为2的5阶B 树中，所含关键字的个数最少是（ ）
A.5 B.7 C.8 D.14 答:A
【解析】根据B 树的定义可知，跟结点最少含有树最少有（5-1）+1=5个关键字，其中根节点含有
个关键字，高度为2的阶B
个关键字，第2层结点含有1关键字。
二、填空题
11．设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
答:23; 100CH
12．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
答
:
第 4 页，共 43 页
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的