华北电力大学2024年非全日制研究生招生考试《软件工程专业基础综合》考试大纲

　　考试科目编号：843

　　考试科目名称：软件工程专业基础综合

　　本门课程由数据结构和操作系统两门课程组成，两门课程各占 75分 ，具体要求如下：

　　第一部分：数据结构

　　一、考试的总体要求

　　掌握数据结构的基本概念、原理和方法。掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度和空间复杂度分析。能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用 C 语言设计与实现算法的能力。

　　二、考试的内容

　　1.绪论

　　数据结构的基本概念，数据的逻辑结构、存储结构。

　　算法的定义、特性和设计要求，算法的时间复杂度分析与空间复杂度分析。

　　2.线性表

　　线性表的定义;线性表的逻辑结构;线性表的存储结构(顺序存储、链式存储)，两种存储方式的特点和适用场合;不同存储方式下基本操作的实现;线性表的应用。

　　3.栈与队列

　　栈：栈的定义和基本概念;栈的逻辑结构;栈的存储结构(顺序存储，链式存储);不同存储方式下基本操作的实现;栈的应用。

　　队列：队列的定义和基本概念;队列的逻辑结构;队列的存储结构(顺序，链式);不同存储方式下基本操作的实现;队列的应用。

　　4.二叉树与树

　　二叉树：二叉树的定义和基本概念;二叉树的基本性质;二叉树的逻辑结构;二叉树的存储结构(顺序、链式);不同存储结构上的基本操作实现;二叉树的遍历及应用;线索二叉树的基本概念和构造。

　　树与森林：树(森林)的定义和基本概念;树(森林)的逻辑结构;树(森林)的存储结构(双亲表示法，孩子链表表示法，双亲孩子链表表示法，孩子兄弟链表表示法);树(森林)的基本操作实现;树(森林)的遍历及应用。

　　树(森林)与二叉树之间的相互转换以及遍历的对应关系。

　　哈夫曼树(最优二叉树)和哈夫曼编码。

　　5.图

　　图的定义与基本概念;图的逻辑结构;图的存储结构(邻接矩阵、邻接表、邻接多重表、十字链表);不同存储结构上的基本操作实现;图的遍历(深度优先遍历，广度优先遍历)及应用;图的应用(最小生成树、最短路径、AOV网及拓扑排序、AOE网及关键路径)。

　　6.查找

　　查找的基本概念与术语;静态查找表(顺序查找、折半查找、分块查找);动态查找表(二叉排序树、二叉平衡树和B-树);哈希表(哈希表的概念、常用的哈希函数、解决冲突的方法);查找算法的分析(ASL)及应用。

　　7.排序

　　排序的基本概念;插入类排序(直接插入排序、折半插入排序、希尔排序)、交换类排序(冒泡排序、快速排序)、选择类排序(简单选择排序、堆排序)、归并类排序(二路归并排序)、基数排序;各种内部排序算法的稳定性和时间复杂度与空间复杂度分析;排序算法的应用。

　　8.综合应用：根据实际问题，设计有效的数据结构和算法，并进行时间复杂度分析。

　　三、考试的题型

　　选择题、填空题(概念及算法)、算法应用题、算法设计题。

　　四、参考书目

　　1.林碧英，石敏，焦润海. 新编数据结构及算法教程(第 2 版).清华大学出版社,2021.

　　2.石敏，焦润海，周长玉等.数据结构与算法慕课(www.xuetangx.com).

　　第二部分：操作系统

　　一、考试的总体要求

　　要求考生熟练掌握计算机操作系统中的基本概念、基本原理; 从资源管理角度掌握计算机操作系统的主要功能及设计思想;了解和掌握现代计算机系统对其各种软硬资源的管理方法及实现技术;了解当代计算机操作系统的新技术与发展趋势。

　　二、考试的内容

　　1.掌握与操作系统相关的基本概念。

　　2.操作系统概述：

　　包括操作系统的概念;操作系统的发展过程;操作系统的分类;操作系统的特征;操作系统的功能;操作系统接口;常用操作系统的结构特点。

　　3.进程管理：

　　包括进程的概念;进程控制(进程的状态机转换);进程同步;经典的进程同步互斥问题;进程通信;线程的定义及实现。

　　4.处理机调度与死锁：

　　包括处理机调度的概念;调度方式及算法;死锁的概念;死锁产生的原因;死锁的处理策略。

　　5.存储器管理：

　　包括程序的装入和链接;连续分配存储管理方式;覆盖与交换;分页存储管理方式;分段存储管理方式;段页式存储管理方式;虚拟存储器的概念;局部性原理;缺页中断;请求分页存储管理方式;页面置换算法;请求分段存储管理方式;逻辑地址到物理地址的转换。

　　6.设备管理：

　　包括 I/O系统的组成;I/O控制方式;I/O软件层次结构;设备独立性;缓冲管理;SPOOLing技术;设备分配;设备处理(驱动)。

　　7.磁盘管理：

　　包括磁盘调度;磁盘空闲存储空间的管理;磁盘阵列。

　　8.文件管理：

　　包括文件和文件系统的概念;文件控制块 FCB;索引节点;文件逻辑结构;目录管理;外存分配方法(文件物理结构);FAT表;文件保护。

　　三、考试的题型

　　选择题、填空题、综合应用题。

　　四、参考书目

　　1.邹鹏，操作系统原理与实践，北京：高等教育出版社，2008.

　　2.汤小丹等，计算机操作系统，第四版.西安：西安电子科技大学出版社，2014.