2017年江苏大学计算机科学与通信工程学院851数据结构考研仿真模拟题
● 摘要
一、选择题
1． 在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性
B. 功能特性
C. 过程特性
D. 电气特性
【答案】C 。
【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以 分析描述事件先后顺序的就是规程，也就是过程特性，答案是C 。
2． 折半查找的时间复杂性为（ ）。
【答案】D
【解析】顺序查找的事件复杂度为因为折半查找是查找效率最高的算法，它的事件复杂 度为
3． 用户在删除某文件的过程中，操作系统不可能执行是（ ）
A. 删除此文件所在的目录
B. 删除与此文件关联的目录项
C. 删除与此文件对应的控制块
D. 释放与此文件关联的内存级冲区
【答案】A
【解析】删除文件不需要删除文件所在的目录，而文件的关联目录项和文件控制块需要随着文件一同删除，同时释放文件的关联缓冲区。
4． float 类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（ ）。 A. B. C. D.
【答案】D 。
【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短 浮点数的真值为：S 为符号位，E 的取值为f 为23位；
故float 类型能表示的最大整数是
5． 假设某计算机按字编址，Cache 有4个行，Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空，采用2路组相联映射方式和LRU 替换算法，当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4， 8时，命中Cache 的次数是（ ）。
A.1
B.2
C.3
D.4
【答案】C 。
【解析】Cache 有4个行，2路组相联，即Cache 被分成2组，每组2行。主存地址为0〜1、4〜5、8〜9 可映射到第0组Cache 中，主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空，采用LRU 替换算法，当访问主存的10个地址依次为0, 4，8, 2, 0, 6，8, 6, 4, 8时，命中Cache 的次数共有3次，分别发生在第7、8和10步时。
6． 在页式存储管理系统中，采用某些页面置换算法，会出现Belady 异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady 异常现象的是（ ）。
I . LRU 算法
A. 仅 II
B .仅 I II
C. 仅I III
D. 仅 II III
【答案】A
【解析】Belady 现象只有FIFO 算法才会出现
7． 以下与数据的存储结构无关的术语是（ ）。
A. 循环队列
B. 链表
C. 哈希表
D. 栈
【答案】D
【解析】循环队列体现线性表是以顺序存储。用散列法存储的线性表称散列表。链表说明线性表是以链式结构存储的。栈不能体现出是顺序还是链式存储结构。
II. FIFO 算法 III. OPT 算法
8． 下面关于求关键路径的说法不正确的是（ ）。
A. 求关键路径是以拓扑排序为基础的
B. —个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D. 关键活动一定位于关键路径上
【答案】C
【解析】一个事件的最迟开始事件是这个事件能够拖到的最晚时间，从这个时刻开始做完这个事件不影响其后续事件的开始时间。
9． 线性表的顺序存储结构是一种（ ）。
A. 随机存取的存储结构
B. 顺序存取的存储结构
C. 索引存取的存储结构
D.Hash 存取的存储结构
【答案】A
【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。
10．一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107
B.108
C.214
D.215
【答案】B
【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有
以
11．下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先
【答案】B
【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。剩余高响应比优先算法和非抢
所
也就是说若对其进行哈夫曼编码，共能得到108个码字。
相关内容
相关标签