还剩1页未读,继续阅读
文本内容:
数据结构算法设计课程教学大纲课程名称数据结构算法设计英文名称Algorithm Designof DataStructures课程编号x2050731学时数32其中实验(实训)学时数28课外学时数0学分数
2.0适用专业网络工程
一、课程的性质和任务本课程是网络工程专业的专业基础课程,它是《数据结构》课程的继续和延伸通过该课程的学习,在掌握数据结构中的基础算法的基础上,进一步掌握、理解一些经典算法和应用算法及其程序实现,了解算法设计的基本理论及算法效率评价,培养学生算法设计能力、程序设计能力和程序调试能力,为后续课程的学习打下坚实的基础
二、课程教学内容的基本要求、重点和难点
(一)线性表的操作
1、掌握顺序表的操作
(1)基本操作插入、删除、查找、逆置、构造、析构、遍历;
(2)典型算法有序表的插入、合并;
2、掌握单向链表的操作
(1)基本操作插入、删除、查找、逆置、遍历;
(2)典型算法有序表的插入、合并;正整数链表的分解两个奇数、偶数表;
3、掌握双向链表的插入、删除、对称判断等;
4、理解应用算法(拓展)构造一个循环表,实现约瑟夫问题,一元多项式相加等;重点实现基本内容中的经典算法及应用算法难点双向链表的操作及一元多项式相加
(二)栈和队列的操作
1、掌握顺序栈的基本操作;
2、掌握顺序队列的基本操作(循环队列)入队、出队、判断队满等;
3、掌握应用算法
(1)利用栈实现回文判断,括号匹配判断,表达式求值,迷宫求解(拓展)
(2)循环队列中利用count记录队中元素个数/设置标志位来区分队空/队满,实现基本操作重点应用算法中各个问题的程序实现难点迷宫求解及表达式求值
(三)二叉树的操作
1、以二叉链表为存储结构,实现二叉树的3种递归遍历算法;先序、中序非递归算法、层次遍历算法;
2、以此为基础实现简单应用算法求高度,求叶子个数,拷贝二叉树等;
3、设定一些权值,实现哈夫曼树的构造,计算哈夫曼编码*;重点二叉树的非递归遍历及哈夫曼编码难点哈夫曼编码
(四)图的操作
1、构造一个图的邻接表、计算各结点的度;以邻接表为存储结构实现深度、广度遍历算法
2、构造一个无向图的邻接表,实现算法判断任意两个顶点间是否有路径可达;
3、构造一个无向图的邻接表,计算连通分量的个数;
4、构造一个有向图的邻接表,实现拓扑排序算法,并运行;
5、根据无向带权图的邻接矩阵,分别按照prim算法、kruskal算法,构造最小生成树*重点判断顶点间是否有路径可达算法,计算连通分量个数算法,拓扑排序算法,prim算法难点拓扑排序,prim算法的程序实现
(五)查找及排序
1、构造一个二叉排序树,实现查找、插入、删除等操作
2、设定一下散列函数,利用拉链法处理冲突,构造一个散列表,实现查找操作
3、实现插入排序、快速排序、堆排序*、希尔排序算法,并比较它们的时间效率,其中快速排序利用栈实现非递归算法重点快速排序的非递归算法的程序实现及各个算法时间效率的比较难点快速排序非递归算法及时间效率的比较
三、教学方式及学时分配序号主要内容主要教学方式学时分配辅导答疑比例布置任务,讲解算法表达式求值,1迷宫求解,哈夫曼编码算法,快速排讲授421序的非递归算法等2线性表的应用算法实验4213栈和队列的应用算法实验8214二叉树的应用算法实验4215图的应用算法实验4216排序和查找实验4217实验考核考核4
四、课程其他教学环节要求(-)实验环节
1、线性表的操作(4学时)
2、栈和队列的操作(8学时)
3、二叉树的操作(4学时)
4、图的操作(4学时)
5、查找及排序(4学时)
6、实验考核(4学时)
(二)实验报告要求
(1)学生上实验之前按照要求查阅相关资料,准备实验题目,实验中独立完成教师布置的任务,编写程序,实验结束时含有提交实验报告电子版(实验内容、实验要求、程序源代码、运行结果截图及实验总结)
(2)实验考核平时实验过程中随时考核,最后一次进行实验综合测试及答辩
(三)考核方式考勤10%,实验报告质量40%,实验测试50%
五、本课程与其他课程的联系本课程的先修课程是C++程序设计和数据结构等,后续课程是ASP.net程序设计等
六、教学参考书目
1、《数据结构》(C++版)第二版王红梅等主编清华大学出版社
2011.
72、《数据结构》(C++版)学习辅导与实验指导王红梅等清华大学出版社
2005.
73、《数据结构》(C语言版)严蔚敏等主编清华大学出版社
2007.
74、《数据结构》(C++语言描述)William Ford等编著清华大学出版社
1999.1。