2017年沈阳理工大学信息科学与工程学院812数据结构考研冲刺密押题
● 摘要
一、选择题
1． 希尔排序的组内排序采用的是（ ）。
A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 归并排序
【答案】A
【解析】希尔排序基本思想是：先将整个待排元素序列按某个增量分割成若干个子序列，在子序列内进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
2． 设有两个串S1和S2, 求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串
B. 判断是否相等
C. 模型匹配
D. 连接
【答案】C
【解析】常用的串的基本操作有七种，INDEX （s ，t ）是其中的定位函数，这种运算就是所说的模式匹配。
3． 主机甲与主机乙之间已建立一个TCP 连接，主机甲向主机乙发送了 3个连续的TCP 段，分别包含300字节、400字节和500字节的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是（ ）。
A.300
B.500
C.1200
D.1400
【答案】B
【解析】本题考查TCP 的确认机制，TCP 首部的序号字段是指本报文所发送的数据的第一个字节的序号。本题中首先根据第3个段的序号为900, 可以得出第2个段的序号为500, 第1个段的
序号为200, 这里主机乙仅 正确接收了第1段和第3段，这意味着第2段丢失，需要超时重传，因此主机乙发送给主机甲的确认序号，也就是此时接收端期望收到的下一个数据包中第一个字节的序号应该是第二段的第一个字节的序号，也就是500, 因此答案是B 。
4． 为支持 中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（ ）
A. 连续结构
B. 链式结构
C. 直接索引结构
D. 多级索引结钩
【答案】A
【解析】为了实现快速随机播放，要保证最短的查询时间，即不能选取链表和索引结构，因此连续结构最优。
5． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ）
A.
B.
C.
D.
【答案】D
【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。
6． 下列选项中，不会引起指令流水线阻塞的是（ ）。
A. 数据旁路（转发）
B. 数据相关
C. 条件转移
D. 资源冲突
【答案】A
【解析】由于采用流水线方式，相邻或相近的两条指令可能会因为存在某种关联，后一条指令不能按照原指定的时钟周期运行，从而使流水线断流。有三种相关可能引起指令流水线阻塞：
①结构相关，又称资源相关；
②数据相关；
③控制相关，又称指令相关，主要由转移指令引起。
7． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz , 则总线带宽是（ ）。
A.lOMB/s
B.20MB/S
C.40MB/S
D.80MB/S
【答案】B
【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为10MHz , 时钟周期为0.1押，总线周期占用2个时钟周期，为0.2两。一个总线周期中并行传输4字节信息, 则总线带宽是4B ÷
8． 假设5个进
程=20MB/s。 共享三类资
源
题表资源分配情况表
这些资源总数分别
为时刻的资源分配情况如题表所示，此时存在的一个安全序列是（ ）。
【答案】D 。
【解析】典型的死锁避免算法、银行家算法的应用。本题的题型与2011年的27题相似。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到
，运行是可以的。
本题也可以排除法，时刻可用资源是分别为2, 3, 3, 此时刻，P0需要
分别为2, 3, 7，故排除A , P1需要Rl ，R2, R3分别为1，3, 3, P2还需要资源Rl ，R2, R3分别为0, 0, 6，故C 排除，P3需要Rl ，R2, R3分别为2, 2, 1。所以正确答案在B ，D 之间。看B 选项，P1之后的可用资源Rl ，R2, R3分别变为6, 3，6，而P0尚需资源2, 3, 7, 故B 方案行不通。因而最终答案只有D 项。