2017年沈阳航空航天大学计算机学院805数据结构考研冲刺密押题
● 摘要
一、选择题
1． 数组
A.55 B.45 C.36 D.16
【答案】B
【解析】该数组为三维数组。其个数为
2． 某计算机主存地址空间大小为256MB , 按字节编址。虚拟地空间大小为4GB ，采用页式存储管理，页面大小为4KB ，TLB （快表）采用全相联映射，有4个页表项，内容如下表所示。
中含有元素的个数（ ）。
则对虚拟地址03FFF180H 进行虚实地址变换的结果是（ ）
A.0153180H B.0035180H C.TLB 缺失 D. 缺页 【答案】A
【解析】虚拟地址为03FFF180H ，其中页号为03FFFH , 页内地址为180H ，根据题目中给出的页表项可知页标记为03FFFH 所对应的页框号为0153H , 页框号与页内地址之和即为物理地址015 3180H。
3．
某系统正在执行三个进程
例如下表所示。
和各进程的计算（CPUCPUCPU
）时间和时间比
为提高系统资源利用率，合理的进程优先级设置应（ ）
A.
B.
C.
D. 【答案】B
【解析】为了合理地设置进程优先级，应该将进程的CPU 利用时间和
时间做综合考虑，
故答案选B 。
4． 有向带权图如题图所示，若采用迪杰斯特拉（Dijkstra ）算法求从源点a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b ，第二条最短路径的目标顶点是c ，后续得到的其余各最短路径的目标顶点依次是（ ）。
题图有向带权图
A.d , e , f
B.e , d , f C.f , d , e D.f , e , d 【答案】C 。
【解析】本题主要考查Dijkstra 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。
执行Dijkstra 算法过程中各步的状态表，故后续目标顶点依次为f ，d , e 。
5． 采用简单选择排序，比较次数与移动次数分别为（ ）。
【答案】C
【解析】简单选择排序只在要交换的时候交换位置，及移动位置，共需移动n 次。而需要比 较的次数为
6． 已知循环队列存储在一维数组rear 的值分别是（ ）。
A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-1
【答案】B
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，且要求第1 个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。
7． 数据链路层采用选择重传协议（SR ）传输数据，发送方已发送了0H3号数据倾，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是（ ）。
A.1 B.2 C.3 D.4
【答案】B
【解析】在选择重传协议中，接收方逐个地确认正确接收的分组，不管接收到的分组是否有序，只要正确接 收就发送选择ACK 分组进行确认。因此选择重传不支持累积确认，要特别注意其与GBN 协议的区别。本题收到1号帧的确认，说明1号帧正确接收，0和2号帧依次超时，因此必须重传，然而3号帧尚未超时，是否正确接收未知，故不用重传，因此必须重传0和2号帧，答案是B 。
中，且队列非空时front 和rear 分别指向队头元素和
队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和