据结构》教学大纲 - 南京大学.doc

《据结构》教学大纲 - 南京大学.doc》由会员分享，可在线阅读，更多相关《据结构》教学大纲 - 南京大学.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程教学大纲课程代码 课程类型 成教必修课 学 分 3 学分 学 时 51学时 适用专业 计算机科学与技术、网络工程、软件工程 一、教学目标和教学要求1教学目标：培养学生综合分析能力，以便能够合理有效地表示和处理数据，提高程序设计的质量。为今后其它的信息与数据处理专业课程打下良好的基础。2教学要求（1）学生能够掌握常用的数据结构抽象数据类型、各种基本存储方法以及主要的算法，例如（线性结构、二叉树、树、图等）。（2）学生能够掌握并应用常用的排序、检索技术。（3）培养学生分析问题和解决问题的能力，根据所求解问题的性质选择合理的数据结构；使学生能够掌握基本的算法设计和分析技术，并能对自己设计

2、的数据结构和算法进行简单的分析，并对时间空间复杂性进行必要的控制。二、课程内容、重点、难点和教学环节第一章 数据结构概论1、教学基本要求（1）理解数据结构的概念。（2）理解算法的定义及特性、算法的性能标准、算法分析、空间复杂度和时间复杂度的渐进表示法。2、教学内容（1）数据、数据对象、数据结构、逻辑结构、存储结构的概念。（2）抽象数据类型及面向对象概念（3）算法和算法分析。第二章 线性表1、教学基本要求（1）理解顺序表、链表、循环链表、双向链表的概念及基本操作。（2）了解链表的相关应用。2、教学内容（1）顺序表、链表、循环链表、双向链表的概念。（2）顺序表、链表、循环链表、双向链表的建立、插入

3、、删除操作第三章 栈和队列1、教学基本要求（1）理解栈、队列的概念及基本操作。2、教学内容（1）栈、队列的概念及操作。（2）算术表达式、应用后缀表示计算表达式的值、中缀表达式转换为后缀表达式。第四章 数组、串与广义表1、教学基本要求（1）理解多维数组、稀疏矩阵、字符串、广义表的概念及基本操作。（2）了解稀疏矩阵的转置算法与广义表的存储实现。2、教学内容（1）多维数组、稀疏矩阵、字符串、广义表的概念。（2）稀疏矩阵的转置算法、字符串的实现。（3）广义表的head和tail操作。第五章 树1、教学基本要求（1）理解树和森林的概念。（2）熟练掌握二叉树的存储表示。（3）掌握二叉树的遍历算法。2、教学

4、内容（1）树和森林的概念。（2）二叉树的概念及性质。（3）二叉树的前序（中序、后序）遍历算法。（4）二叉树的线索化建立算法，树（森林）与二叉树的转换。（5）堆的建立（Filterdown调整算法）、插入（FilterUp调整算法）、删除堆顶元素操作。第八章 图1、教学基本要求（1）理解图的基本概念。（2）了解图的存储表示。（3）理解图的遍历方法。（4）理解图的最小生成树方法。（5）了解图的最短路径方法。（6）了解活动网络的概念。2、教学内容（1）图的基本概念和术语。（2）图的两种存储表示。（3）图的深度优先和广度优先遍历方法。（4）图的Kruskal、Prim最小生成树算法。（5）图的最短路径

5、Dijkstra算法。第九章 排序 1、教学基本要求（1）了解排序的基本概念。（2）理解排序的稳定性概念、算法分析方法。（3）理解插入排序、交换排序、选择排序、归并排序。（4）了解排序算法的分析方法。2、教学内容（1）排序的概念和术语。（2）排序的稳定性和算法分析。（3）直接插入排序、 折半插入排序、Shell排序。（4）冒泡排序、快速排序。（5）直接选择、 锦标赛、堆排序。（6）2-路归并算法。（7）各种排序方法的比较。三、学时分配序号学 教 时 学 环 节内 容讲课（面授）自学（作业）实习实验小计第一章前言、基本概念及算法分析31004第二章顺序表的基本概念、主要操作（查找、插入、删除）、

6、链表的基本概念、主要操作（查找、插入、删除），双向链表、链表的应用922215第三章栈的基本概念和操作（POP、PUSH）、顺序栈、链式栈、应用后缀表示计算表达式的值、中缀表达式转换为后缀表达式，栈与递归，队列的基本概念和操作（出队、入队）、循环队列、链式队列、优先级队列、稀疏矩阵的正交链表表示622212第四章数组的基本概念和操作、串的的基本概念和操作、广义表的基本概念和存储实现622212第五章树的基本概念、二叉树的定义及性质、二叉树的表示、二叉树的遍历、线索化二叉树的基本概念、树的表示、树（森林）与二叉树的转换、树的遍历。1233321第八章图的基本概念和存储表示、图的遍历（深度优先、广

7、度优先）、最小生成树（Kruscal和Prim算法）、最短路径（Dijstra算法）。622212第九章排序的基本概念、插入排序（直接插入排序、折半插入排序、shell排序）、交换排序（冒泡排序、快速排序）、布置课堂讨论内容（有关排序的问题，同学们课后准备）、选择排序、归并排序、简单介绍基数排序、安排学生讨论排序算法922417总计51181720106四、主要教材及参考书主要教材：殷人昆，数据结构用面向对象方法与C+描述（第二版），清华大学出版社，2007参考书目：1 许卓群、杨冬青、唐世渭、张铭，数据结构与算法，高等教育出版社，2004年7 月2 张铭、赵海燕、王腾蛟，数据结构与算法学习指导与习题解析，高等教育出版社，2005 年9 月3 张铭、刘晓丹译, 数据结构与算法分析C+第二版，电子工业出版社，2002 年6 月