《数据结构》课程教学大纲

1、数据结构课程教学大纲一、课程基本信息课程名称：数据结构课程代码：CST202学 分：4（大学科基础课）学 时：3学时/课，共48学时。二、任课教师、助教、教室等情况（四）教 室：C501 实 验 室：D502（五）上课时间：每周二上午1，2，3节（六）纪 律：1、无特殊情况，不允许无故缺课。2、每次作业须在规定时间内提交。三、阅读材料（一）推荐教材：数据结构，严蔚敏等著，清华大学出版社。2015年数据结构，刘小晶著，清华大学出版社。2015年（二）参考教材1. 熊伟编著，数据结构，机械工业出版社，2005年11月。2. 数据结构教材编写组，数据结构（第三版），清华大学出版社，2006年。3数据

2、结构与算法Sartaj Sahni（美）著 汪诗林 孙晓东等译 机械工业出版社。4DATA STRUCTURES WITH C+ 清华大学出版社。（三）进一步阅读教材1The Art of Computer Programming Volumes 1-3 Boxed Set ，Donald E.Knuth，清华大学出版社。2 Data structures A Pseudocode Approach with C+ 英文版 美Richard F.Gilberg Behrouz A.Forouzan 著 ，人民邮电出版社。3中国知网()相关文献四、课程内容概要（一）课程目标本课程的教学目的是使学

3、生学会在非数值计算数学模型下分析计算机加工数据的理论和方法，掌握各种数据结构（线性表、堆栈与队列、树、图）的特性，为应用所涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并且灵活地进行各种数据结构的基本操作，同时初步掌握对算法的时间分析和空间效率分析。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力、良好的程序设计能力，为编译原理、算法分析与设计、操作系统等后续课程的学习及以后从事软件开发工作打下良好的基础。（二）教学内容(分章节)主 要 教 学 内 容第一章 概 论（3学时）第一节 基本概念和术语第二节学习数据结构的意义第三节抽象数据类型第四节算法的描述和分析第

4、二章 线性表（6学时）第一节 线性表的逻辑结构第二节 线性表的顺序存贮结构第三节 线性表的链式存贮结构第四节 顺序表和链表的比较第三章 栈和队列（6学时）第一节 栈第二节队列第三节栈与队列的应用实例第四章 串（3学时）第一节 串及其运算第二节串的存贮结构第三节串的模式匹配(分章节)主 要 教 学 内 容第五章 树（6学时）第一节 树的概念第二节 二叉树第三节二叉树的遍历第四节线索二叉树第五节树和森林、哈夫曼树及其应用第六节树与等价问题、树的计数第六章 图（9学时）第一节 图的概念第二节 图的存贮结构第三节 图的遍历第四节 图的连通性问题第五节 最短路径第六节 有向无环图及其应用第七章 动态存储

5、管理（3学时）第一节 概述第二节可利用空间表及分配算法第三节边界标识法第四节伙伴系统第五节无用单元收集第八章 查找（3学时）第一节 基本概念第二节 静态查找第三节 动态查找第四节 散列查找第九章 文件简介（3学时）第一节文件基本概念第二节顺序文件与索引文件第三节 ISAM和VSAM文件第三节散列文件第十章 排序（3学时）第一节 概述第二节 插入排序第三节 快速排序第四节 堆排序第五节 归并排序第六节 基数排序第七节 各种排序方法的综合比较第八节 外部排序（三）课程要求1.文献与参考书阅读作业：课堂进行随机抽查回答与提前指定汇报结合方式。2.平时课后作业：按时规定的时间交与助教进行批改，隔一周上

6、课时间助教与授课教师进行评讲。3.上机作业：上机实验作业按照“学号-姓名-实验*”方式命名，课后及时在课程中心作业论坛中进行提交。4.课程设计：课程设计第12个教学周开始，以小组方式进行，每组由5-6名学生组成，设计报告以小组名义提交。要求运用本课程所学理论与方法，分析解决现实中企业组织面临的管理决策或优化问题，第16周课堂进行答辩，课程设计内容要求详见课程设计指导书。（四）教学安排周数教学时数及内容备注课堂讲授课堂讨论实验实习或上机作业章节内容课时题目课时内容及要求复习程序设计知识（C）1.数据类型及运算符,表达式2.算法及其描述3.程序设计基础4.数组,函数5.指针及结构6.链表及其应用3

7、根据实际情况增加课时11.1 数据结构讨论的范畴1.2 基本概念1.3 算法和算法的量度322.1 线性表的类型定义2.2 线性表类型的实现顺序映象2.3 线性表类型的实现链式映象332.4 一元多项式的表示3.1 栈的类型定义3.2 栈的应用举例3.3 栈类型的实现3C程序设计练习:指针和链表操作43.4 队列的类型定义3.5 队列类型的实现354.1 串的抽象数据类型的定义4.2 串的表示和实现31.复数运算 2约瑟夫环 3.迷宫求解64.3 串的模式匹配算法5.1 数组的类型定义5.2 数组的顺序表示和实现375.3 稀疏矩阵的压缩存储 5.4 广义表的类型定义5.5 广义表的表示方法5

8、.6 广义表操作的递归函数386.1 树的类型定义6.2 二叉树的类型定义6.3 二叉树的存储结构396.4 二叉树的遍历6.5 线索二叉树6.6 树和森林的表示方法31、矩阵运算2、求广义表深度3、求最小生成树106.7 树和森林的遍历6.8 哈夫曼树与哈夫曼编码3117.1 抽象数据类型图的定义7.2 图的存储表示3127.3 图的遍历7.4 最小生成树3137.5 重（双）连通图和关节点7.6 两点之间的最短路径问题7.7 拓扑排序7.8 关键路径31、哈希树2、最短路径导游149.1 静态查找表9.2 动态查找树表9.3 哈希表31510.1 概述10.2 插入排序10.3 快速排序31610.4 堆排序10.5 归并排序10.6 基数排序10.7 各种排序方法的综合比较10.8 外部排序31、平衡二叉树查找2、内部排序比较五、考核方式考试形式