2018年南昌大学信息工程学院894数据结构[专业硕士]考研核心题库
● 摘要
一、单项选择题
1． 哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。
A. 哈希函数
B. 除余法中的质数
C. 冲突处理
D. 哈希函数和冲突处理
【答案】D
【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
2． 先序序列为a , b , c , d 的不同二叉树的个数是（ ）。
A.13
B.14
C.15
D.16
【答案】B
【解析】二叉树的先序遍历定义为:若二叉树为空, 则空操作; 否则, 访问根节点, 然后先序遍历左子树, 最后先序遍历右子树。本题中, 结点a 为二叉树的根节点, 左右子树的先序遍历可能存在下面四种情况:
①左子树为空, bcd 为右子树; ②b 为左子树, cd 为右子树; ③bc 为左子树, d 为右子树; ④bcd 为左子树, 右子树为空。
然后将左右子树继续分解, 如第①种情况的右子树先序遍历(bcd)可能有:
A. 左子树为空, 右子树为cd ;
b. 左子树为c , 右子树为d ;
c. 左子树为cd , 右子树为空。
按照这种方法继续分解左右子树, 直到不能再分解为止, 可得第①和④种情况各包含5种不同情况, 第②和③种情况各包含2种情况, 因此总共有14种不同的二叉树。
3． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为（ ）。 A.
B.n/2
C.
D.n
【答案】C
【解析】最快查找一次成功，最慢查找n
次成功。平均查找次数为
。
4． 下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）.
A. 连续结构
B. 索引结构
C. 链式结构且磁盘块定长
D. 链式结构且磁盘块变长
【答案】B
【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问. 链式结构的优点是文件易于扩展，缺点是不易随机访问. 索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展.
5． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。
A. 选择排序法
B. 插入排序法
C. 快速排序法
D. 堆排序法
【答案】A
【解析】选择排序的基本思想是:
第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录
和分别变为新的有序区和新的无序区。 和，该趟排序，将它与无序区的第1个记录R[i]交换，使那么
6． 假设变址寄存器R 的内容为1000H , 指令中的形式地址为2000H ; 地址1000H 中的内容为2000H , 地址2000H 中的内容为3000H , 地址3000H 中的内容为4000H , 则变址寻方式下访问到的操作数是（ ）
A.1000H
B.2000H
C.3000H
D.4000H
【答案】D
【解析】
根据变址寻址的
操作数的实际地址,
由题可知
4000H 。
, 变址寄存器的内容与形式地址的内容相加之后得到, 根据实际地址访问内存, 获取操作数
7． 给定二叉树如下图所示. 设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树. 若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）.
A.LRN
B.NRL
C.RLN
D.RNL
图
【答案】D
【解析】对“二叉树”而言，一般有三条搜索路径：
①先上后下的按层次遍历；
②先左(子树) 后右(子树) 的遍历；
③先右(子树) 后左(子树) 的遍历.
其中第1种搜索路径方式就是常见的层次遍历，第2种搜索路径方式包括常见的先序遍历NLR 、中序遍历LNR 、后序遍历LRN ，第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN. 本题考查的是第3种搜索路径方式的一种情况. 根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D.
8． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序
B. 快速排序，堆排序
C. 直接选择排序，归并排序
D. 归并排序，起泡排序
【答案】D
9． 为实现快速排序算法, 待排序序列宜采用的存储方式是（ ）。
A. 顺序存储
B. 散列存储
C. 链式存储
D. 索引存储
【答案】A
【解析】对绝大部分内部排序而言, 只适用于顺序存储结构, 快速排序在排序过程中, 既要从后