数据结构考试大纲.docx

一、 本课程的地位、作用和任务
    数据结构是计算机专业（包括软件、应用和科学教育等专业）的主干课、专业基础课，主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。通过教学要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，并为后续课程的学习打下良好的理论基础和实践基础。

    二、 课程内容及学时分配
    第一章 绪论
    (1)数据、数据对象、数据结构、数据类型
    (2)算法及算法描述
    (3)算法的时间复杂度和空间复杂度
    本章学时数：2，本章习题数：4

    第二章 线性表
    2.1 线性表的逻辑结构 
    线性表的形式定义及基本操作
    2.2线性表的顺序存储结构
    (1)线性表的顺序存储结构描述
    (2)在顺序存储结构表示方式下线性表基本操作的实现
    2.3 线性表的链式存储结构
    (1)线性表的单链表表示及其实现方法
    (2)循环链表 (a)表示 (b)运算
    (3)双向链表 (a)类型描述 (b)运算实现
    2.4一元多项式的表示及相加
    (1) 一元多项式的线性表表示
    (2)一元多项式基本操作的实现
    本章学时数：6，本章习题数：10

    第三章 栈和队列
    3.1 栈
    (1) 抽象数据类型栈的定义
    (2) 栈的顺序存储和链接存储
    (3) 栈基本操作的实现
    3.2 表达式求值
    栈的应用--表达式求值 (a)算法描述 (b)操作过程
    3.3 栈与递归过程
    (1)递归算法执行过程中栈的状态变化过程
    (2)递归过程转化成非递归过程的变换方法
    3.4 队列
    (1)抽象数据类型队列的定义
    (2)队列的链式存储结构
    (3)队列的顺序存储结构
    本章学时数：6，本章习题数：10

    第四章 串
    4.1 串及其操作
    (1)串的概念
    (2)串的基本操作
    4.2 串的存储结构
    (1) 串的静态存储结构 (a)非紧缩格式 (b)紧缩格式
    (2)串的动态存储结构 (a)串的链表存储方式 (b)存储密度
    4.3串基本操作的实现
    (1) 静态结构存储串时的操作 (a)联接函数 (b)求子串函数 (c)定位函数
    (2) 模式匹配的改进算法 
    (3)堆结构存储串时的操作 (a)赋值操作 b)联接运算 (c)求子串操作
    4.4 串操作应用举例(自学)
    串的应用及实现
    本章学时数；4，本章习题数：6

    第五章 数组和广义表
    5.1 数组的定义和运算
    (1) 二维数组、n维数组的逻辑结构
    (2) 数组的基本操作
    5.2 数组的顺序存储结构
    (1) 以行序为主序的存储结构
    (2) 以列序为主序的存储结构
    5.3矩阵的压缩存储
    (1)特殊矩阵和稀疏矩阵 (a)下（上）三角矩阵 (b)对角矩阵 (c)稀疏矩阵
    (2)三元组表 (a)形式描述 (b)转置运算 (c)相乘运算
    (3)十字链表 (a)形式描述 (b)加法运算
    5.4 广义表的定义
    广义表的定义和特点
    5.5 广义表的存储结构
    广义表的链式存储结构表示
    5.6 m元多项式的表示(自学)
    三元多项式的广义表表示
    本章学时数：4，本章习题数：8

    第六章 树和二叉树
    6.1 树的结构的定义和基本操作
    (1)树的定义及基本术语
    (2)树的基本操作
    6.2 二叉树
    (1)二叉树的定义和操作
    (2)二叉树的性质 
    (3) 二叉树的存储结构 （a）顺序存储结构 (2)链式存储结构
    6.3 遍历二叉树和线索二叉树
    (1)遍历二叉树的操作定义与算法描述 (a)先序遍历 (b)中序遍历 (c)后序遍历
    (2)线索二叉树定义及存储结构 (a)线索链表 (b)二叉树的线索化
    (3)线索二叉树的基本操作
    6.4 树和森林
    (1)树的存储结构 (a)双亲表示法 (b)孩子表示法 (c)孩子兄弟表示法
    (2)森林与二叉树的转换 (a)森林转换成二叉树 (b)二叉树转换成森林
    (3)树的遍历 (a)先序遍历 (b)中序遍历 (c)后序遍历
    6.5 树与等价问题
    (1)等价问题描述及其抽象数据类型
    (2)基本操作实现
    6.6 哈夫曼树及应用
    (1)哈夫曼树定义及哈夫曼算法描述
    (2)哈夫曼编码 (a)前缀编码概念 (b)求哈夫曼编码的算法
    本章学时数：12，本章习题数：15

    第七章 图
    7.1 图的定义和术语
    (1)图的基本概念
    (2)图的基本操作
    7.2 图的存储结构
    (1)数组表示法 (a)形式描述 (b)邻接矩阵
    (2)邻接表 (a)邻接表 (b)逆邻接表
    (3)十字链表 (a)存储结构 (b)十字链表建立算法
    (4)邻接多重表
    7.3 图的遍历
    (1)深度优先搜索及其算法
    (2)广度优先搜索及其算法
    7.4 图的连通性问题
    (1)无向图的连通分量和生成树
    (2)有向图的强连通分量
    (3)最小生成树定义及算法 (a)最小生成树概念 (b)Prim算法 (c)Kruskal算法
    7.5 有向无环图及应用
    (1)拓扑排序
    (2)AOV-网及关键路径
    7.6 最短路径
    (1)单源最短路径与Dijkstra算法
    (2)每对顶点之间的最短路径与Floyd算法

    本章学时数：10，本章习题数：10

    第八章 动态存储管理
    8.1 概述
    动态存储问题概述
    8.2 可利用空间表及分配方法
    (1)可利用空间表结构形式
    (2)三种分配策略 （a）首次拟合法 (b)最佳拟合法 (c)最差拟合法
    8.3 边界标识法
    (1)可利用空间表的结构 (2)分配算法 (3)回收算法
    8.4 伙伴系统
    (1)可利用空间表的结构 (2)分配算法 (3)回收算法
    8.5 无用单元收集
    (1)无用单元收集基本步骤 (2)三种标志算法 
    8.6 存储紧缩
    存储紧缩基本步骤
    本章学时数：4，本章习题数：5

    第九章 查找
    9.1 静态查找表
    (1)顺序表的查找
    (2)有序表的查找
    (3)静态树表的查找
    (4)索引顺序表的查找
    9.2 动态查找表
    (1)二叉排序树和平衡二叉树 
    (a)二叉排序树查找算法 (b) 二叉排序树插入和删除算法 (c) 二叉排序树查找分析 (d)平衡二叉树
    (2)B-树和B+树 (a) B-树的查找、插入和删除算法 (b)B+树的查找、插入和删除算法
    (3)键树 (a)双链树 (b)Trie树
    9.3 哈希表
    (1)哈希表定义及哈希函数的构造方法
    (2)处理冲突方法 (a)开放定址法 (b)再哈希法 (c)链地址法 (d)建公共溢出区法
    (3)哈希表的查找及其分析
    本章学时数：8，本章习题数：10

    第十章 内部排序
    10.1 概述
    排序基本概念
    10.2 插入排序
    (1) 直接插入排序
    (2) 折半插入排序、2-路插入排序和表插入排序
    (3)希尔排序
    10.3 快速排序
    (1)快速排序算法
    (2)快速排序算法性能
    10.4 选择排序
    (1)简单选择排序
    (2)树形选择排序
    (3)堆排序 (a)堆定义 （b）筛选算法 (c)堆排序算法 (d)时间复杂度分析
    10.5 归并排序
    归并排序算法及性能
    10.6 基数排序
    (1)多关键字排序 (a)MSD法 (b)LSD法
    (2)链式基数排序
    10.7 各种内部排序方法的比较讨论(课堂讨论)
    本章学时数：10，本章习题数：12

    第十一章 外部排序
    11.1 外存信息的存取(简讲)
    (1)磁带信息的存取 (2)磁盘信息的存取

    11.2 外部排序的方法
    (1)外部排序的归并过程 (2)外部排序所需时间
    11.3 多路平衡归并的实现
    (1)败者树概念 (2)k-路归并算法描述
    11.4 置换-选择排序
    (1)置换-选择排序排序过程 (2)置换-选择排序算法描述
    11.5 缓冲区的并行操作处理（简讲）
    11.6 最佳归并树
    (1)最佳归并树概念 (2)附加虚段数目的判定
    11.7 磁带归并排序
    （1）平衡归并 （2）多步归并
    本章学时数：4，本章习题数：4

    第十二章 文件
    12.1 有关文件的基本概念
    (1)文件及其类别 (2)记录的逻辑结构和物理结构 (3)文件的操作 (4)文件的物理结构
    12.2 顺序文件
    (1)顺序文件概念及特点 (2)批处理算法
    12.3 索引文件概念
    (1)静态索引 (2)动态索引
    12.4 ISAM文件和VSAM文件
    (1)ISAM文件 (2)VSAM文件
    12.5 直接存取文件（散列文件）
    直接存取文件组织方法
    12.6 多关键字文件
    (1)多重表文件 (2)倒排文件
    本章学时数：2，本章习题数：3

    三、 先修课程
    离散数学，PASCAL语言(或C语言)

    四、 教材及主要参考书
    1、 严蔚敏等，数据结构（第二版），清华大学出版社
    2、 管纪文等，数据结构，高等教育出版社
    3、 朱望规，数据结构，西安交大出版社
    4、 E.Horowitz and Sahni，Foudamentals of Data Structures, by Pitmen Publishing Limited.
    5、 D.E.Knuth，The Art of Computer Programming，by Addison-Wesley Publishing Company,Inc.

    五、 实验
    实验1 线性表(4学时)
    要求：熟悉线性表的基本运算以及在两种存储结构上的实现
    实验2 栈、队列与递归算法设计（4学时）
    要求：进一步了解栈、队列的特点，完成较复杂的递归算法设计 
    实验3 串（4学时）
    要求：熟悉一般文字处理软件的设计方法
    实验4 树、图及其应用（4学时）
    要求：将树和图结构应用于解决实际问题
    实验5 文件、查找与排序（8学时）
    要求：设计一个实用系统，涉及文件的组织、查询和排序等操作