《北京华电大学842数据结构与操作系统》.doc

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