《2019年山东大学软件工程专业基础综合考研真题.doc》由会员分享，可在线阅读，更多相关《2019年山东大学软件工程专业基础综合考研真题.doc（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2019年山东大学软件工程专业基础综合考研真题一、简答题（共50分）1.（10分）对关键字序列（7、9、2、3、0、8、1、8*、6），用下列排序算法进行递增排序，写出第一趟结束后的序列（注8和8*分别表示第一次出现的8和第二次出现的8）1）冒泡排序 2）快速排序（选第一个记录为支点） 3）插入排序2. （10分）假定采用下述公式来描述一个线性表其中M a x S i ze是用来存储表元素的数组的大小。与专门保留一个表长的做法不同的是，用变量 first 和last 来指出表的第一个元素和最后一个元素的位置。基于该公式1）first 和1 a s t的初始值应该是多少?2）对于新的类，试描述如
2、何删除元素。3）分析删除操作的时间复杂性。3.（10分）一棵高度为h的完全k 叉树，如果按层次从上而下，从左向右，按顺序从1开始对全部结点编号。问该树最多有多少个结点?最少有多少个结点?4.（10分） 假设某个字母表各个字母的权分别为按照这个字母表，一个长度为n的字符串采用霍夫曼编码在最坏及最好情况下各需要多少位?为什么?5.（10分）对下图，使用Kruskal算法求其最小生成树。二、程序设计题（共25分）1.（12分）设计算法，删除链式存储二叉树所有的叶结点。说明算法思想，给出算法代码，并分析算法的时间复杂度以及空间复杂度。2.（13分）假设图以邻接链表表示，试写出广度优先遍历的非递归算法。
3、操作系统一、概念解释（每小题4分，共20分）1. 临界区2.分时系统3.存储保护4. 管程5. 设备驱动程序二、简答题（每题11分，共55分）1.在调页式虚拟内存管理中，某进程的页访问序列为0，1，2，1，3，4，1，3，0，3，2。若采用 LRU页置换策略，则产生缺页异常的次数是多少?举例说明一种LRU 算法的近似方法，并解释 LRU 算法的可行性依据。2.下列 CPU调度方法中;1）非抢占式短作业优先法2）时间片轮转法;3）静态优先权方法;4）抢占式短作业优先法;5）先来先服务，哪些会产生饥饿问题?解释为什么。说明死锁与饥饿的主要区别。3.试绘图描述分页系统的地址变换过程，其中页表的内容是何时、由谁来填写的?页表中的地址是物理地址还是逻辑地址?4. 操作系统中进程的基本状态一般有哪些?说明各种进程状态之间的转换关系，以及转换的原因。5.某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题（1） 在连续、链式、索引三种文件的数据块组织方式中，哪种更合适该文件系统?要求说明理由。为定位文件数据块，需在 FCB中设计至少哪些相关描述字段?（2）为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块一起存储好?说明理由。