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

1、数据结构课程教学大纲课程名称数据结构/Data Structure课程编码10030500110 课程类型专业必修课课程性质专业主干课适用范围信息安全专业学分数4先修课程程序设计语言学时数72 实验/实践学时无课外学时无考核方式考试 一、教学大纲说明（一）课程的地位、作用和任务数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已成为其他理工科专业的热门选修课。本课程的主要目的是培养学生的数据抽象能力，其任务是通过若干数据结构应用实例，引导学生掌握数据类型的使用，为学生今后学习、开发与应用作些铺垫。 （二）课程教学的目的和要求本课程的主要目的是培养学生的数据抽象能力，

2、对学生要求如下：掌握算法的时间分析和空间分析技术，学会分析研究计算机加工的数据结构 的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法；理解各种数据结构的基本概念和术语，如线性结构、树型结构、图型结构等；了解数组和广义表，动态存储管理，外部排序以及文件的有关内容。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写程序时始终坚持结构化程序设计的思想，可读性强，符合软件工程的规范。数据结构作为信息安全等专业的专业必修课，要求学生能够做到为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法。（三）课程教学方法和手段本课程80%为教学部分，20%为学生自学部分

3、（教材中打*号部分）。教学部分又分为课堂讲授及练习两部分。课堂讲授以多媒体教学为主，练习则由教师布置若干任务，通过习题课或学生独立完成，。（四）课程与其它课程的联系本课程要求学生具备一定的程序设计能力，因此学生至少应先修“计算机基础”及“程序设计语言”两门专业基础课程。通过对“数据结构”的学习，将为“数据库原理与应用”、“面向对象系统设计”、“算法设计与分析”等后续课程作必要的铺垫。（五）教材与参考书教材：严蔚敏、吴伟民著，数据结构（C语言版），清华大学出版社，2003年教学参考书：王 玲，数据结构实验教程，四川大学出版社 ，2003年 二、课程的教学内容、重点和难点第一章 绪论内容：“数据结

4、构”的基本概念和术语，算法的设计要求抽象数据类型的表示与实现，算法时间效率及空间效率的度量方法；重点：算法的设计要求抽象数据类型的表示与实现，算法时间效率及空间效率的度 量方法；难点：算法时间效率及空间效率的度量方法；第二章 线性表内容：线性表的类型定义，线性表的顺序表示和实现，线性表的线性链表、循环链表及双向链表的表示和实现及其应用（一元多项式相加），抽象数据类型的表示与实现；重点：线性表的线性链表、循环链表及双向链表的表示和实现及其应用（一元多项式相加），抽象数据类型的表示与实现；难点：线性表的线性链表、循环链表及双向链表的表示和实现及其应用（一元多项式相加）。第三章 栈和队列内容：栈和队

5、列的特性及其抽象数据类型表示，栈和队列的表示和实现，栈的应用（数制转换、括号匹配的检验、迷宫求解、表达式求解）；重点：栈和队列的表示和实现，栈的应用（数制转换、括号匹配的检验、迷宫求解、表达式求解）；难点：栈的应用（数制转换、括号匹配的检验、迷宫求解、表达式求解）；第四章 串内容：串的特点及其类型定义，串的定长顺序存储、堆分配存储表示方法，串的模式匹配算法，文本编辑方面的应用；重点：串的定长顺序存储、堆分配存储表示方法，串的模式匹配算法，文本编辑方面的应用；难点：串的模式匹配算法；第五章 数组与广义表内容：数组的定义和性质、数组的顺序表示与实现、规则矩阵与一般稀疏矩阵的压缩存贮、广义表的定义、

6、广义表的存储结构重点：数组的顺序表示与实现、规则矩阵与一般稀疏矩阵的压缩存贮、广义表的存储结构难点：规则矩阵与一般稀疏矩阵的压缩存贮、广义表的存储结构；第六章 树和二叉树内容：树和二叉树的定义和性质，二叉树的存储结构，二叉树的遍历算法及线索二叉树的方法，赫夫曼树及其应用，树和二叉树的转换方法，回朔法与树的遍历；重点：二叉树的遍历算法及线索二叉树的方法，赫夫曼树及其应用，树和二叉树的转换方法，回朔法与树的遍历；难点：二叉树的遍历算法及线索二叉树的方法，赫夫曼树及其应用；第七章 图内容：图的性质与特点，图的邻接距阵以及邻接表表示方法，图的遍历、最小生成树、关键路径以及最短路径；重点：图的邻接距阵以

7、及邻接表表示方法，图的遍历、最小生成树、关键路径以及最短路径；难点：图的遍历、求最小生成树、关键路径以及最短路径的算法；第九章 查找内容：顺序表查找、二叉排序树和平衡二叉树，哈希表，各种查找方法在时间上的定性或定量的分析和比较；重点：顺序表查找、二叉排序树和平衡二叉树，哈希表，各种查找方法在时间上的定性或定量的分析和比较；难点：二叉排序树和平衡二叉树，哈希表及各种查找方法在时间上的定性或定量的分析和比较；第十章 内部排序内容：插入排序、快速排序、选择排序以及归并排序、基数排序的实现方法，各种排序方法在时间上的定性或定量的分析和比较；重点：插入排序、快速排序、选择排序以及归并排序的实现方法，各种排序方法在时间上的定性或定量的分析和比较；难点：快速排序、选择排序以及归并排序的实现方法。 三、 学时分配教学内容各教学环节学时分配采用何种多媒体教学手段章节主要内容讲授实验讨论习题课外其它小计第一章基本概念和术语，算法分析200002CAI课件，电脑演示第二章线性表的表示与实现、多项式的表示与相加402006CAI课件，电脑演示第三章栈和对列的应用62008CAI课件，电脑演示第四章串的表示与应用402006CAI课件，电脑演示第五章数组与广义表44CAI课件，电脑演示第六章树和二叉树10020012CAI课件，电脑演