文档介绍：华北电力大学2017年硕士生入学考试初试科目考试大纲
科目代码:842
科目名称:数据结构与操作系统
本门课程由数据结构和操作系统两门课程组成,两门课程各占75分,具体要求如下:
第一部分:数据结构
一、 考试的总体要求
掌握数据结构的基本概念和术语;掌握线性表、栈、队列、二叉树、树和图的逻辑结构、存储结构以及常用操作;掌握查找和内排序的各种方法;设计具有较高时空性能的算法。
二、 考试的内容
1、概述
数据结构的基本概念与理解;相关术语包括:数据,数据元素,数据项,数据对象,逻辑结构,存储结构,抽象数据类型;四种基本的逻辑结构;两种基本的存储结构。
算法相关内容,包括:算法定义;算法的5大特性;算法设计要求;时间复杂度;空间复杂度;语句频度。
线性表
线性表的定义;线性表的逻辑结构;线性表的顺序存储(顺序表);线性表的链式存储(单链表,循环链表,双向链表);不同存储方式下基本操作的实现
,包括:初始化、创建、插入、删除、查找、修改、求表长、遍历、输出等;基于各基本操作的简单应用。
栈与队列
栈的定义;栈的逻辑结构;栈的存储结构(顺序栈,链栈);不同存储方式下基本操作的实现,包括:初始化、入栈、出栈、取得栈顶元素、判栈空、判栈满、遍历等;栈的简单应用。
队列的定义;队列的逻辑结构;队列的存储结构(顺序,链式);不同存储方式下基本操作的实现:初始化、入队、出队、队空、队满的判定条件、求队列长度、遍历等;队列的简单应用。
4、树和二叉树
二叉树的基本概念与术语;二叉树的5个基本性质;二叉树的逻辑结构;二叉树的存储结构(顺序、链式);各存储结构上的基本操作,包括:创建、前序(中序、后序)三种遍历、层次遍历、求结点个数、求叶子个数、求深度;基于遍历的简单应用。
树(森林)的基本概念与术语;树(森林)的逻辑结构;树(森林)的存储结构(双亲表示法,孩子链表表示法,孩子兄弟链表表示法);树(森林)的基本操作,包括:创建、查找、插入、删除、求深度、先根(先序)遍历和后根(中序)遍历;基于树(或者森林)的遍历的简单应用。
二叉树和树(森林)的典型应用,包括:由两种遍历序列确定一棵二叉树;由两种遍历序列确定一棵树(或森林);树(森林)与二叉树之间的相互转换;
哈夫曼树(最优二叉树),包括:哈夫曼树的定义及术语、哈夫曼树的逻辑结构、哈夫曼树的存储结构、哈夫曼编码、WPL、构造哈夫曼树(逻辑结构及存储结构的变化过程)。
图
图的定义与基本术语;图的逻辑结构;图的邻接矩阵存储结构;图的邻接表及逆邻接表存储结构;两种存储上基本操作,包括:创建、深度遍历、广度遍历。
图的典型应用,包括:判断回路、最小生成树(prim算法、kruscal算法)、最短路径(迪杰斯特拉算法、floyd算法)、拓扑排序、关键路径;基于遍历的其他简单应用。
查找
查找相关的基本概念与术语;几类常用的查找,包括:线性表查找、树表查找、哈希表等。
线性表查找,包括:顺序查找、折半查找、分块查找;以上几种线性表查找的算法及性能分析(查找成功与不成功时的平均查找长度)。
树表查找,包括:二叉排序树的构造、查找、删除与查找性能分析(平均查找长度);平衡二叉树的构造、查找、删除与查找性能分析(平均查找长度);
哈希表,包括:哈希表的概念、常用的哈希函数、