《数据结构》课程教学实施计划

《《数据结构》课程教学实施计划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》课程教学实施计划课程代码04812600课程名称数据结构DataStructuresandAlgorithms学时/学分64学时(48授课课时+16实验课时)/3+1学分先修知识高等程序设计、软件基础实验、高等数学、离散数学开课单位计算机与通信学院适用专业：计算机科学技术、信息安全、通信工程、智能科学与技术专业开课时间本科2年1期课程性质：必修使用教材数据结构(C语言版)严蔚敏著淸华大学岀版社2007一、课程教学目标“数据结构与算法”是计算机专业本科生的一门必修的专业基础课，通过本课程的学习，让学牛掌握线性表、栈、队列、二叉树

2、、树和图等常用的数据结构；掌握常用的排序、检索算法及其时间、空间代价；学会分析计算机处理的数据对象的特性，能够选择并设计合适的数据结构及相应的算法，初步寧握算法的时间和空间代价的分析方法。二、教学内容及基本要求(一)绪论(1)了解数据类型、抽象数据类型、数据结构的概念以及它们之间的关系(2)了解问题、算法、程序、算法的代价等概念(二)算法分析(1)了解渐近算法分析、算法代价的增长率等概念(2)了解算法的最佳情况、最差情况和平均情况(3)掌握上限、下限的概念以及人0、大Q和大©表示法(4)掌握渐进分析的化简法则(5)掌握简单程序运行时间的计

3、算方法(6)了解问题的代价与算法的代价的区别(7)了解多参数问题、空间代价、空间/时间权衡原则和实际操作屮的一些因素(三)递归学握递归算法的设计方法(四)线性表、栈和队列(1)了解线性表的基本概念和抽彖数据类型(2)掌握顺序衣的实现方法(3)掌握带表头结点的单-链表的实现方法(4)了解线性农的两种实现方法的优点和缺点(5)掌握带表头结点的双链表的实现方法(7)了解单循环链衣和双循环链衣的结构(8)了解栈的基木概念(9)掌握顺序栈的实现方法(10)拿握链式栈的实现方法(11)了解顺序栈与链式栈的比较(12)了解队列的基本概念(7)学握顺序队

4、列的实现方法(8)掌握链式队列的实现方法(9)了解顺序队列与链式队列的比较(一)二叉树(1)了解二叉树的定义与术语(2)学握满二叉树与完全二叉树的定义(3)掌握满二叉树定理及其推论(4)了解二叉树结点的抽彖数据类型(5)掌握前序、中序和后序周游二叉树的方法(6)掌握用指针实现二叉树的方法(7)了解二叉树实现的结构性开销的计算(8)拿握用数组实现完全二叉树的方法(9)掌握二义检索树的实现方法(10)学握实现堆以及利用堆实现优先队列的方法(11)掌握Huffman编码树的建立以及利用它进行编码/反编码的方法(二)树(1)了解树的定义与术语(2

5、)了解树结点的抽象数据类型及树的周游方法(3)掌握树的父指针表示法以及利用UNI0N/FIM)算法解决等价类问题的方法(4)了解树的子结点表表示法、动态利静态的左子结点/右兄弟结点表示法(5)了解K叉树和树的顺序表示法(三)图(1)了解图的术语和邻接矩阵、邻接表表示法(2)了解图的抽象数据类型(3)掌握图的邻接矩阵和邻接表实现方法(4)掌握图的两种周游算法：深度优先和广度优先算法(5)掌握图的两种拓扑排序算法(6)了解关键路径算法(7)掌握求单源最短路径的Dijkstra算法(8)掌握求每对顶点间最短路径的Floyd算法(9)掌握求最小支

6、撑树的Prim算法和Kruskal算法(四)内排序(1)掌握冒泡排序、选择排序和插入排序算法(2)了解Shell排序算法(3)拿握快速排序算法(4)掌握归并排序算法(5)学握堆排序算法(6)了解基数排序算法(7)了解各种排序算法的实验比较和排序问题的下限(五)查找(1)了解已排序数组的査找方法(2)了解白组织线性衣的查找方法(3)了解集合的查找方法(4)了解B树(5)掌握散列函数的设计方法(6)掌握两种冲突解决策略：开散列方法和闭散列方法三、考核方式课堂讲授+作业+实验+考试：课堂参与(10)+课后作业(10)+课程实验(20)+课程考试

7、(60)四、教学进度安排（含作业及实验安排）授课内容授课时间作业课程实验第一章绪论2作业1第一•章线性表8作业2实验1、2第三章堆栈和队列4作业3实验3第四章串2作业4实验4第五章数组和广义表2笫六章树和二叉树8作业5实验5第七章图6作业6实验6第八章内部排序8作业7实验7第九章查找8作业8实验8小计488次8个四、参考书1•数据结构与算法分析（C++版）（第二版）CliffordA.Shaffer著张铭刘晓丹等译电子工业出版社2002年2.数据抽象和问题求解一Java语言描述.FrankM.Carrano等著，韩志宏译.清华人学出版社2

8、005年4刀第1版.附录一：大作业设计并实现一个简单文本编辑器设计目标：1.该文本编辑器能不断接收和执行人通过键盘发出的命令，直至收到结束命令时终止运行。2.启动后给出提示信息，表示已经进入结