2019年山东大学软件工程专业基础综合考研真题.doc

发布时间：2022-09-16 发布人：admin 分类：说明书资料大小：0.16M 资料格式：doc 举报版权申诉

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

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）对于新的类，试描述如何删除元素。 3）分析删除操作的时间复杂性。 3.（10 分）一棵高度为 h 的完全 k 叉树，如果按层次从上而下，从左向右，按顺序从 1 开

始对全部结点编号。问∶该树最多有多少个结点?最少有多少个结点? 4.（10 分）假设某个字母表各个字母的权分别为∶ 按照这个字母表，一个长度为 n 的字符串采用霍夫曼编码在最坏及最好情况下各需要多少位? 为什么? 5.（10 分）对下图，使用 Kruskal 算法求其最小生成树。二、程序设计题（共 25 分） 1.（12 分）设计算法，删除链式存储二叉树所有的叶结点。说明算法思想，给出算法代码，并分析算法的时间复杂度以及空间复杂度。 2.（13 分）假设图以邻接链表表示，试写出广度优先遍历的非递归算法。

操作系统一、概念解释（每小题 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，是集中存储好，还是与对应的文件数据块一起存储好?说明理由。

分享到：

赞收藏

资料库

2019年山东大学软件工程专业基础综合考研真题.doc

相关推荐

考研

热门标签

最新资料