数据结构教学大纲44 20.doc

数据结构课程教学大纲课程名称 数据结构 (Data structure)课程编码 学时/学分 64/3.5适用专业（层次） 适用工学学科、管理学学科的本专科教学课程简介数据结构是计算机程序设计的重要理论技术基础，是计算机学科的核心课程，是一门专业基础课。数据结构课程主要包括：（1）数据结构的基本概念；（2）线性表栈队列字符串数组广义表树二叉树图查找表等基本数据结构的概念、操作及应用；（3）查找、排序的实现方法等重要内容。在学习数据结构课程之前，必须具备高等数学、离散数学、计算机基本操作技术和一门设计语言（C或C+）等知识，后续课程为相关专业课程。数据结构课程主要是为了培养学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技术。通过学习课程的过程，也是对学生进行复杂程序设计的训练过程，培养了数据抽象能力。教学重点和难点数据结构的教学重点和难点有：数据的存储结构、运算及算法的分析。课程内容教学安排和学时分配表章次教学内容总学时数讲授学时实验学时设计学时作业学时讨论学时实习学时教学条件教学要求1绪论221.1什么是数据结构C1.2基本概念和术语C1.3抽象数据类型的表示与实现D1.4算法和算法分析C1.4.1算法C1.4.2算法设计的要求C1.4.3算法效率的度量C1.4.4算法的存储空间需求C2线性表8442.1线性表的类型定义11C2.2线性表的顺序表示和实现312A2.3线性表的链式表示和实现312A2.3.1线性链表A2.3.2循环链表A2.3.3双向链表A2.4一元多项式的表示及相加11C3栈和队列844章次教学内容总学时数讲授学时实验学时设计学时作业学时讨论学时实习学时教学条件教学要求3.1栈312A3.1.1抽象数据类型栈的定义A3.1.2栈的表示和实现11A3.2栈的应用举例11B3.2.1数制转换B3.2.2括号匹配的检验B3.3栈与递归的实现C3.4队列312A3.4.1抽象数据类型队列的定义A3.4.2链队列队列的链式表示和实现A3.4.3循环队列队列的顺序表示和实现A3.5离散事件模拟C4串224.1串类型的定义11C4.2串的表示和实现11A4.2.1定长顺序存储表示A4.2.2堆分配存储表示C4.2.3串的块链存储表示C4.3串的模式匹配算法B4.4串操作应用举例C4.4.1文本编辑C5数组和广义表225.1数组的定义C5.2数组的顺序表示和实现A5.3矩阵的压缩存储B5.3.1特殊矩阵B5.3.2稀疏矩阵B5.4广义表的定义11C5.5广义表的存储结构11A5.6m元多项式的表示B5.7广义表的递归算法C6树和二叉树10826.1树的定义和基本术语11C6.2二叉树11A6.2.1二叉树的定义章次教学内容总学时数讲授学时实验学时设计学时作业学时讨论学时实习学时教学条件教学要求6.2.2二叉树的性质A6.2.3二叉树的存储结构A6.3遍历二叉树和线索二叉树112A6.3.1遍历二叉树A6.3.2线索二叉树A6.4树和森林12B6.4.1树的存储结构B6.4.2森林与二叉树的转换B6.4.3树和森林的遍历B6.5树与等价问题C6.6赫夫曼树及其应用21A6.6.1最优二叉树A6.6.2赫夫曼编码B6.7回溯法与树的遍历1C6.8树的计数1C7图887.1图的定义和术语11C7.2图的存储结构11A7.2.1数组表示法A7.2.2邻接表A7.2.3十字链表A7.2.4邻接多重表A7.3图的遍历11A7.3.1深度优先搜索A7.3.2广度优先搜索A7.4图的连通性问题12B7.4.1无向图的连通分量和生成树B7.4.2有向图的强连通分量B7.4.3最小生成树B7.5有向无环图及其应用12B7.5.1拓扑排序B7.5.2关键路径B7.6最短路径11C7.6.1从某个源点到其余各顶点的最短路径C7.6.2每一对顶点之间的最短路径C章次教学内容总学时数讲授学时实验学时设计学时作业学时讨论学时实习学时教学条件教学要求8查找10648.1静态查找表422C8.1.1顺序表的查找B8.1.2有序表的查找B8.1.3静态数表的查找D8.1.4索引顺序表的查找B8.2动态查找表422B8.2.1二叉排序树和平衡二叉树B8.2.2B-和B+树B8.2.3键树D8.3哈希表12B8.3.1什么是哈希表B8.3.2哈希函数的构造方法B8.3.3处理冲突的方法B8.3.4哈希表的查找及其分析B9内部排序8629.1概述0.50.5C9.2插入排序11A9.2.1直接插入排序A9.2.2其他插入排序A9.2.3希尔排序A9.3交换排序11A9.4选择排序1.51.5A9.4.1简单选择排序A9.4.2树形选择排序A9.4.3堆排序A9.5归并排序0.50.5B9.6基数排序0.50.5B9.6.1多关键字的排序B9.6.2链式基数的排序B9.7各种内部排序方法的比较讨论312A教学要求：重点（A）、掌握（B）、理解（C）、了解（D）考核方式及成绩评定考核方式：闭卷、机试。成绩评定：考核成绩70%、平时考核30%。平时考核由平时考勤(10%）、实习成绩(20%）构成。教材及参考书目教 材: 数据结构（C语言版） 严蔚敏 吴伟民编著 清华大学出版社 2003年参考书目：1、数据结构 刘振鹏 张晓莉 郝杰编著 中国铁道出版社 2003年2、数据结构 杨正宏编著 中