山东科技大学406数据结构与操作系统2006考研试题研究生入学考试试题考研真题
● 摘要
科目代码：406 请在答题纸（本）上做题，在些试卷或草稿纸上做题无效！ 山东科技大学2006年招收硕士学位研究生入学考试娄所结构与操作系统试卷
数据结构部分
（共3页）
注意事项：
1、算法应说明基本思路，应对主要数据类型、就量给出说明，所写算法应结构清晰、简明易懂，应加上必要的注释。
2、算法可用（类）PASCAL 语言、（类）C 语言等你所熟悉的高级语言编写，但要注明语种。
一、解答下列问题（共30分）：
1、[5分]度量一个程序的执行时间通常有哪几种方法？各有何缺点？
2、[5分]如果元素的进栈序列为123456，问能否得到435612和125426的出栈序列？请说明为什么不能得到或者如何得到。
3、[5分]串是一种特殊类型的线性表，请你从串的存储及操作两方面分析它特殊在什么地方？
4、[5分]给出树的层次遍历序列与后序遍历序列能否唯一确定一棵树？（如能请说明原因，如不能请例说明。）
5、[5分]设有三对角矩阵（a ij ）n*n,将其三条对角线上的元素还行地存于数组B[3n-2],使得B[k]= （a ij ），求用i,j 表示k 的下标变换公式。
6、[5分]基于比较的查找算法所能达到的最优时间复杂度是？基于比较的排序算法所能达到的最优时间复杂度是？
二、[10分]森林的中序遍历结果为DECBAFIKLG ，先序遍历结果为ADCEBIFGKL ，要求：
1、画出此森林。
2、将其转换为二叉树。
3、将得到的二叉树后序线索化。
三、[15分]定义链栈数据类型，并编写函数实现链栈入栈操作。
四、[15分]2路归并排序的一种策略是，先对待排序序列扫描一遍，找出并划分为若干个最大有序子列，将这些子列作为初始归并段。试在链表结构上实现这一排序算法。
五、[15分]试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。用树中结点的关键字均不同。
六、[15分]试写一算法，在图G 中求一条从顶点V i 到顶点V j 的简单路径。
科目代码：406 请在答题纸（本）上做题，在此试卷或草稿纸上做题无效！
数据结构与操作系统试卷
操作系统部分
（共2页）
一、名词解释（本大题共12分，每小题4分）
1．死锁 2．虚拟存储技术 3．SPOOLing 技术
二、问答题（本大题共20分，每小题5分）
1．OS 具有并发、共享、虚拟和异步四个基本特征。如何理解“并发特征是OS 最重要的特征”？
2．简述进程与线程的区别和联系。
3．请对比存储管理技术中分页管理和分段管理两种技术的优缺点。
4．进程有三种基本状态：就绪状态、执行状态和阴塞状态。请给出三种基本状态间可能发生的状态转换和对应的转换条件；在某些操作系统中除以上三种基本状态还引入了挂起状