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

《数据结构》课程教学大纲 ? 二、课程的基本要求 本课程的教学基本要求如下： 三、教学内容 4 3 栈和队列 理论教学 1．栈和队列的概念及运算； 2．栈和队列的顺序、链接存储 3．栈和队列的插入、删除算法及其应用 熟练掌握栈和队列的特征、基本运算并能设计简单算法 4 4 串 理论教学 1．串及其运算、串的存储结构； 熟练掌握串的逻辑结构、存储结构 2 5 树 理论教学 树的定义和表示； 二叉树的定义、重要性质、存储结构和运算； 二叉树的遍历、线索、排序； 二叉树与树和森林的转换； 树的应用： 二叉排序树、哈夫曼树及其应用 熟练掌握： 1.树形结构的基本概念和术语； ２.二叉树定义和存储结构； ３.二叉树的遍历次序及算法 6 6 图 理论教学 图的定义和术语 图的存储结构 图的建立和遍历 图的生成树 最短路径 图的遍历、图的生成算法 熟练掌握图的存储结构和遍历算法，以及生成最小生成树的方法 6 7 查找 理论教学 1．查找的基本概念 2．顺序查找、 3．索引查找 4．树表查找(二叉排序树定义及查找，二叉平衡树的定义) 5．散列查找 熟练掌握顺序查找、二分查找、分块查找、二叉排序树查找的基本思想和算法；散列法基本思想、散列函数的常用构造方法及解决冲突方法 6 8 排序 理论教学 1．排序的基本概念 2．插入排序（直接插入排序、折半插入排序、希尔排序） 3．交换排序（冒泡排序、快速排序） 4.选择排序（简单选择排序、*堆排序） 5．各种排序方法比较 熟悉各种内部排序方法的基本思想和特点；各种排序方法的优缺点、时、空性能和适用场合 6 学 时 合 计72 理论教学 36 实践教学 36 （二）实践环节 for(i=1; i=n; i++) for(j =1; j =i ; j++) x=x+1; 掌握分析算法段的语句频度及时间复杂度，并用程序加以验证 2 2 线性表 实践项目 设计一个通信录信息管理程序, 程序要求用结构体定义记录，用单链表存放数据，并具有如下功能： 打开文件（读入文件中记录到链表）；添加、插入、删除、查找一个记录；显示所有记录；存盘（保存链表中记录到文件）和退出。 利用单链表的各种运算的算法来解决实际问题；要求学生自己查阅C语言书本，调试完善实践项目。 4 3 栈和队列 实践项目 1、栈和队列的顺序存储结构的所有操作算法的实现； 2、栈和队列的链式存储结构的所有操作算法的实现； 掌握栈和队列的实际应用 4 4 串 实践项目 串中字符及子串的查找和匹配 掌握串的实际应用 2 5 树 实践项目 用模块化的方法设计一个程序进行二叉树的建立和遍历。 主菜单中包括如下功能选项： 1.建立二叉树 2.先序非递归遍历 3.先序递归遍历 4.中序递归遍历 5.后序递归遍历，求叶节点数 6.退出 主要掌握二叉树的几种遍历的递归算法，先序的非递归遍历算法 6 6 图 实践项目 用模块化的方法设计一个程序建立无向图的邻接表并遍历该图。主菜单中包括如下功能选项： 1 建立无向图的邻接表 2 按深度优先遍历 3按广度优先遍历 4 退出 掌握图的生成和遍历算法 6 7 查找 实践项目 用模块化的方法编一程序测试顺序查找、折半查找、杂凑查找三种算法。其功能菜单如下： 1 顺序查找 2 折半查找 3 杂凑查找 0 退出 写出顺序查找、折半查找（二分查找）的算法并调试通过 6 8 排序 实践项目 用模块化的方法编一程序测试几种排序算法的运行时间。其功能菜单如下： 1选择排序 2 冒泡排序 3 希尔排序 4 快速排序 0 退出 写出几种插入排序算法、交换排序算法和简单选择排序算法并调试 6 学 时 合 计72 理论教学 36 实践教学 36 四、课时分配 《》课程共学分，课内学时，其中理论课学时，上机学时。