《2017年中国农业科学院麻类所808数据结构考研冲刺密押题.doc》由会员分享，可在线阅读，更多相关《2017年中国农业科学院麻类所808数据结构考研冲刺密押题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年中国农业科学院麻类所808数据结构考研冲刺密押题一、选择题1 在采用中断I/O方式控制打印输出的情况下，CPU 和打印控制接口中的I/O端口之间交换的信息不可能是（ ）。A. 打印字符B. 主存地址C. 设备状态D. 控制命令【答案】B【解析】I/O接口的功能包括：选址功能；传送命令功能；传送数据功能；反映I/O设备工作状态功能。A 项为数据，C 项为设备状态，D 项为命令。B 项，主存地址在中断方式控制下是不需要的，因此，它不可能是CPU 和打印控制接口中的I/O端口之间交换的信息。 2 稀疏矩阵一般的压缩存储方法有两种，即（ ）。A. 二维数组和三维数组B. 三元组和散列C. 三
2、元组和十字链表D. 散列和十字链表【答案】C【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组（行标，列标，值）。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。 3 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。 【答案】B【解析】根据输入序列和输出序列可知，输入序列全部进栈，然后再出栈。从中可以看出，push 的数目始终大于等于pop 的数目。 4 在有向图的邻接表存储结构中，顶点V 在链表中出现的次数是（ ）。A. 顶点V 的度 B
3、. 顶点V 的出度 C. 顶点V 的入度 D. 依附于顶点V 的边数【答案】B【解析】在有向图中，第j 个链表中的结点个数只是顶点Vi 的出度，为求入度，必须遍历整个邻接表。因此顶点V 在链表中出现的次数是顶点V 的出度。 5 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。A. 先来先服务B. 高响应比优先C. 时间片轮转D. 非抢占式短任务优先【答案】B【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。
4、剩余高响应比优先算法和非抢占式短任务优先是哪一个? 我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到 调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有尚响应比优先算法。 6 一个TCP 连接总是以1KB 的最大段发送TCP 段，发送方有足够多的数据要发送。当拥塞窗口为16KB 时发生了超时，如果接下来的4个RTT （往返时间）时间内的TCP 段的传输都是成功的，那么当
5、第4个RTT 时间内发送的所有TCP 段都得到肯定应答时，拥塞窗口大小是（ ）。A.7KBB.8KBC.9KBD.16KB【答案】C【解析】回顾TCP 流量控制和拥塞控制（慢启动）的知识点，从第一个MSS 开始，每次发送成功，拥塞窗口值翻倍，四次以后，应该为16, 但是由于拥塞阈值变为16/2=8, 故三次成功后为8, 以后为线性增长，故为8+1=9, 答案为C 。 7 在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。A. 机械特性B. 功能特性C. 过程特性D. 电气特性【答案】C 。【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边
6、界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以 分析描述事件先后顺序的就是规程，也就是过程特性，答案是C 。 8 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）。A.B.C.D. 字节字节字节字节【答案】C【解析】段内位移的最大值就是最大段长。段号长度占了8位，剩下32-8=24位是段内位移空间，因此最大段长为B 。9 已知关键字序列5, 8, 12, 19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。A.3, 5，12，8, 28，20, 15，22，19B.3, 5, 12, 19, 20, 15, 22, 8, 28C.3, 8, 12, 5, 20, 15, 22, 28, 19D.3, 12, 5, 8, 28, 20, 15, 22, 19【答案】A【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）?（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。 一、选择题考研试题
