2016年东北师范大学信息与软件工程、计算机科学与信息技术学院数据结构(同等学力加试)复试笔试仿真模拟题
● 摘要
一、选择题
1． 为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。
A. 顺序存储
B. 散列存储
C. 链式存储
D. 索引存储
【答案】A
【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。
2． 某时刻进程的资源使用情况如下表所示
此时的安全序列是（ ）。
A.P1, P2, P3, P4
B.P1, P3, P2, P4
C.P1, P4, P3, P2
D 不存在
【答案】D
【解析】典型的死锁避免算法，银行家算法的应用。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到，经过P1, P4的运行以后，可用资源是2, 2，1，而 P2, P3所需资源分别是1，3, 2和1，3，1。所以剩余资源已经不够P2或P3的分配，亦即找不到能够安全运行的序 列，因此此时是处于不安全状态，所以不存在这样的安全序列。
3． 现有容量为10GB 的磁盘分区，磁盘空间以簇（cluster ）为单位进行分配，簇的大小为4KB , 若采用位图法管理该分区的空闲空间，即用一位（bit ）标识一个簇是否被分配，则存放该位图所需簇的个数为（ ）
A.80
B.320
C.80K
D.320K
【答案】A
【解析】磁盘的簇的个数为：
而一个簇的位示图能管理的簇的个数为：
所以需要簇的个数为
4． 计算机开后，操作系统最终被加载到（ ）
A.BIOS
B.ROM
C.EPROM
D.RAM
【答案】D
【解析】系统开机后, 操作系统的程序会被自动加载到内存中的系统区，这段区城是RAM ，故答案选D 。
5． 下列关于IP 路由器功能的描述中，正确的是（ ）。
I. 运行路由协议，设置路由表；II. 监测到拥塞时，合理丢弃IP 分组；III. 对收到的IP 分组头进行差错校验，确保传输的IP 分组不丢失；IV . 根据收到的IP 分组的目的IP 地址，将其转发到合适的输出线路上。
A. 仅III 、IV
B. 仅 I 、II 、III
C. 仅 I 、II 、IV
D.I 、II 、III 、IV
【答案】C 。
【解析】路由器的主要功能是路由和转发，因此I 和IV 是正确的，而针对II 和III ，可以从ICMP 协议的差错控制出发，注意检测到拥塞时，合理丢弃IP 分组，并回传ICMP 源抑制报文，
个
II 是正确的，而III 对收到的IP 分组头进行差错校验，确保传输的IP 分组不丢失，差错校验是正确的，但网络层不保证IP 分组不丢失，也就是不可靠的，因此III 的说法错误，正确的说法仅I 、II 、IV , 因此答案是C 。
6． 下列AOE 网表示一项包含8个活动的工程。通过同时加快若干进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（ ）
A.c 和e
B.d 和e
C.f 和d
D.f 和h
【答案】C
【解析】根据AOE 网的定义可知，同时缩短几条关键路径上的活动时间，可以缩短整个工期。
7． 假定编译器将赋值语句“x=x+3; ”转换为指令” add xaddt, 3”，其中xaddt 是x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ，且Cache 使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（ ）。
A.0
B.1
C.2
D.3
【答案】C
【解析】采用页式虚拟存储管理方式时，若页表全部放在内存中，则存取一个数据最少要访问两次内存：第一次是访问页表，得到所存取的数据或指令的物理地址；第二次根据该地址存取数据或指令。在配有TLB 的页式虚拟管理方式中，如果给出的地址在TLB 中，则直接根据该地址取数据或指令，仅需要一次访问内存。Cache 使用直写方式时，计算完需要将数据写回到内存中，因此完成整个指令功能至少需要访问主存2次。
8． 下列选项中，不会引起指令流水线阻塞的是（ ）。
A. 数据旁路（转发）
B. 数据相关
C. 条件转移
D. 资源冲突
【答案】A