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