山东某大学软件学院849软件工程专业基础综合历年考研真题汇编.pdf

《山东某大学软件学院849软件工程专业基础综合历年考研真题汇编.pdf》由会员分享，可在线阅读，更多相关《山东某大学软件学院849软件工程专业基础综合历年考研真题汇编.pdf（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目 录2014年山东大学849软件工程专业基础综合考研真题2015年山东大学849软件工程专业基础综合考研真题2016年山东大学849软件工程专业基础综合考研真题2017年山东大学849软件工程专业基础综合考研真题2018年山东大学849软件工程专业基础综合考研真题2014年山东大学849软件工程专业基础综合考研真题山 东 大 学二0一四年招收攻读硕士学位研究生入学考试试题科0 代码 8J9 科目名称 软件工程专业基础综合（答案必须写在答卷纸上，写在试题上无效）一,名词解释（共3题，共15分）1、管程（m o n i t o r）2、DM A3、P CB二,简 答 题（共11题，共85分）1、

2、（5分）画一说明进程在其生命周期中的各个状态，以及各个状态之间转换的条件.2、（5分）解择抖动及其出现的K!因：并解释工作集模型的 作肺必3、汴分）.个请求分贝系统中.如一个进程的中面询问一生为:7,0,I,2,0,3.0,4,2,3,0,3.2,1,2,0,1,7.0,I当分配给该进程的物理块数为3.分别画图说明采用H F O及L R U页面配换算法时的负面徨换过程，计兑访问过程中所发生的缺页次数并解释L R I.醺法优I I-l i O算法的原因？（假定开始时内存中的3个块都是空的，4、（5分）什么处死锁？详述发生死锁的必要条件，5,（5分）操作系统M a c h采用了微内核技术设计实现其

3、内核，说明该技术的军本思想及其主要优缺点、6、（8分）针对有序线件表的插入操作，比较公式化存储、链式存储和M按 址存储的差异.7、（8 分）对于关键字序列 5 0 3,8 7,5 1 2,6 1,9 0 8,1 70,8 9 7,2 75,6 5 3,4 2 6进行基数排疗：（基数取1 0），要求排序结果按递清顺序,写匕排序过程中每趟排序后的结果，8,(1 2 分)设散列表长度为1 3,散列函数为Ha s h(k)-煦 3,依次输入以下序列中的各元索(8 4,5 5,1 0,2 0,1 9,7 9,0 1,6 8,2 7,1 4,I I.2 3),建立链表素列表。(1)、画出该散列表。(2),

4、写出搜索元素2 3,2 7,6 8 的比较次数。(3)、设搜索各元素的概率相等,搜索成功时的平均比较次数是多少？9、(1 0 分)已如以卜.森林，将其转换成二叉树,给出二叉树的先序、后序遇历序列。1 0、(8 分)写出完全二叉树(1 0,6 0,3 2,4 5 ,2 5 ,3 6,4 0,7 2,6 6,2 2)的前序序列，然后将其调整为最大堆，丐出调整后的序列.1 K (1 4 分)对 下 图:(1)写出其邻接矩阵.(2)按 K r u s k al 算法求其最小生成树：花写出相应的边集数组。三、应用分析题(1 5 分)某医院对病人进行体检，在体检处设置了一个容纳5 0 人的休息室供来体检人

5、员休息并等候医生检杳，开始的时候休息室是空的：当有人来进行体检时，若休息室中有空座位,则进入休息率等候检查,否则需要在休息室门门等待0医生每次呼叫个在休息室中等待的人员运入检查室对其进行检杳，无人时医生休息.试写出体构人员和医生的进程,并用信号量及w ai t、s i g n al操作描述他们之间的同步关系四、算法题（共 3题，共35分）1、（1 5分）已知电链表类C h ai n类型,假设单能表A,B分别表不了两个集合，为C h ai n类设计一新的成员函数，该函数求柒合B对J集合A的补兔k A B,同时返回该兔合的元素个数,要求首先给出类的声明,在类的声明中.其它成员函数省略一2.（1 0

