2018年太原科技大学交通与物流学院828数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列, 能属于同一棵哈夫曼树的是（ ）。
A.24, 10, 5和24, 10, 7
B.24, 10, 5和24, 12, 7
C.24, 10, 10和24, 14, 11
D.24, 10, 5和24, 14, 6
【答案】D
【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中, 第二个被访问的两个结点的权值要么相等, 要么和为根节点的权值, 故B 项错误。同理, 通过第三个被访问的节点排除A 项。C 项, 由两条路径可推出三个叶子节点的权值分别是:3、10和11, 而根据哈夫曼树的定义可知, 权值为3的节点应该和权值为10的结点结合, 故C 项错误。D 项, 反推出有四个叶子节点, 权值分别为:5、5、6和8, 满足哈夫曼树的条件。
2． 有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612
B.453126
C.346521
D.234156
【答案】C
【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出枝。
3． 数据链路层采用选择重传协议(SR)传输数据, 发送方已发送了0H3号数据帧, 现已收到1号帧的确认, 而0、2号帧依次超时, 则此时需要重传的帧数是（ ）。
A.1
B.2
C.3
D.4
【答案】B
【解析】在选择重传协议中, 接收方逐个地确认正确接收的分组, 不管接收到的分组是否有序, 只要正确接收就发送选择ACK 分组进行确认。因此选择重传不支持累积确认, 要特别注意其与GBN 协议的区别。本题收到1号帧的确认, 说明1号帧正确接收, 0和2号帧依次超时, 因此必须重
传, 然而3号帧尚未超时, 是否正确接收未知, 故不用重传, 因此必须重传0和2号帧, 答案是B 。
4． 用有向无环图描述表达式，至少需要顶点的数目为（ ）。
A.5
B.6
C.8
D.9
【答案】A
，6条边【解析】一共5个结点
5． 在缺页处理过程中, 操作系统执行的操作可能是（ ）。
Ⅰ. 修改页表
Ⅱ. 磁盘
Ⅲ. 分配页框
A. 仅Ⅰ、Ⅱ
B. 仅Ⅱ
C. 仅Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】D
【解析】首先我们要考虑的是, 为什么会发生缺页中断? 当然, 在一个采用虚拟存储管理技术的系统中, 程序是部分装入的, 还有部分是处于外存上的, 因此, 当需要访问那部分位于外存上的代码或数据时, 系统会产生缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存, 据此, 缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页(若没有空闲的页面则要调用页面置换程序找到一处页面, 将该页面的内容处理掉, 或回写磁盘, 或覆盖掉, 然后将此页分配给需要访问的页) , 分配妥当以后,
缺页中断处理程序调用设备驱动程序做磁盘
, 将位于外存(一般是磁盘) 上的页面调入内存, 调入后转身去修改页表, 将页表中代表该页是否在内存的标志位(一般称为存在位或有效位、在位位) 修改为“真”, 将物理页框号填入相应位置, 若必要还需修改其它相关表项等。完成上述任务后, 缺页中断处理程序返回, 继续程序的执行。从上述过程可以看出, 涉及的相关处理非常多, 因此, 答案就显而易见了。
6． 在一棵具有15个关键字的4阶B 树中, 含关键字的结点数最多是（ ）
A.5 B.6 C.10 D.15
【答案】D
【解析】M 阶B 树非根结点含关键字个数
键字, 一共有15个关键字那么最多有15个含有关键字的结点
。 。 4阶B 树非根结点含关键字1~3个, 所以要使关键字结点数量最多, 那么每个结点只有一个关
7． 在OSI 参考摸型中, 下列功能需由应用层的相邻层实现的是（ ）
A. 对话管理
B. 数据格式转换
C. 路由选择
D. 可靠数据传输
【答案】B
【解析】应用层的相邻层即为表示层, 表示层负责管理数据的压缩、加密与解密、格式装换等, 故答案为B 。
8． 以下数据结构中，（ ）是非线性数据结构。
A. 树
B. 字符串
C. 队
D. 栈
【答案】A
【解析】非线性结构是指存在一对多或者多对一的关系。常见的非线性结构有树结构和图结构。
9． 在物理层接口特性中, 用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性
B. 功能特性
C. 过程特性
D. 电气特性
【答案】C 。
【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性; 机械特性:主要定义物理连接的边界点, 即接插装置; 电气特性:规定传输二进制位时, 线路上信号的电压高低、阻抗匹配、传输速率和距离限制; 功能特性:主要定义各条物理线路的功能; 规程特性:主要定义各条物理线路的工作规程和时序关系。而从题干可以分析描述事件先后顺序的就是规程, 也就是过程特性, 答案是C 。
10．用邻接表存储图所用的空间大小（ ）。
A. 与图的顶点数和边数都有关
B. 只与图的边数有关
C. 只与图的顶点数有关
D. 与边数的平方有关