2022哈尔滨工程大学自命题考研大纲：812软件工程专业基础综

　　附件5：

　　2022年考试内容范围说明

　　考试科目名称: 软件工程专业基础综合 R初试 □复试 □加试

　　数据结构部分

　　考试内容范围:

　　一、绪论

　　1. 了解有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。

　　二、线性表

　　1. 了解线性表的逻辑结构特性是数据元素之间存在线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。

　　2. 熟练掌握顺序存储结构和链式存储结构的描述方法以及线性表的操作在这两种存储结构上的算法实现。

　　3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

　　三、栈和队列

　　1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。

　　2. 熟练掌握栈类型的两种实现方法。

　　3. 熟练掌握循环队列和链队列的基本操作实现算法。

　　4. 理解递归算法执行过程中栈的状态变化过程。

　　四、串

　　1. 理解串类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。

　　2. 理解串类型的各种存储表示和实现，理解串的应用场合。

　　五、 数组和广义表

　　1. 理解多维数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”和“以列为主”的存储表示中的地址计算方法。

　　2. 掌握特殊矩阵的压缩存储表示和实现方法。

　　3. 理解稀疏矩阵的压缩存储方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。

　　4. 理解广义表定义及其从各种基本操作的特点，并能正确利用它们进行广义表的操作。理解广义表的存储表示。

　　六、 树和二叉树

　　1. 领会树和二叉树的类型定义，理解树和二叉树的结构差别。

　　2. 熟记二叉树的主要特性，并掌握它们的证明方法。

　　3. 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。

　　4. 理解二叉树的线索化过程以及在线索化树上找给定结点的前驱和后继的方法。

　　5. 熟练掌握二叉树和树的各种存储结构及其建立的算法。

　　6. 学会编写实现树的各种操作的算法。

　　7. 了解哈夫曼树的特性，掌握建立哈夫曼树和哈夫曼编码的方法。

　　七、 图

　　1. 领会图的类型定义。

　　2. 熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。

　　3. 熟练掌握图的遍历算法，并理解掌握图的连通性问题及相关应用。

　　4. 理解掌握各种图的应用问题的算法及其应用场合。

　　八、 查找

　　1. 理解查找表的结构特点以及各种表示方法的适用性。

　　2. 熟练掌握以顺序表或有序表表示静态查找表时的查找方法。

　　3. 熟练掌握二叉排序树的特点、构造和查找方法。

　　4. 熟练掌握平衡二叉排序树的特点、构造过程和查找方法。

　　5. 理解B-树的特点及查找方法。

　　6. 熟练掌握哈希表的构造和处理冲突方法，深刻理解哈希表与其它结构的查找表的实质性的差别。

　　7. 掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。

　　九、 内部排序

　　1. 理解排序的定义和各种排序方法的特点，并能加以灵活应用。

　　2. 掌握各种排序方法及其时间复杂度和空间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。

　　3. 理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。

　　十、 文件

　　1. 熟悉各类文件的特点、构造方法以及如何实现检索、插入和删除等操作。

　　2. 了解各种文件的适用场合。

　　考试总分：90分 考试时间：1.8小时 考试方式：笔试

　　考试题型：选择题(20分)

　　简答题(25分)

　　计算题(30分)

　　算法题(15分)

　　参考书目(材料)

　　严蔚敏 吴伟民编著，数据结构(C语言版)，北京：清华大学出版社

　　操作系统部分

　　考试内容范围:

　　一、操作系统概述

　　1.理解操作系统的概念、特征、功能和提供的服务。

　　2.了解操作系统的发展与分类。

　　3.了解操作系统的运行环境。

　　二、进程管理与处理机调度

　　1.前趋图、程序顺序执行、程序的并发执行、进程概念及特征、进程的状态与转换、进程控制块。

　　2.进程控制、进程的创建和终止、的阻塞与唤醒、进程的挂起与激活进程。

　　3.进程同步的基本概念、临界区、信号量机制、信号量的应用。

　　4.经典同步问题、讲述生产者—消费者问题、哲学家进餐问题、读者—写者问题。

　　5.管程的基本概念、利用管程解决生产者—消费者问题。

　　6.进程通信概念和类型、消息传递通信的实现方法、消息缓冲队列通信机制。

　　7.线程的引入、进程与线程的区别和联系。

　　三、处理机调度与死锁

　　1.处理机调度的基本概念、进程的高级、中级和低级调度、选择调度方式和调度算法的若干准则。

　　2.典型调度算法：先来先服务调度算法;短作业(短进程)优先调度算法;时间片轮转调度算法;优先级调度算法;高响应比优先调度算法;多级反馈队列调度算法;实时调度;多处理机调度。

　　3死锁的概念，产生死锁的原因和必要条件，处理死锁的基本方法、死锁预防、死锁避免(系统安全状态、银行家算法)、死锁检测和解除。

　　四、内存管理

　　1.内存管理概念、程序装入与链接、逻辑地址与物理地址空间、内存保护。

　　2.连续分配方式：单一连续分配、固定分区分配、动态分区分配(可变分区分配)、伙伴系统、哈希算法、可重定位分区分配、对换与覆盖。

　　3.离散分配管理方式：分页管理方式、分段管理方式、段页式管理方式。

　　4.虚拟内存和抖动的基本概念、页面分配策略、请求分页管理方式和页面置换算法、请求分段存储管理方式。页面置换算法包括最佳置换算法(OPT)、先进先出置换算法(FIFO)、最近最少使用置换算法(LRU)、时钟置换算法(CLOCK)、最少使用(LFU)、页面缓冲算法(PBA)。

　　5.虚拟内存基本概念、请求分页管理方式，并熟练掌握页面置换算法(OPT、FIFO、LRU、CLOCK)。

　　五、设备管理

　　1.I/O设备、设备控制器、I/O通道、I/O控制方式。

　　2.缓冲管理、设备分配与回收、假脱机技术(SPOOLing)。

　　3.磁盘的结构、磁盘调度算法、磁盘存储器管理。

　　六、文件管理

　　1.文件、记录和数据项、文件类型和文件系统模型、文件操作。

　　2.文件的逻辑结构、外存分配方式、文件控制块和索引结点、目录结构、目录查询技术、文件共享、文件保护。

　　3.文件存储空间的管理：空闲表法和空闲链表法、位示图法、成组链接法。

　　考试总分：60分 考试时间：1.2小时 考试方式：笔试

　　考试题型： 选择题(10分)

　　填空题(10分)

　　应用题(40分)

　　参考书目(材料)

　　汤小丹 梁红兵 哲凤屏 汤子瀛编著，计算机操作系统(第四版)，西安：西安电子科技大学出版社