燕山大学操作系统与数据结构历年考研真题答案附后11p

1、燕山大学操作系统与数据结构历年考研真题答案附后最新资料， WORD格式，可编辑修改！目 录1燕山大学操作系统与数据结构历年考研真题.2015年燕山大学 810操作系统与数据结构考研真题 . .2014年燕山大学 811操作系统与数据结构考研真题 . .2013年燕山大学 810操作系统与数据结构考研真题 . .2012年燕山大学 810操作系统与数据结构考研真题 . .2中国计量学院数据结构与操作系统历年考研真题.2015年中国计量学院806数据结构与操作系统考研真题 . .2014年中国计量学院818数据结构与操作系统考研真题 . .2013年中国计量学院818数据结构与操作系统考研真题 .

2、 .3广东工业大学操作系统历年考研真题.2014年广东工业大学830操作系统考研真题 . .2013年广东工业大学830操作系统考研真题 . .4沈阳航空航天大学操作系统历年考研真题.2014年沈阳航空航天大学811 操作系统考研真题 . .2013年沈阳航空航天大学811 操作系统考研真题 . .5沈阳工业大学计算机操作系统历年考研真题.2014年沈阳工业大学837计算机操作系统考研真题 . .2013年沈阳工业大学837计算机操作系统考研真题 . .6山东科技大学数据结构与操作系统历年考研真题.2014年山东科技大学830数据结构与操作系统考研真题 . .2012年山东科技大学838数据结

3、构与操作系统考研真题 . .2011年山东科技大学827数据结构与操作系统考研真题 . .说明： 精选了 16 套名校操作系统历年考研真题1燕山大学操作系统与数据结构历年考研真题2015 年燕山大学810 操作系统与数据结构考研真题2014 年燕山大学811 操作系统与数据结构考研真题2013 年燕山大学810 操作系统与数据结构考研真题2012 年燕山大学810 操作系统与数据结构考研真题2中国计量学院数据结构与操作系统历年考研真题2015 年中国计量学院806 数据结构与操作系统考研真题2014 年中国计量学院818 数据结构与操作系统考研真题2013 年中国计量学院818 数据结构与操作

4、系统考研真题3广东工业大学操作系统历年考研真题2014 年广东工业大学830 操作系统考研真题2013 年广东工业大学830 操作系统考研真题4沈阳航空航天大学操作系统历年考研真题2014 年沈阳航空航天大学811 操作系统考研真题2013 年沈阳航空航天大学811 操作系统考研真题5沈阳工业大学计算机操作系统历年考研真题2014 年沈阳工业大学837 计算机操作系统考研真题6山东科技大学数据结构与操作系统历年考研真题2014 年山东科技大学830 数据结构与操作系统考研真题2012 年山东科技大学838 数据结构与操作系统考研真题数据结构部分一、简答题（ 15 分，每题5 分）1什么是原地工

5、作？2什么是完全二叉树？3什么是稳定的排序方法？二、应用题（ 45 分）1设有一个顺序栈S，元素 s1, s2, s3, s4, s5, s6依次进栈，如果6 个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。（10 分）2给定一棵二叉树如右图所示（ 1）写出该树的前序、中序、后序遍历结果；（ 2）画出该二叉树的中序线索树；（ 3）将它转换成等价的树或森林。（ 15 分）3已知一个无向图如下图所示， 要求用 Kruskal 算法生成最小树，试画出构造过程。（ 10 分）4某整形数组A 的数组元素分别是6， 2， 9， 7，3，

6、8， 4， 5， 0，试用下例各排序方法将A 中元素由小到大排序。（10 分）(1) 用第一元素中的值6 作为枢轴，试写出快速排序第一次分割后A 中的结果。(2)A 中的元素是否为堆，如果不是，请将其调整为堆，写出将A 调整成堆后A中的结果。三、算法设计题（30 分)答题要求：用自然语言说明所采用算法的思想；给出每个算法所需的数据结构定义，并做必要说明；用 C 语言写出对应的算法程序，并做必要的注释。1将 n(n1) 个整数存放到一维数组R 中。设计一个尽可能高效（时间、空间）的算法，将 R 中保存的序列循环左移p（ 0pn）个位置，即将R 中的数据（ x0, x1,x2, xn-1），变换为

7、 (xp ， xp 1, xn-1 ,x0 , x1, xp-1)。 (15 分 )2给出折半查找的递归算法，并给出算法时间复杂度性分析。（15 分）操作系统部分一、简单题（每小题5 分，共 30 分）1操作系统设计的最重要的两个目标是什么？并简述原因。2进程有哪五种基本状态？发生状态间转移的原因是什么？3在请求分页机制中会发生缺页中断。请概述缺页中断的处理流程。4I/O 控制方式有哪几种实现方式？并比较这几种I/O 控制方式的优缺点。5索引分配是外存管理中常用的分配方式。 请问，索引分配有哪三种常见的方式？这些方式的优点和缺点是什么？6产生死锁的四个必要条件是什么？预防死锁有几种实现方法？二

8、、算法和计算题（共30 分）1桌子上有一只盘子，每次只能放一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等着吃盘子中的橘子，一个女儿专等着吃盘子中的苹果。父、母的动作可以分解为：准备水果；放水果两步；儿女的动作可以分解为：拿水果，吃水果两步。把父、母、儿、女看作是4 个进程，请用 wait,signal 操作写出他们之间的同步机制。（注意：对于用到的各个信号量需要说明初值）（ 12分）2在请求页式系统中，一程序的页面走向（访问串或引用串）为2，3，4，5，2，3，6，2，3，4，5，6, 设分配给该程序的存储块数为m。试分别计算 m=3和 m=4时， FIFO 和 LRU两种替换算法