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

《据结构》教学大纲-南京大学》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、结构；使学生能够掌握基本的算法设计和分析技术，并能对自己设计的数据结构和算法进行简单的分析，并对时间空间复杂性进行必要的控制。二、课程内容、重点、难点和教学环节第一章数据结构概论1、教学基本要求(1)理解数据结构的概念。(2)理解算法的定义及特性、算法的性能标准、算法分析、空间复杂度和时间复杂度的渐进表示法。2、教学内容(1)数据、数据对象、数据结构、逻辑结构、存储结构的概念。(2)抽象数据类型及面向对象概念(3)算法和算法分析。第二章线性表1、教学基本要求(1)理解顺序表、链表、循环链表、双向链表的

3、概念及基本操作。(2)了解链表的相关应用。2、教学内容(1)顺序表、链表、循环链表、双向链表的概念。(2)顺序表、链表、循环链表、双向链表的建立、插入、删除操作第三章栈和队列1、教学基本要求(1)理解栈、队列的概念及基本操作。2、教学内容(1)栈、队列的概念及操作。(2)算术表达式、应用后缀表示计算表达式的值、中缀表达式转换为后缀表达式。第四章数组、串与广义表1、教学基本要求(1)理解多维数组、稀疏矩阵、字符串、广义表的概念及基本操作。(2)了解稀疏矩阵的转置算法与广义表的存储实现。2、教学内容(1)

4、多维数组、稀疏矩阵、字符串、广义表的概念。(2)稀疏矩阵的转置算法、字符串的实现。(3)广义表的head和tail操作。第五章树1、教学基本要求(1)理解树和森林的概念。(2)熟练掌握二叉树的存储表示。(3)掌握二叉树的遍历算法。2、教学内容(1)树和森林的概念。(2)二叉树的概念及性质。(3)二叉树的前序(中序、后序)遍历算法。(4)二叉树的线索化建立算法，树(森林)与二叉树的转换。(5)堆的建立(F订terdown调整算法)、插入(F订terUp调整算法)、删除堆顶元素操作。第八章图1、教学基本要

5、求(1)理解图的基本概念。(2)了解图的存储表示。(3)理解图的遍历方法。(4)理解图的最小生成树方法。(5)了解图的最短路径方法。(6)了解活动网络的概念。2、教学内容(1)图的基本概念和术语。(2)图的两种存储表示。(1)图的深度优先和广度优先遍历方法。(4)图的KruskakPrim最小生成树算法。(5)图的最短路径Dijkstra算法。第九章排序1、教学基本要求(1)了解排序的基本概念。(2)理解排序的稳定性概念、算法分析方法。(3)理解插入排序、交换排序、选择排序、归并排序。(4)了解排序算

6、法的分析方法。2、教学内容(1)排序的概念和术语。(2)排序的稳定性和算法分析。(3)直接插入排序、折半插入排序、Shell排序。(2)冒泡排序、快速排序。(3)直接选择、锦标赛、堆排序。(6)2■路归并算法。(7)各种排序方法的比较。三、学时分配序号学教时学内容讲课(面授)自学(作业)实习实验小计第一章前言、基本概念及算法分析31004笫二章顺序表的基本概念、主要操作(查找、插入、删除)、链表的基本概念、主要操作(查找、插入、删除)，双向链表、链表的应用922215第三章栈的基本概念和操作(PO

7、P、PUSH)、顺序栈、链式栈、应用后缀表示计算表达式的值、中缀表达式转换为后缀表达式，栈与递归，队622212列的基本概念和操作（出队、入队）、循环队列、链式队列、优先级队列、稀疏矩阵的正交链表表示第四章数组的基本概念和操作、串的的基本概念和操作、广义表的基本概念和存储实现622212第五章树的基本概念、二叉树的定义及性质、二叉树的表示、二叉树的遍历、线索化二叉树的基本概念、树的表示、树（森林）与二叉树的转换、魁的-'J历1233321第八章图的基本概念和存储表示、图的遍历（深度优先、广度优先）、最

8、小生成树（Kruscal和Prim算法）、最短路径（Dijstra算法）。622212笫九章排序的基本概念、插入排序（直接插入排序、折半插入排序.shell排序）、交换排序（冒泡排序、快速排序）、布置课堂讨论内容（有关排序的问题，同学们课后准备）、选择排序、归并排序、简单介绍基数排序、安排学生讨论排序算法922417总计51181720106四、主要教材及参考书主要教材：殷人昆，《数据结构——用面向对象方法与C++描述》（第二版），清华大学出版社，200