6、分）黑小树是M个）点的值都小 或 等 其子节点（如果有的话）价的树,设一义树采用一叉隹表存储结构，设计算法，判断二义树是否为最小树。叙述W法思想并给出算法实现.3、（1（）分）编写程序，利断一个用邻接表存储的勺向图是否存在回路，2015年山东大学849软件工程专业基础综合考研真题山 东 大 学二。一五年招收攻读硕士学位研究生入学考试试题科 目 代 码 849 科目名称 软件工程专业基础综合_（答案必须写在答卷纸上，写在试题上无效）一、名词解释（共3题，共 15分）1、多道程序设计（m u l t i p r o g r am m i n g）2、进程控制块（P C B）3、C PU 周 期（C

7、 PU bu r s t）二、简 答 题（共 H 题，共 85分）1、（5分）操作系统设计的两大目标是什么？不同类型的操作系统是如何满足这两大目标的？2、（5分）为什么现在操作系统对于死锁采用鸵鸟策略？3、（5分）各类进程的C PU bu r s t各有什么特点？这对于C PU调度有何指导意义？4,（5分）简述p ag e-bu f f e r i n g al g o r i t h m的基本思想，该算法有何优点？5、（5分）小王想买一台计算机，主要用于下载和观看电影，从操作系统的角度,你在配置硬件上给他什么建议？并说明原因.6、（8分）树的度为m,度为1的结点数为n l,度为2的结点数为n

8、 2,度为m的结点数为n m,求树的叶子结点数。7、（1 0分）有一个nX n的三对角矩阵A,将A中三条对角线上的元素按对角线（从低对角线到高对角线）存放在维数组B中，使得 ,=%且%存放于B 0.（1）一维数组B有多少个元素？（2）用i,j表示k的地址转换公式。8、（1 5分）设散列表长度为1 3,散列函数为H as h（k）=k%1 3,依次输入以下序列中 的 各 元 素（1 9,1 4,2 3,0 1,6 8,2 0,8 4,2 7,5 5,1 1,1 0,7 9）,建立线性开型寻址散列表。(1)画出该散列表.(2)给出搜索元素2 3,5 5,7 9的比较次数。(3)设搜索各元素的概率相

9、等，搜索成功时的平均比较次数是多少？9、(8分)二叉树给出按关键字序列(2 0,3 6,8 8,1 2,1 6,7 7,5 0)生成的二叉搜索树和A VL搜索树。1 0、(1 0分)请给出最小生成树的Kr u s k al算法描述，用Kr u s k al算法构造以下网络的最小生成树，并求出该树的代价。1 1、(9分)对于下面的有向图，试给出：(1)邻 接 矩 阵(2)邻接表(3)从出发的深度优先遍历序列；从出发的广度优先遍历序列;三、应用分析题(1 5分)1、假定系统中共计有5个磁带机，2个显示器、4台打印机、3块磁盘。已知为以下4个进程分配资源如下：Process NameTape Dri

10、vesGraphicsPrintersDisk DrivesProcess A2011Process B0100Process C1011Process D1101各进程尚需的资源情况如下:Process NameTape rivesGraphicsPrintersDisk DrivesProcess A1100Process B0112Process C3100Process D0010请问系统目前处于安全状态吗？给出分析过程.2,描述具有非忙等待特性的信号量的实现，并运用该信号量解决存储空间为N的生产者一消费者问题。四、算法题（共3 题，共35分）1、（10分）二叉树采用二叉链表存储结构，

11、设计算法，判断二叉树是否为完全二叉树.叙述算法思想并给出算法实现.2、（10分）二叉树采用二叉链表存储结构，写出中序遍历该二叉树的非递归算法.叙述算法思想并给出算法实现。3、（15分）假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）.（注：图中不存在顶点到自己的边）2016年山东大学849软件工程专业基础综合考研真题山东大学二。一六年招收攻读硕士学位研究生入学考试试题科目代码 849 科目名称 软件工程专业基础保合（答案必须写在答卷纸上，写在试题上无效）一解释概念（共5题，15分）I、中版服务程序2、纨程

