文档介绍：华北电力大学2018年硕士生入学考试初试科目考试大纲
科目代码:842
科目名称:数据结构与操作系统
本门课程由数据结构和操作系统两门课程组成,两门课程各占75分,具体要求如下:
第一部分:数据结构
一、考试的总体要求
掌握数据结构中常用的逻辑结构、存储结构和基本操作,灵活运用所学的数据结构解决实际问题;掌握典型的查找和排序算法,并能够针对不同特征的数据集进行有效应用;能够分析算法的时间复杂度,设计具有较高时空性能的算法。
二、考试的内容
1、基本概念和术语
2、线性表
线性表的定义;线性表的逻辑结构;线性表的存储结构(顺序存储、链式存储);不同存储方式下操作的实现;线性表的应用。
3、栈与队列
栈:栈的定义;栈的逻辑结构;栈的存储结构(顺序存储,链式存储);不同存储方式下操作的实现;栈的应用。
队列:队列的定义;队列的逻辑结构;队列的存储结构(顺序,链式);
不同存储方式下操作的实现;队列的应用。
4、树和二叉树
二叉树:二叉树的概念;二叉树的基本性质;二叉树的逻辑结构;二叉树的存储结构(顺序、链式);各存储结构上的基本操作实现;二叉树的应用。
树和森林:树(森林)的基本概念;树(森林)的逻辑结构;树(森林)的存储结构(双亲表示法,孩子链表表示法,孩子兄弟链表表示法);树(森林)的基本操作实现;树(森林)的应用。
树(森林)与二叉树之间的相互转换;
哈夫曼树(最优二叉树):哈夫曼树的定义、哈夫曼树的存储与应用。
5、图
图的定义与基本术语;图的逻辑结构;图的存储结构(邻接矩阵,邻接表及逆邻接表);不同存储结构上的基本操作实现;图的应用。
6、查找
基本概念与术语;静态查找(顺序查找、折半查找、分块查找);动态查找(二叉排序树、二叉平衡树和B-树的查找、插入和删除);哈希查找(哈希表的概念、常用的哈希函数、解决冲突的方法);查找性能分析(平均查找长度);
7、排序
插入类排序(直接插入排序、折半插入排序、希尔排序)、交换类排序(冒泡排序、快速排序)、选择类排序(简单选择排序、堆排序)、归并类排序(二路归并排序)、基数排序
;各种排序方法的稳定性和时间性能分析。
:根据实际问题,设计有效的数据结构和算法,并进行时间复杂度分析。
三、考试的题型
选择题、填空题、综合题、算法设计题
第二部分:操作系统
一、考试的总体要求
要求考生熟练掌握计算机操作系统中的基本概念、基本原理; 从资源管理角度掌握计算机操作系统的主要功能及设计思想;了解和掌握现代计算机系统对其各种软硬资源的管理方法及实现技术;了解当代计算机操作系统的新技术与发展趋势。