《2018年山东大学软件工程专业基础综合考研真题.doc》由会员分享，可在线阅读，更多相关《2018年山东大学软件工程专业基础综合考研真题.doc（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2018年山东大学软件工程专业基础综合考研真题一、解释概念（共 5 题，每题3 分）1、物理格式化（physical formatting）2、饥饿3、临界区4、响应时间5、磁盘调度二、叙述题（共 6 题，每题 10 分）1、三个进程 P1、P2和 P3，到达 优先权 进程 执行时间 到达时间就绪队列的时间和当前所需的 CPU 执行时间，以及优先权如图所示，若采用优先权方法进行调度（优先权值大的进程首先运行），试分别计算抢占和非抢占的情况下，进程的平均周转时间。2、 若CPU硬件提供一条指令TestAndSet，其功能描述如下设计一种方法，通过 TestAndSet 指令实现两个进程之间的互斥
2、。TestAndSet 是否是原子操作?为什么?这种方法是否适合多个进程之间的互斥?主要缺点是什么?3、在实现文件系统时把文件目录的目录项分解成两部分索引结点和符号名目录项。请说明这两部分的主要内容，这样做有什么好处?4、在一个采用分段管理的系统中，段表如下在将下列逻辑地址0，300、1，0、2，580和3，1240转换为物理地址时，得到的结果是什么?5、解决死锁的方法有哪些类?请比较这些方法的优缺点。6、关于高速缓存（cache）和缓冲区（buffer）回答下列问题1）高速缓存一般用在什么地方，有什么作用?2）缓冲区的作用是什么?它和cache有什么区别?三、简答题（共3题，共35分）1、（
3、10分）二叉树的中序序列为ABC，画出该二叉树所有的可能形态。2、（12分）什么是最小堆?对于给定的关键字集合55，31，11，37，46，73，63，2，7，画出其初始最小堆;画出堆排序这些数据的中间过程，并进行简要说明。3、（13分）考虑下图（邻接点按顶点编号升序排列），画出邻接表，从顶点A出发，求它的深度优先生成树和广度优先生成树;并根据普里姆（Prim）算法，画出从顶点A出发的生成最小生成树的过程。四、程序设计题（共3 题，共40分）1、（15分）已知单链表A和 B分别表示了两个集合，设计算法求集合 B对于集合A的补集 A=A-B，同时返回该集合的元素个数。2、（15分）对于给定的单链表，编写算法将奇数序位与偶数序位上的结点进行交换。3、（10分）设计非递归算法实现二叉树的中序遍历。