12、序技术3、CPC内核态k-（threshing）5、义件控制块（F C B）二、叙述题（共6题，60分）I.简要说明目前PC机上的操作系统除;舟过程，2,若系统将进程的状态分为新建、结束、相塞.执行和就绪A种状态,试说明这五肿状态2间的相互转换关系.并分别举例说明是什么事件促成了状态之间的转换.3,设盯四个进程，到这就绪队列时间及执行时间如卜表所示，苫分刖采用剥夺式同短作业优先嫡度和工级反馍队列调度（箕中一级和二级队列果用时间片调度，时间片分别为2和4,三级队列乘用FC FSiffi度），分别给出各进程的调度次序及平均等他时间（给出计售过程）进程 到达就绪队列时间 执 行 而 一P/0 6P2

13、 8Pi 2 3P4 3 124、文件系统果用混今索引结构,设次长为512字 上 块 号 占2个字节，文件控制块巾的直接索山坎号有10个，另有分别指向一、二级索引的两个指针，试问该文件系统故多能存储多大的文件？淞今索引有什么优点？5、打一个停车场，可以停放2Q0辆汽乍.停乍场的入口是;I有一个车道,出口有三个位机谛用途号编写M实现 I部之间的同步大系，6、在一个采用分段管理的系统中，段展如图所加，在将卜列遗料地址：0,300、I.0,2,580 3,12：转换为物理地址时,得到的结果是什么？三、简答题（共4题，50分）段号基地址段长020035()700120022000500；1(X1001

14、234I、（12分）写出二分山战算法的*木祖也.甘单点我的节点超按关健字升序傩接,能否用二分查找法进行查找，为什么？2、（1 2分）描述归并排序加快速揖序算法的基本思想，举例说明,分析其募法复杂度和算法适用情况。3、（12分）南出依次插入关健字21,II,17,7,9,33,27,25生成的二义搜索树.1一 卜；分）所出下面有向图的邻接矩阵、邻接表.写出邻接我表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列，四、程序设计题（共2题，25分）I,（12分）设二叉搜索树采用二叉链表存储结构，编写算法剧除给定美健字x对应的结，乩2、（13分）什么是图的连通分量？对于给定的无向图,编写算法标记

15、出图中所有直通分量,2017年山东大学849软件工程专业基础综合考研真题山东大学二0一七年招收攻读硕士学位研究生入学考试试题科目代码 849 科目名称 软件工程专业基础综合(答案必须写在答卷纸上，写在试题上无效)一、解释概念(共5 题，每题3 分)R 内 核(kernel)2、计时器(Timer)3、进 程(process)4、对 换(swapping)5、动态装入(dynamic loading)二 叙述题(共6 题，每题10分)1、简要描述进程调度中多级反馈队列调度算法的基本思想，并且说明它在哪些方面体现了进程调度的基本准则.2、系统中有两个进程P1和P2,他们的执行过程如图所示.试用信号

16、量机制编写代码，描述这两个进程之间的同步关系。进程P 1W hile(true)进程P2W hile(true),申请磁带机申请打印机使用磁带机使用打印机申请打印机申请磁带机同时使用磁带机和打印机同时使用打印机和磁带机释放磁带机释放打印机释放打印机释放磁带机113、在一个采用分段内存管理的系统中，段表如下,段号基地址段长02 0 03 5 017 0 01 2 0 022 0 0 05 0 031 0 0 0 01 2 3 4在将下列逻辑地址：0,3 0 0、1,0 ,2,5 8 0 和 1 2 3 4】转换为物理地址时,得到的结果是什么？4、在一个多线程的进程中，线程之间可以共享如下哪些资源

17、：1）寄存照；2）堆；3）检；4）全程变量；5）T/O端门，并说明共享或不能共享的理由。5、什么是虚拟文件系统（v i s u al f i l e s ys t e m）?它与普通文件系统有什么不同？说明虚拟文件系统的基本结构.6、简 述 磁 盘 的 物 理 格 式 化（p h ys i cal f o r m at t i n g）和 逻 辑 格 式 化（l o g i calf o r m at t i n g）-般是由谁、在什么时候来做的？这两个操作所完成的主要:作是什么？三,简答题（共4题，50分）I、（1 3分）假设分6个从小到大排好序的有序表,它们分别含有2 0、3 0、4 0、

18、6 0、7 0和1 0 0个整数，现要通过5次两两合并，将它们最终合并成一个有序表，同：应该按怎样的次序进行这5次合并，以使所有可能使用的最大的总比较次数最小？请简要给出求解过程.2、（1 3分）对于给定的一组关键字输入序列 5 5,3 1,1 1,3 7,4 6,7 3,6 3,2,7 ,从空树开始构造一义搜索树，画出每加入个新节点时的二叉树形态，对于最终形成的二叉搜索树，分别计算等概率瓷找各关健字情况下，瓷找成功和不成功的平均查找次数。3、（】2分）写出二分查找算法的基本思想.若呻.橙表的节点是按关健字升序链接，能否用二分查找法进行查找，为什么？4、（12分）给定邻接链表方式存储的无向图G

19、（V,E）,如下图所示要求:写出此图的邻接矩阵表达形式，并画出该图的深度优先和广度优先生成树。1 2 7-42川 一3f43fli2T4-*l-2-*3-*55-2-4四,程序设计题（共2 题，25分）】、（13分）二义树中两个结点之间的距离定义为结点之间的路径长度。设一义树采用二叉链表存储结构，对于给定二叉树中的两个结点，编写算法计算它们之间的距离。2、（12分）给定n个整数，设计快速排序算法；然后适当改进算法求解第k大的数。2018年山东大学849软件工程专业基础综合考研真题山 东 大 学二。一八年招收攻读硕士学位研究生入学考试试题科目代码 849 科目名称 软件工程专业基础综合（答案必须

20、写在答卷斑上，写在试题上无效）一解释概念（共 5 题，每题3 分）k 物理格式化（physical formatting）2,饥饿3、临界区4、响应时间5、破盘调度二、叙述题（共 6 题，每题10分）k三个进程Ph P2和 P 3,到达就绪队列的时间和当前所隔的CPU执行时间,以及优先权如图所示，若采用优先权方法进行调度（优先权值大的进程首先运行），试分别计算抢占和非抢占的情况下，进程的平均周转时间.进程到达时间执行时间优先权P1051P2342P36332,若CPU硬件提供一条指令TestAndSet,其功能描述如下:boolean TestAndSet(boolean*target)boo

21、lean rv=*target;target=TRUE;return rv:)设计一种方法，通过Te s t A n dSe t指令实现两个进程之间的互斥。Te s t A n dSe t是否是原子操作？为什么？这种方法是否适合多个进程之间的互斥？主要缺点是什么？3、在实现文件系统时把文件目录的目录项分解成两部分：索引结点和符号名目录项。清说明这两部分的主要内容，这样做有什么好处？4、在一个采用分段管理的系统中，段表如下：段号基地址段长02 0 0560170 03 40 022 0 0 058031 0 0 0 01 2 3 0在将下列逻辑地址：0,3 0 0,I,0.2,580 和3,1

22、2 40 转换为物理地址时，得到的结果是什么？5,解决死锁的方法有哪些类？请比较这些方法的优缺点.6,关于高速缓存（ca ch e）和缓冲区（bu f f er）回答下列问题：D高速缓存一般用在什么地方，有什么作用？2）缓冲区的作用是什么？它和ca ch e有什么区别？三、简答题（共3题，共35分）1、（1 0分）二叉树的中序序列为A B C,画出该二叉树所有的可能形态.2、（1 2分）什么是最小堆？对于给定的关键字集合 55,3 1,1 1,3 7,46,73,63,2,71,画出其初始最小堆；画出堆排序这些数据的中间过程，并进行简要说明。3、（1 3分）考虑下图（邻接点按顶点编号升序排列），画出邻接表，从顶点A出发,求它的深度优先生成树和广度优先生成树；并根据普里姆（P r i m）算法，画出从顶点A出四、程序设计题（共3题，共40分）1、（15分）己知单链表A和B分别表示了两个集合，设计算法求集合B对于集合A的补集A=A-B,同时返回该集合的元素个数.2,（15分）对于给定的单链表，编写算法将奇数序位与偶数序位上的结点进行交换.3、（10分）设计非递归算法实现二叉树的中序遍历.平台简介及