(NEW)山东科技大学信息科学与工程学院《823数据结构》与操作系统历年考研真题汇编.pdf

目　录 2014年山东科技大学信息科学与工程学院830数据结构与操作系统考研 真题 2012年山东科技大学信息科学与工程学院838数据结构与操作系统考研 真题 2011年山东科技大学信息科学与工程学院827数据结构与操作系统考研 真题 2010年山东科技大学信息科学与工程学院827数据结构与操作系统考研 真题 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算法生成最小树， 试画出构造过程。 （10分） （10分） 　 4 ．某整形数组A 的数组元素分别是6，2，9 ，7，3，8，4 ，5，0， 试用下例各排序方法将A 中元素由小到大排序。 （10分） （1）用第一元素中的值6作为枢轴，试写出快速排序第一次分割后 A 中的结果。 （2 ）A 中的元素是否为堆，如果不是，请将其调整为堆，写出将A 调整成堆后A 中的结果。 三、算法设计题 （30分) 答题要求： ①用自然语言说明所采用算法的思想； ②给出每个算法所需的数据结构定义，并做必要说明； ③用C语言写出对应的算法程序，并做必要的注释。 1．将n(n1)个整数存放到一维数组R 中。设计一个尽可能高效 （时 间、空间）的算法，将R 中保存的序列循环左移p （0pn ）个位置，即 将R 中的数据 （x , x , x ,…, x ），变换为(x ， x , … , x ,x x …, 0 1 2 n-1 p p ＋1 n-1 0 , 1, xp-1) 。(15分) 2 ．给出折半查找的递归算法，并给出算法时间复杂度性分析。 （15分） 《操作系统部分》 一、简单题 （每小题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, 设分配给该程序的存储块数为