2017年南昌大学信息工程学院838数据结构[专业硕士]考研导师圈点必考题汇编
● 摘要
一、选择题
1． 对一组数据（2, 12, 16, 88, 5，10）进行排序，若前三趟排序结果如下：
第一趟：2，12，16, 5，10，88
第二趟：2，12，5，10，16, 88 第三趟：2，5，10，12，16, 88
则采用的排序方法可能是（ ）。
A. 起泡排序
B. 希尔排序
C. 归并排序
D. 基数排序
【答案】A
【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次
，待序列中的记录“基比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”
本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐増多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序
，直至整个序列为有序为止。 基数排序是分配排列合并为一个大的有序序列，然后“逐趟归并”
序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。 本
，显然使用的是起泡排序法。 题中，很容易看出大值逐渐“沉底”
2． 用有向无环图描述表达式（A+B）*（，至少需要顶点的数目为（ ）（A+B）/A）。
A.5 B.6 C.8 D.9
【答案】A
6条边 【解析】一共5个结点
3． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。
A.4
B.5
C.6
D.7
【答案】B
【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（l 〇g2n ） +1，在本题中，n=16, 故比较次数最多为5。
4． 在页式存储管理系统中，采用某些页面置换算法，会出现Belady 异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady 异常现象的是（ ）。
I . LRU 算法
A. 仅 II
B .仅 I II
C. 仅I III
D. 仅 II III
【答案】A
【解析】Belady 现象只有FIFO 算法才会出现
5． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进栈，然后再出栈。从中可以看出，push 的数目始终大于等于pop 的数目。
6． 为提高散列（Hash ）表的查找效率，可以采用的正确措施是（ ）。
I .增大装填（载）因子
II. 设计冲突（碰撞）少的散列函数
III. 处理冲突（碰撞）时避免产生聚集（堆积）现象
A. 仅I B. 仅 II C. 仅 I 、II D. 仅 II 、III
【答案】D
【解析】散列表的查找效率（比较次数）取决于：散列函数、处理冲突的方法和散列表的装填因子a 。CX 标 志着散列表的装满程度，通常情况下，（X 越小，发生冲突的可能性越小；反之，a 越大，表示已填入的记录越多， 再填入记录时，发生冲突的可能性越大。因此选项I 错误，越是增大装填因子，发生冲突的可能性就越大，查找 效率也越低。选项II 正确。选项III 正确。采用合适的处理冲突的方法避免产生聚集现象，也将提高查找效率。例如，用拉链法解决冲突时不存在聚集现象，用线性探测法解决冲突时易引起聚集现象。
7． 某同步总线的时钟频率为宽度为32位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输128位数据所需要的时间至少是（ ）。
A.20ns
B.40ns
C.50ns
D.80ns
II. FIFO 算法 III. OPT 算法
【答案】C 。
【解析】总线的时钟频率为100MHz ，贝时钟周期为10ns 。数据是128位，总线宽度是32位，所以需要4个时钟周期，而传输地址还需要一个周期，所以传输一个128位的数据至少需要5个时钟周期，所以至少需要10ns*5=50ns。
8． 在含有n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。
【答案】D
【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于的结点上。
9． 现有容量为10GB 的磁盘分区，磁盘空间以簇（cluster ）为单位进行分配，簇的大小为4KB , 若采用位图法管理该分区的空闲空间，即用一位（bit ）标识一个簇是否被分配，则存放该位图所需簇的个数为（ ）
A.80
B.320
C.80K
D.320K
【答案】A
【解析】磁盘的簇的个数为：
而一个簇的位示图能管理的簇的个数为：个 所以需要簇的个数为
10．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。
A. 存在，且唯一
B. 存在，且不唯一不唯一
C. 存在，可能不唯一
D. 无法确定是否存在
【答案】C 。
【解析】图的基本应用——拓扑排序，用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，说明该图为有向无环图，所以其拓扑序列存在，但不一定唯一，如图的邻接矩阵为则存在两个拓扑序列。
相关内容
相关标签