课程类型：专业基础课
总学时：90
考核对象：计算机科学与技术专业
执笔者：连雁平
编写日期： 2012年9月
一、课程性质与考试目的：
本课程是计算机科学与技术专业的一门专业基础课，该课程主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习与考核，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、数据库、为面向对象的程序设计等课程奠定基础。
二、考试内容及要求：
第一章 绪论
【本章重点】
数据的逻辑结构，数据在计算机内的存储结构，反映算法优劣的两个指标。
1、考试内容：
数据；数据结构（逻辑结构和物理结构）；数据类型；抽象数据类型；数据结构的发展简史及其在计算机科学中的地位；描述算法的方法和基本的算法分析方法。
2、考核要求：
（1）掌握数据和数据结构相关的基本术语
（2）熟练掌握算法的描述语言
（3）理解算法的评价方法
第二章 线性表
【本章重点】
线性表的顺序存储与链式存储优势及弱势。
1、考试内容：
线性表的逻辑结构；线性表的顺序存储结构及其在这种结构上各种操作的实现；线性表的链式存储结构（线性链表、循环链表）及其各种操作的实现；线性表的应用；一元多项式的表示及相加。
2、考核要求：
（1）掌握线性表的逻辑结构和两种存储结构的描述方法；
（2）熟练掌握线性表的两类存储结构（顺序表和链表）上的基本算法尤其是插入删除算法；
（3）了解基本算法的时间复杂度的计算方法；
（4）深刻理解指针与指针所指结点的关系。
第三章 栈和队列
【本章重点】
栈和队列的区别，栈和队列的“上溢”“下溢”概念及其判断条件。
1、考试内容：
栈的定义；栈的表示和实现；表达式求值；队列的定义；链队列和循环队列。
2、考核要求：
（1）掌握栈和队列这两种抽象数据类型的特点；
（2）熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法；
（3）熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的条件以及它们的描述方法；
（4）理解递归算法执行过程中栈的状态变化过程。
第四章 串
【本章重点】
串的逻辑结构、存储方式及其应用。
1、考试内容：
串的定义；串的三种存储表示；串匹配算法（简单模式匹配、KMP算法）
2、考核要求：
（1）熟悉串的定义；
（2）熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法；
（3）掌握串的堆存储结构以及在其上实现串操作的基本方法；
（4）理解串匹配的KMP算法，熟悉next函数的定义，学会手工计算给定模式串的next函数值和改进的next函数值。
第五章 数组和广义表
【本章重点】
特殊矩阵和稀疏矩阵存储方法及运算的实现；广义表的结构特点。
1、考试内容：
数组的类型定义和表示方式；特殊矩阵和稀疏矩阵的压缩存储方法和运算；广义表的定义和存储结构；
2、考核要求：
（1）掌握多维数组的逻辑特征及其存储方式，以二维数组为主；
（2）了解特殊矩阵及稀疏矩阵的压缩存储方法；
（3）掌握广义表的结构特点及其存储表示方法。
第六章 树和二叉树
【本章重点】
二叉树的概念、性质及存储表示，线索二叉树的实现，二叉树的遍历；树、森林的顺序存储和链式存储结构的实现，及其遍历的方法。
1、考试内容：
树的基本概念和术语；结构定义和基本操作；二叉树的定义与基本操作；二叉树的性质；二叉树的存储结构；遍历二叉树（利用遍历方法实现各种树型基本操作的方法）的递归及非递归算法；线索二叉树；树、森林与二叉树的转换；树的存储结构；哈夫曼树及哈夫曼编码。
2、考核要求：
（1）熟练掌握二叉树的结构性质，了解相应的证明方法；
（2）熟悉二叉树的各种存储结构的特点及适用范围；
（3）熟练掌握二叉树的遍历及其上的一些应用；
（4） 熟练掌握二叉树的线索化过程；
（5） 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法；
（6）了解哈夫曼树的特性，掌握最优二叉树和哈夫曼编码的方法。
第七章 图
【本章重点】
图的存储结构，最小生成树、最短路径问题。
1、考试内容：
图的存储结构（邻接矩阵表示法、邻接表、十字链表、邻接多重表）及在各种结构上图的基本操作的实现；图的两种遍历方法（深度优先搜索和广度优先搜索）；连通分量；生成树、最小生成树及其在交通网络中的应用；有向图的应用（拓补排序、关键路径、最短路径）。
2、考核要求：
（1）熟练图的各种存储结构及其构造算法；
（2）熟练掌握图的两种搜索路径遍历的逻辑定义和算法；
（3）理解课本中讨论的各种图的算法。
第八章 查找
【本章重点】
威尼斯赌博游戏线性表的折半查找，威尼斯赌博游戏二叉查找树的构造，哈希表的概念、哈希函数和处理冲突的方法。
1、考试内容：
线性表的查找；有序表的查找；索引顺序表的查找；二叉排序树和平衡二叉树；B树；哈希表的构造方法及处理冲突的方法；哈希表的查找及其分析。
2、考核要求：
（1）了解查找和平均查找长度的概念；
（2）掌握线性表的三种基本查找方法及对表的要求；
（3）熟练掌握二叉排序树的构造方法及平均查找长度的计算；
（4）掌握二叉平衡树的维护平衡方法；
（5）理解B-树和B+树的特点以及它们的建树过程；
（6）了解散列表的概念，熟练掌握散列表的构造方法及冲突的处理方法。深刻理解散列表与其他结构的表的实质性的差别。
第九章 排序
【本章重点】
掌握各种排序算法的时间复杂度分析方法和结果。
1、考试内容：
直接插入排序；希尔排序；快速排序；选择排序；归并排序和基数排序各种排序的特点及时间复杂度的讨论比较。
2、考核要求：
（1）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；
（2）了解各种方法的排序过程和实现算法，能熟练写出各趟结果；
（3）掌握各种排序方法的时间复杂度的分析方法；
（4）理解排序方法“稳定”或“不稳定”的含义；
第十章 文件
【本章重点】
各类文件的构造方法及文件操作在其上的实现。
1、考试内容：
各类文件（顺序文件、索引顺序文件、直接存取文件、多重表文件和倒排文件）的构造方法及文件操作在其上的实现。
2、考核要求：
（1）熟悉各类文件的特点、构造方法；
（2）熟悉各类文件如何实现检索、插入和删除等操作；
三、考试方式及试题类型：
1、考试方法：笔试，闭卷；
2、考试时间：120分钟；
3、题目类型：
客观性试题包括选择题、填空题等。主观性试题包括应用题、程序题等。试题难度等级为：简单、中等难度、较难/难三种，比例大约为40：45：15。
四、教材及参考书：
教材：
[1] 严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社,2012.5.
参考书：
[2] 严蔚敏、吴伟民、米宁.《数据结构题集（C语言版）》.清华大学出版社，2011.11.
[3] 杨升，林芳等.《数据结构（C语言版）》.厦门大学出版社，2009.
[4] 宗大华，宗杰，黄芳.《数据结构》.人民邮电出版社，2010.11.
[5] 谭浩强.《C语言程序设计》.电子工业出版社，2005.