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

GDOU-B-11-213《 数据结构 》课程教学大纲 GDOU-B-11-213 课程编号 1620067 学分 3 总学时 56 理论 46 实验/上机 10 英文课程名 DATA STRUCTURES 开课院（系） 软件学院 开课系 软件技术系 修订时间 2005年 6月 5日 课 程 简 介 课程简介: 数据结构基本概念、栈、队列、数组表示和存储、广义表的定义和存储、树的定义和数的存储结构、二叉数的定义和存储、二叉数的遍历、赫夫曼数及其应用、图的定义和存储、图的遍历及其应用、数据查找、哈希表、内部排序。 课 程 大 纲 一、课程的性质与任务：数据结构是计算机学科的核心课程，是本专业的基础课。培养学生数据抽象能力。 二、课程的目的与基本要求：要求学生学会分析计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析技术。 三、面向专业：软件工程及相关专业。 四、先修课程: C语言程序设计 五、本课程与其它课程的联系：学习数据结构要先修C语言程序设计，数据结构这门课程也是学习计算机操作系统、软件工程、软件设计等专业课程的基础。 六、教学内容安排、要求、学时分配及作业： 第1章：绪论(2学时)（作业1次） 1.1什么是数据结构(B) 1.2基本概念和术语(B) 1.3抽象数据类型的表示与实现(B) 1.4算法和算法分析(B) 第2章:线性表(6学时) （作业1次） 2.1线性表的类型定义(B) (2学时) 2.2线性表的顺序表示和实现(A) 2.3线性表的链式表示和实现(A) (2学时) 2.4一元多项式的表示及相加(B) (2学时) 第3章:栈和队列(4学时) （作业1次） 3.1栈(2学时) 栈的定义(A)、栈的表示和实现（A） 3.2栈的应用举例(B) 3.4队列(2学时) 队列的定义(A)、队列的表示和实现（A） 第4章:串(2学时) 4.1串的定义(C) 4.2串的表示和实现(C) 第5章:数组和广义表(2学时) （作业1次） 5.1数组的定义(B) 5.2数组的顺序表示和实现(A) 5.3矩阵的压缩存储(B) 5.4广义表的定义(C) 5.5广义表的存储结构(C) 第6章:树和二叉树(6学时) （作业1次） 6.1树的定义和基本术语(A) (2学时) 6.2二叉树(A) 6.3遍历二叉树和线索二叉树(2学时) 遍历二叉树(A) 6.4树和森林(2学时) 树的存储结构(A)、森林与二叉树的转换（B）、树和森林的遍历（C） 6.6赫夫曼树及其应用(A) 第7章:图(10学时) （作业1次） 7.1图的定义和术语(A) (2学时) 7.2图的存储结构(A) 7.3图的遍历(A) (2学时) 7.4图的连通性问题(2学时) 无向图的连通分量和生成树(B)、最小生成树（A） 7.5有向无环图及其应用(B) (2学时) 7.6最短路径(B) (2学时) 第9章:查找(4学时) （作业1次） 9.1静态查找表(2学时) 顺序表的查找（A）、有序表的查找（A）、索引顺序表的查找（B） 9.2动态查找表 二叉排序树和平衡二叉树(B) 9.3哈希表(A) (2学时) 第10章:内部排序(8学时) （作业1次） 10.2插入排序(2学时) 直接插入排序(A)、其他插入排序（B）、希尔排序（C） 10.3快速排序(A) (2学时) 10.4选择排序 简单选择排序(A)、树形选择排序（C）、堆排序（B） 10.5归并排序(A) (2学时) 10.6基数排序 多关键字的排序(B) 10.7各种内部排序方法的比较(B) (2学时) 机动：(2学时) 七、实验名称与类别: 序号 实验名称 学时 实验类别 1 一元多项式相加程序 2 设计型 2 行编辑程序 2 设计型 3 图的遍历程序 2 设计型 4 关键路径程序 4 综合型 5 注:实验类别指:演示型、操作型、验证型、综合型、设计型、研究创新型 八、实验目的、内容与要求 实验1 实验目的：熟悉和掌握线性表及其应用 实验内容：编制一元多项式相加程序，上机调试、运行并分析结果。 实验要求：上机前理解书算法2.22,根据此算法编制一元多项式相加程序。 实验2 实验目的：熟悉和掌握栈结构及其应用 实验内容：编制行编辑程序，上机调试、运行并分析结果。 实验要求：上机前理解书算法3.2,根据此算法编制行编辑程序。 实验3 实验目的：熟悉和掌握图型结构及其应用 实验内容：编制图的遍历（深度和广度）程序，上机调试、运行并分析结果。 实验要求：上机前理解书算法7.4,7.5和7.6,根据此算法编制图的遍历程序。 实验4 实验目的：了解