2018山东科技大学研究生入学考试823数据结构与操作系统真题.pdf
数据结构部分一、简答题(30 分,每题 5 分)1、串、数组、广义表从元素间关系上可以看成线性结构,它们与一般意义上的线性表相比有何特殊性?2、借助栈可以实现更复杂的操作,请简述如何利用栈实现对表达式中括号是否匹配的检验。3、基于关键字比较的查找算法所能达到最优时间复杂度是?能否设计一种与问题规模无关的查找算法?请给出基本思路。4、图的广度优先遍历与树的何种遍历策略相似?请给出简单解释。5、数据结构中经常采用“树形化组织”的方式来整理数据,比如折半查找表、二叉排序树、大顶堆/小顶堆等,请简述这样做的优点。6、何为稳定的排序方法?何为不稳定的排序方法?哪些排序算法是不稳定的?二、综合应用题(40 分,每题 10分)1、假设用于通信的电文共有 8 个字母 A,B,C,D,E,F,G,H组成,字母在电文中出现的频率分别是0.2,0.04,0.06,0.02,0.12,0.24,0.25,0.07。试为这 8 个字符设计哈夫曼编码;试设计另一种由二进制表示的等长编码方案;对于上述实例,比较两种方案的优缺点。2、试找出满足下列条件的二叉树:先序序列与后序序列相同;中序序列与后序序列相同;先序序列与中序序列相同;中序序列与层次遍历序列相同。3、已知图的邻接表结构为(其中边节点数据域分别为:邻接点编号、边的权值、指向下一条关联边的指针):A 1 6BCDEF0123454 5 0 6 2 101 10 3 8 4 11 2 8 4 12 0 5 1 7 2 11 5 12 4 7 画出该图;给出从顶点 A开始的深度优先遍历序列;给出从顶点 A开始的广度优先遍历序列;给出图的一种最小生成树。4、设待排序的关键字序列为15,70,16,65,46,37,17,60,12,86,试分别完成以下任务:请写出链式基数排序的过程;讨论该排序算法的时间复杂度与空间复杂度。三、算法设计题(20 分,每题 10分)1、已知非空线性链表由 L 指出,链结点的构造为(data,link),请写一算法,将链表中数据域值最大的那个链结点移到链表的最前面。2、已知二叉树采用二叉链表存储,设计一个算法求二叉树中指定节点所在的层数。操作系统部分四、基础题(每小题 5分,共 30分)1、单处理器操作系统的多个进程无法实现并行操作,如果要提高处理器利用率,主要采用什么技术?并对这一技术进行说明。2、某操作系统的一个进程从移动存储设备读入一个文件到内存中,该操作系统所在的计算机系统采用 DMA 控制器实现字节传输。请简述DMA传输文件到内存的主要过程。3、操作系统中采用虚拟机结构的主要优点是什么?举出一种常用的虚拟机规范,并简要说明其工作过程。4、进程死锁发生的必要条件是什么?对每个条件进行说明。5、操作系统的目录结构的主要作用是什么?目录中主要包含哪些信息?6、列举三种主要的操作系统类型,并简要说明每种类型的特点。五、应用题(共 30 分)1、在虚拟存储管理中,操作系统需要为多个进程分配一定数量的物理内存块(帧),分配方法有很多种,例如固定分配、优先级分配等,但如果分配方法不当,容易引起页面在内外存之间频繁的换入换出,使得系统性能(主要是处理器利用率)下降。为减少这一问题出现的可能性,除了经常采用的工作集机制以外,还可以通过编写高质量的程序代码这一方法进行解决。假设某操作系统的页大小为 1024个字,给每个进程分配一个物理内存块。有一个矩阵定义如下:int A = new int10241024;如果该矩阵按行存放,每一行存储在一页中,则下述程序代码会产生10241024 次缺页。for (j=0; j A.length; j+) for (i=0; i A.length; i+)Ai, j = 0;请对上述代码进行改进,使之产生最少的缺页次数,并说明原因。(8分)2、有 5 个进程 A,B,C,D,E,它们几乎同时先后达到,预计它们运行的时间为 10s,6s,2s,4s,8s。其优先级分别为 3,5,2,1,4,这里1 为最高优先级。对优先级调度和短作业优先调度算法,计算该系统的平均周转时间和平均带权周转时间。(不考虑进程之间的切换开销)(10分)3、桌上有一个空盘子,盘子中最多允许放置一个物品。有两个厨师甲和乙,分别带着自己的徒弟 A 和 B,徒弟 A 向盘子中放置食材 1,徒弟B 向盘子中放置食材 2,厨师甲从盘子中取食材 1,厨师乙从盘子中取食材 2。请用信号量机制实现两个厨师和两个徒弟四个并发进程的同步过程。(12分)