2003年甘肃兰州大学数据结构(含操作系统)考研真题.doc

发布时间：2022-09-20 发布人：admin 分类：说明书资料大小：0.55M 资料格式：doc 举报版权申诉

第1页 / 共3页

2003年甘肃兰州大学数据结构(含操作系统)考研真题.doc.pdf-第2页.jpg

第2页 / 共3页

2003年甘肃兰州大学数据结构(含操作系统)考研真题.doc.pdf-第3页.jpg

第3页 / 共3页

文本预览

2003 年甘肃兰州大学数据结构(含操作系统)考研真题【数据结构部分（90 分）】一、解释下列术语（每小题 4 分，共 20 分）∶ 1、时间复杂性 2、模式匹配 3、地址向量 4、碰撞 5、倒排文件二、求解以下问题∶（共 50 分） 1、数组 A【-3…10，812，6…15】采用行优先存储法，现假设基地址为 100，每个元素占用 2 个存储单元，请计算数组 A 的虚拟地址值。（5 分） 2、对于图（a）所示森林，将其转换为二叉树，给出转换后的二叉树图示，并写出得到的二叉树的中序遍历结果及中序线索树图示。（10 分） 3、若有关键字序列（6，2，1，4，5，3，7）请构造一棵 AVL 树（要求画出每步状│态变迁图示），并计算在等概率情况下该 AVL 树的平均检索长度。（9 分）4、已知无向图 G 的邻接矩阵如图（b）所示;请画出其所有的连通分量的图示。（6 分》

5、利用 Djista 方法求最短路径时需要引入一个辅助向量 D 用以记录找到的最短路径长度。对于图（c）所示的有向图，给出其邻接矩阵，求从顶点 1 出发分别到达其它各顶点的最短路径，并写出运算过程中 D 向量的变化状况。（12 分） 6、对于图（d）所示的三阶 B 树，请画出插入关键字 R 后的结果图示。（4 分） 7、已知关键字的初始序列为（34，21，65.24，77，32，44），请给出利用快速排序法对其进行第一趟快排的排序过程示意图。（4 分）三、算法设计（算法描述语言采用类 C 或者类 Pascal。需说明所用语言，对所用存储结构需给出形式化说明，算法关键地方需加注解。每个小题 10 分，共 20 分。）【操作系觥部分（60 分〕】四、名词解释（每小题 2 分，共 10 分） 1、重定位 2、管程 3、多道程序设计技术 4 文件系统 5、虚拟五、简答（每小题 4 分，共 20 分） 1、下图（e）中一个进程状态转换的发生，是否会导致另一个转换的发生。列出两种可能，并给出相应的条件。

2、简述引入线程的好处。 3、常见的文件物理结构有几种，各有何优缺点。 4、VO 控制方式有几种。 5、简述预防死锁的措施。六、综合题（每小题 10 分，共 30 分） 1、在一个请求分页存储管理系统中，一个作业的页面走向为 1、2、3、4、1、3、5、1、2、 3、4、5，分配给该作业的物理块数为 4，请画出采用先进先出、LRU 页面淘汰算法时的置换过程，计算缺页率，并列出淘汰页面序列。 2、物业中心有 N（N>1）位维修员，一本一次只允许一人填写的维修记录表。如没有维修任务则维修员睡觉。住户有维修请求时，到物业中心在维修记录表上进行登记，每人每次只能登记一个请求。当累计有三个维修请求时，唤醒维修员去进行维修。维修员完成维修任务后，回到物业中心在维修记录上填写维修结果。如没有新的维修请求或请求少于三个时，维修员休息睡觉。请用信号量机制解决维修员与住户的同步问题。 3、在两道环境下有四个作业。已知它们进入系统的时间、估计运行时间。若系统采用短作业优先作业调度算法，进程调度采用基于短作业优先的可抢占式调度算法。请填写下表中的开始时间和结束时间，并计算出平均周转时闾及带权平均周转时间。

分享到：

赞收藏

资料库

2003年甘肃兰州大学数据结构(含操作系统)考研真题.doc

相关推荐

考研

热门标签

最新资料