《数据结构》教学大纲new

《《数据结构》教学大纲new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》教学大纲l教学课时：72l适用对象：计算机应用专业l先修课程：C语言程序设计、VisualBasic程序设计一、课程性质、目的课程性质：数据结构是计算机应用专业的主干课程之一，属于专业课。本课程是学习提高程序设计、学习数据库技术、进行应用系统开发的基础。课程目的：通过学习使学生了解客观数据及其联系，在计算机内部物理表示的特性及其存储结构，了解数据的逻辑结构与物理实现的区别；理解数据类型的概念；掌握线性表、栈与队列、树、二叉树、图等典型的数据结构，掌握典型内部排序算法和查找算法；通过对各种数据结构和算法的学习，能够为具体的问题

2、选择适当的逻辑结构、存储结构及其相应的算法；为学习操作系统、数据库等后序课程打好基础。本课程是学习《计算机操作系统》、《数据库系统术》、以及今后进行软件开发工作的必修课。本课程共需72课时，其中54课时讲授，18课时上机，为实现。上机所用计算机语言为C语言。二、教学基本内容教学基本要求1.知识要求了解：数据结构、数据类型、抽象数据类型概念；算法和算法分析概念；树的定义、表示；分类、查找的基本概念；内部排序算法的效率分析。掌握：线性数据结构线性表、栈、队列、串的抽象类型描述方法和物理实现算法；二叉树的性质与存储，二叉树的遍历，树与二叉树的

3、转换；最优二叉树；图的存储与遍历，拓扑排序；内部排序的算法与实现；折半查找与动态查找；Hash表；2.能力要求：简单应用：运用线性表结构解决实际问题，如高次多项式的存储，集合类型的实现；应用栈结构，如编制递归算法，解决汉诺塔问题；简单表达式的求解；拓扑排序。熟练应用：应用数据结构知识描述实际问题。第1章绪论1.1数据结构分析示例1.2数据结构的基本概念1.2.1什么是数据结构(了解)1.2.2数据结构的图形表示1.2.3线性数据结构与非线性数据结构1.3算法分析的考虑1.3.1什么是算法1.3.2算法的复杂性1.3.3算法描述性语言第2

4、章线性表及其顺序存储结构2.1线性表的定义（掌握）2.2栈及其应用2.3队列及其应用2.4字符串基本操作第3章线性链表3.1线性链表的基本概念3.1.1线性表的顺序存储问题3.1.2线性链表3.1.3带链的栈3.1.4带链的队列3.2线性链表的基本操作3.2.1在线性链表中查找指定的元素3.2.2线性链表的插入3.3.3线性链表的删除3.3循环链表3.4多项式的表示与运算第4章数组4.1数组的定义与数组的顺序存储结构4.2规则矩阵的压缩4.3一般稀疏矩阵的表示4.3.1稀疏矩阵的三列二维数组表示4.3.2十字链表第5章树和二叉树5.1树

5、的基本概念（掌握）5.2二叉树及其基本性质（掌握）5.2.1什么是二叉树（掌握）5.2.1二叉树的基本性质（掌握）5.2.3满二叉树与完全二叉树5.3二叉树的基本性质存储结构5.3.1二叉树链表（了解）5.3.2二叉树的生成5.4二叉树的遍历（掌握）5.5穿线二叉树5.6表达式的线性化5.7最优二叉树及其应用5.7.1什么是最优二叉树5.7.2最优二叉树的构造5.7.3赫夫曼树及其应用（简单应用）第6章图6.1图的定义（掌握）6.2图的存储结构（掌握）6.3图的遍历6.3.1深度优先搜索（掌握）6.3.2广度优先搜索（掌握）6.4最短距

6、离问题第7章查找技术7.1顺序查找（掌握）7.2折半查找（掌握）7.3分块查找7.4二叉树排序查找7.5多层索引树查找第8章Hash表技术8.1Hash（哈希）表的基本概念什么是Hash表哈希函数的构造方法处理冲突的方法8.2常用的几种哈希表（掌握）第9章排序技术9.1交换类排序9.1.1冒泡排序（掌握）9.1.2快速排序9.2插入排序（掌握）简单插入排序希尔排序9.3选择类排序9.4拓扑分类9.5其他排序方法简介归并排序（了解）基数排序三.实践环节序号相关理论内容实践内容实践方式学时基本教学要求1栈结构应用栈对表达式处理，用C语言编程

7、实现简单表达式的求值处理。上机2掌握栈结构的物理实现，应用栈解决实际问题。2队列与栈利用队列将递归的快速排序算法改为非递归上机2简单应用线性表知识，解决实际问题。3单链表链表的生成、插入、删除和排序上机2掌握链表的常用操作4二叉树采用二叉链表结构建立二叉树、实现二叉树的遍历上机2掌握二叉树的存储与遍历算法5图的存储求最短路径与遍历上机2掌握有向图的生成与求最短路径和遍历6表、链表顺序查找、二分查找上机2使用多种技术进行查找，比较各种查找技术算法效率。7Hash技术用内存模拟Hash方法，找较好的Hash函数与解决冲突的方法上机2实践Ha

8、sh技术8排序简单选择排序、快速排序，并比较算法效率。上机2掌握选择排序、快速排序算法。9排序希尔排序、拓扑排序上机2掌握希尔排序、拓扑排序总计18四.学时分配章次内容学时分配理论学时实践学时第一章绪论20