华北电力大学（北京）

华北电力大学2021年硕士生入学考试初试科目考试大纲

科目代码：842

科目名称：数据结构与操作系统

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

第一部分：数据结构

一、考试的总体要求与目标

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

二、考试的内容

1. 基本概念和术语

2. 线性表

线性表的定义;线性表的逻辑结构;线性表的存储结构(顺序存储、链式存储);不同存储方式下操作的实现;线性表的应用。

3. 栈与队列

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

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

4. 树和二叉树

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

树和森林：树(森林)的基本概念;树(森林)的逻辑结构;树(森林)的存储结构(双亲表示法，孩子链表表示法，孩子兄弟链表表示法);树(森林)的基本操作实现;树(森林)与二叉树之间的相互转换;树(森林)的应用。

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

5. 图

图的定义与基本概念;图的逻辑结构;图的存储结构(邻接矩阵、邻接表、邻接多重表、十字链表);不同存储结构上的基本操作实现;图的遍历(深度优先遍历，广度优先遍历);图的应用。

6. 查找

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

7. 排序

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

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

三、考试的题型

选择题、填空题、判断题、简答题、综合应用题、算法设计题

四、参考书目

1. 林碧英，石敏，焦润海. 新编数据结构与算法教程.清华大学出版社.

第二部分：操作系统

一、考试的总体要求

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

二、考试的内容

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

2.操作系统概述：

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

3. 进程管理：

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

4.处理机调度与死锁：

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

5.存储器管理：

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

6.设备管理：

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

7.磁盘管理：

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

8.文件管理：

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

三、考试的题型

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

四、参考书目

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

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