2018年南昌大学信息工程学院829数据结构考研核心题库
● 摘要
一、单项选择题
1． 为提高散列(Hash)表的查找效率, 可以采用的正确措施是（ ）。
Ⅰ. 增大装填(载) 因子
Ⅱ. 设计冲突(碰撞) 少的散列函数
Ⅲ. 处理冲突(碰撞) 时避免产生聚集(堆积) 现象
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅱ
D. 仅Ⅱ、Ⅲ
【答案】D
【解析】散列表的查找效率(比较次数) 取决于:散列函数、处理冲突的方法和散列表的装填因子α。α标志着散列表的装满程度, 通常情况下, α越小, 发生冲突的可能性越小; 反之, α越大, 表示已填入的记录越多, 再填入记录时, 发生冲突的可能性越大。因此选项Ⅰ错误, 越是增大装填因子, 发生冲突的可能性就越大, 查找效率也越低。选项Ⅱ正确。选项Ⅲ正确。采用合适的处理冲突的方法避免产生聚集现象, 也将提高查找效率。例如, 用拉链法解决冲突时不存在聚集现象, 用线性探测法解决冲突时易引起聚集现象。
2． 在缺页处理过程中, 操作系统执行的操作可能是（ ）。
Ⅰ. 修改页表
Ⅱ. 磁盘
Ⅲ. 分配页框
A. 仅Ⅰ、Ⅱ
B. 仅Ⅱ
C. 仅Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】D
【解析】首先我们要考虑的是, 为什么会发生缺页中断? 当然, 在一个采用虚拟存储管理技术的系统中, 程序是部分装入的, 还有部分是处于外存上的, 因此, 当需要访问那部分位于外存上的代码或数据时, 系统会产生缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存, 据此, 缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页(若没有空闲的页面则要调用页面置换程序找到一处页面, 将该页面的内容处理掉, 或回写磁盘, 或覆盖
掉, 然后将此页分配给需要访问的页) , 分配妥当以后,
缺页中断处理程序调用设备驱动程序做磁盘
, 将位于外存(一般是磁盘) 上的页面调入内存, 调入后转身去修改页表, 将页表中代表该页是否在内存的标志位(一般称为存在位或有效位、在位位) 修改为“真”, 将物理页框号填入相应位置, 若必要还需修改其它相关表项等。完成上述任务后, 缺页中断处理程序返回, 继续程序的执行。从上述过程可以看出, 涉及的相关处理非常多, 因此, 答案就显而易见了。
3． 线性表的顺序存储结构是一种（ ）。
A. 随机存取的存储结构
B. 顺序存取的存储结构
C. 索引存取的存储结构
D.Hash 存取的存储结构
【答案】A
【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。
4． 假定有4个整数用8位补码分别表示为
放在一个8位寄存器中, 则下列运算会发生溢出的是（ ）。 A. B. C. D.
【答案】B
【解析】用补码表示时8位寄存器所能表示的整数范围为
数
, , 在4个选项中, 只有
都未超过127, 不发生溢出
5． 下面关于串的叙述中，不正确的是（ ）。
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
【答案】B
【解析】空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。
6． 下列选项中, 满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务
。若将运算结果存。现在4个整数都是负, 结果溢出, 其余3个算式结果
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先
【答案】B
【解析】分析该题目可以看到, 本题所提到的问题是涉及短任务调度也就是属于作业调度, 因此首先排除时间片轮转算法; 因为作业调度算法中没有时间片轮转的算法。其次, 因为问题提到短任务, 则先来先服务的算法也可以排除了, 它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个？我们可以通过分析得到, 非抢占式短任务优先算法不能解决饥饿问题, 因为当一个系统短任务源源不断到达是, 长任务必然会得不到调度, 产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法, 并以高响应比值优先调度。这样, 无论短任务或长任务, 均可以得到调度, 而且, 较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有高响应比优先算法。
7． 已知串
A.0123
B.1123
C.1231
D.1211
【答案】A 其Next 数组值为（ ）。
【解析】KMP 算法的next 数组建立的原则
8． 设置当前工作目录的主要目的是（ ）.
A. 节省外存空间
B. 节省内存空间
C. 加快文件的检索速度
D. 加快文件的读/写速度
【答案】C
【解析】工作目录只是指出了当前操作的默认目录，使得在每次访问的时候不需要由根目录一层一层地解析，在文件路径比较长时，可以节省许多解析的时间，从而加快了文件的检索速度.
9． 下列哪一种图的邻接矩阵是对称矩阵？（ ）
A. 有向图
B. 无向图
C.AOV 网