燕山大学操作系统与数据结构历年考研真题答案附后Word文件下载.docx

燕山大学操作系统与数据结构历年考研真题答案附后Word文件下载.docx

《燕山大学操作系统与数据结构历年考研真题答案附后Word文件下载.docx》由会员分享，可在线阅读，更多相关《燕山大学操作系统与数据结构历年考研真题答案附后Word文件下载.docx（5页珍藏版）》请在冰点文库上搜索。

2013年燕山大学810操作系统与数据结构考研真题

2012年燕山大学810操作系统与数据结构考研真题

2．中国计量学院数据结构与操作系统历年考研真题

2015年中国计量学院806数据结构与操作系统考研真题

2014年中国计量学院818数据结构与操作系统考研真题

2013年中国计量学院818数据结构与操作系统考研真题

3．广东工业大学操作系统历年考研真题

2014年广东工业大学830操作系统考研真题

2013年广东工业大学830操作系统考研真题

4．沈阳航空航天大学操作系统历年考研真题

2014年沈阳航空航天大学811操作系统考研真题

2013年沈阳航空航天大学811操作系统考研真题

5．沈阳工业大学计算机操作系统历年考研真题

2014年沈阳工业大学837计算机操作系统考研真题

6．山东科技大学数据结构与操作系统历年考研真题

2014年山东科技大学830数据结构与操作系统考研真题

2012年山东科技大学838数据结构与操作系统考研真题

《数据结构》部分

一、简答题（15分，每题5分）

1．什么是原地工作？

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算法生成最小树，试画出构造过程。

4．某整形数组A的数组元素分别是6，2，9，7，3，8，4，5，0，试用下例各排序方法将A中元素由小到大排序。

（1）用第一元素中的值6作为枢轴，试写出快速排序第一次分割后A中的结果。

（2）A中的元素是否为堆，如果不是，请将其调整为堆，写出将A调整成堆后A中的结果。

三、算法设计题（30分）

答题要求：

用自然语言说明所采用算法的思想；

给出每个算法所需的数据结构定义，并做必要说明；

用C语言写出对应的算法程序，并做必要的注释。

1．将n（n>

1）个整数存放到一维数组R中。

设计一个尽可能高效（时间、空间）的算法，将R中保存的序列循环左移p（0<

p<

n）个位置，即将R中的数据（x0,x1,x2,…,xn-1），变换为（xp，xp＋1,…,xn-1,x0,x1,…,xp-1）。

2．给出折半查找的递归算法，并给出算法时间复杂度性分析。

《操作系统部分》

一、简单题（每小题5分，共30分）

1．操作系统设计的最重要的两个目标是什么？

并简述原因。

2．进程有哪五种基本状态？

发生状态间转移的原因是什么？

3．在请求分页机制中会发生缺页中断。

请概述缺页中断的处理流程。

4．I/O控制方式有哪几种实现方式？

并比较这几种I/O控制方式的优缺点。

5．索引分配是外存管理中常用的分配方式。

请问，索引分配有哪三种常见的方式？

这些方式的优点和缺点是什么？

6．产生死锁的四个必要条件是什么？

预防死锁有几种实现方法？

二、算法和计算题（共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两种替换算法的缺页（页故障）数。

结果说明了什么？

。

3．在64位机中，如果为每个进程保持一个页表，则会占用较大的内存空间。

请设计一种能够有效降低内存占用率的页表方式，并说明其工作原理。

（8分）

2011年山东科技大学827数据结构与操作系统考研真题