当前位置：问答库＞考研试题

一、应用题

1． 请阅读下列算法，回答问题。

问题一：这是什么类型的排序算法，该排序算法稳定吗？ 问题二：设置

|的作用是什么? 若将WHILE--DO 语句中判断条件改为

该

算法将会有什么变化，是否还能正确工作？

【答案】问题一：此为直接插入排序算法，该算法稳定。 问题二：采用

2．

已知一个整数序列

的作用是监视哨，免去每次检测文件是否到尾，提高了排序效率。

描述算法后，算法变为不稳定排序，但能正常工作。

其中

则称x 为A 的主元素。

例如

若存在

且

则称5为主元素；

又如

则A 中没有主元素。假设A 中的n 个元素保存在一个一维数组中，请设计一个

尽可能高效的算法，找出A 的主元素。若存在主元素，则输出该元素；否则输出-1。要求：

（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】

（1）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num 。然后重新计数，确认Num 是否是主元素。

算法可分为以下两步：

①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num 保存到c 中，记录Num 的出现次数为1; 若遇到的下一个整数仍等于Num ，则计数加1否则计数减1; 当计数减到0时，将遇到的下一个整数保存到c 中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。

或Java 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

②判断c 中元素是否是真正的主元素，再次扫描该数组，统计c 中元素出现的次数，若大于则为主元素；否则，序列中不存在主元素。

（2）算法实现如下：

用来保存候选主元素，count 用来计数

设置A [0]为候选主元素

查找候选主元素

为A 中的候选主元素计数

处理不是候选主元素的情况

更换候选主元素

统计候选主元素的实际出现次数

确认候选主元素

不存在主元素

，空间复杂度为O （1）（3）时间复杂度为O （n ）。

3． 一个循环队列的数据结构描述如下：

给出循环队列的队空和队满的判断条件，并且分析一下该条件对队列实际存储空间大小的影响，如果为了不损失存储空间，你如何改进循环队列的队空和队满的判断条件？

【答案】（1）队空：

（2）队满：

这种判断方法，会“牺牲一个存储单元”。为了不损失存储空间，可以通过设置标志位的方式

来进行队空和队满的判断。设标记tag ，tag 等于0情况下，若删除时导致front=rear为队空; tag=l情况下，若因插入导致front=rear则为队满。

4． 请求分页管理系统中，假设某进程的页表内容如下表所示:

页面大小为4KB ，一次内存的访问时间是100ns ，一次快表（TLB ）的访问时间是10ns ，处，进程的驻留集大小固定为2, 采理一次缺页的平均时间为108ns （已含更新TLB 和页表的时间）

用最近最少使用置换算法（LRU ）和局部淘汰策略。假设①TLB 初始为空；②地址转换时先访问TLB , 若TLB 未命中，再访问页表（忽略访问页表之后的TLB 更新时间）；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列

请问：

（1）依次访问上述三个虚地址，各需多少时间? 给出计算过程。

（2）基于上述访问序列，虚地址1565H 的物理地址是多少? 请说明理由。 【答案】⑴

页面大小为4KB ，因此，虚地址的低12位是页内偏移，其余高位是页号。

访问虚地址2362H , 虚页号为2，页内偏移362H 。查找TLB , TLB 初始为空，未命中，耗时10ns ; 访问页表，2号页面所在页框号为254H ，耗时100ns ; 计算得到的物理地址254362H ，访问内存，耗时100ns 。因此，总共用时

访问虚地址1565H ，虚页号为1, 页内偏移565H 。查找TLB ，未命中，耗时10ns ; 访问页表，有效位是0，未命中，耗时100m ; 产生缺页中断，进行缺页中断处理，耗时108m ; 采用LRU 置换算法，虚页1装入页帧号101H , 缺页中断处理完后，再次访问页表，命中，耗时100m ; 计算得到物理地址101565H ，再次访问内存，耗时100ns 。因此，总共用时

访问虚地址25A5H ，虚页号为2, 页内偏移5A5H 。查找TLB , 命中，耗时10ns ; 虚页2对应的页帧为254H ，因此计算得物理地址为2545A5H , 访问内存，耗时100ns 。因此，

总共用时

（2）当访问虚地址1565H 时，产生缺页中断，合法驻留集为2, 必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H 的对应的页框号为101H ，故可知虚地址1565H 的物理地址为101565H 。

5． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。