计算机与信息科学系教案

计算机与信息科学系教案教研室：计算机应用教研室 授课教师： 编号：1授课时间第 2周 第 1-2 次课授课题目第1章 绪论授课类型理论课( 是 )；实践课( ) 教学时数2学时教学目的及要求1、理解计算机信息处理中数据组织与运算处理的关系；2、熟悉各名词、术语的含义，掌握数据结构相关基本概念，特别是数据、数据元素、数据对象、数据结构、逻辑结构、存储结构等；3、了解数据的逻辑结构和存储结构之间的关系，了解常见的“集合、线性表、树、图”的逻辑结构形式和“顺序、链表、索引、散列”存储组织方法；4、了解抽象数据类型的定义、表示与实现方法。5、算法教学内容提要1、数据结构研究的主要内容与涉及的基本概念；2、数据类型与抽象数据类型。3、算法教学重点及难点1、 数据的逻辑结构、存储结构与运算方法之间的关系2、 算法时间复杂度的衡量教学手段讲授法、案例教学法作业、讨论、思考思考：1、抽象数据类型与数据类型的区别？2、时间复杂度的比较？课后小结 本章重点讲解了数据结构的相关概念、几种常见的数据结构，难点是抽象数据类型的定义以及算法时间复杂度的分析。参考资料1 严蔚敏等，数据结构题集,1995 2 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。6 数据结构教程 李春葆编著 清华大学出版社计算机与信息科学系教案教研室：计算机应用教研室 授课教师： 编号：2授课时间第 2 周 第 3-4次课授课题目第2章 线性表授课类型理论课( 是 )；实践课( ) 教学时数4学时教学目的及要求1、掌握线性表的逻辑表示2、掌握线性表的顺序表示和算法的实现3、掌握线性表的链式表示和算法实现 教学内容提要2.1 线性表的逻辑表示2.2 顺序表2.2.1顺序表的表示2.2.2顺序表的实现2.3 单链表2.3.1链表的表示2.3.2单链表的实现2.3.3 循环链表的表示与实现教学重点及难点重点：1、顺序表的表示2、链表的表示3、算法的实现难点：1、链表的表示与实现 教学手段讲授法、案例教学法作业、讨论、思考讨论：1、顺序表与链表的使用环境？ 2、顺序表与链表各自的优缺点？课后小结本章介绍了一种简单的数据结构线性结构的表示与实现，要求掌握的内容： 1. 线性表的逻辑表示 2.顺序表，利用高级语言实现顺序表的算法。3.链表的表示与实现 参考资料1严蔚敏等，数据结构（第二版）清华大学出版社,19932 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室 授课教师： 编号：3授课时间第 3 周 第5次课授课题目第2章 线性表授课类型理论课( 是 )；实践课( ) 教学时数4学时教学目的及要求1、掌握线性表的应用 教学内容提要1、 线性表的合并；2、 一元多项式的相加的实现教学重点及难点重点：1、线性表的应用 难点：1、一元多项式的链式实现 教学手段讲授法、案例教学法作业、讨论、思考1、一元多项式相加与有序表的合并有什么异同？课后小结 本节介绍了线性结构的应用实例有序表的合并和一元多项式的相加。参考资料1严蔚敏等，数据结构（第二版）清华大学出版社,19932 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室 授课教师： 编号：4授课时间第3 周 第6次课授课题目第4章 栈与队列授课类型理论课( 是 )；实践课( ) 教学时数2学时教学目的及要求1、栈2、栈的应用 教学内容提要 3.1 栈3.1.1 抽象数据类型栈的定义3.1.2 栈的表示和实现3.2 栈的应用举例3.2.1 数制转换3.2.2 括号匹配的检验3.2.3 行编辑程序3.2.4 迷宫求解3.2.5 表达式求值3.3 栈与递归的实现教学重点及难点重点：1、抽象数据类型栈的定义2、栈的表示和实现难点：1、抽象数据类型栈的定义 教学手段讲授法、案例教学法作业、讨论、思考1、顺序栈与链栈之间的区别？ 2、链栈的抽象数据类型的表示？ 3、链栈抽象数据类型的实现？ 课后小结本章主要介绍了线性表中的一个特例栈，它其实是操作受限制的线性表，即总在一端进行操作。它的特点是先进后出。在函数调用和操作系统中的应用非常的广泛。 参考资料1严蔚敏等，数据结构（第二版）清华大学出版社,19932 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室 授课教师： 编号：5授课时间第 4 周 第7-8次课授课题目第3章 栈与队列授课类型理论课( 是 )；实践课( ) 教学时数2学时教学目的及要求1、掌握队列的抽象数据类型的定义2、掌握队列的实现3、理解队列的特点4、掌握队列的应用 教学内容提要 3.4 队列3.4.1 抽象数据类型队列的定义3.4.2 链队列-队列的链式表示和实现3.4.3 循环队列-队列的顺序表示和实现3.5 离散事件模拟（选讲）教学重点及难点重点：1、 队列的抽象数据类型的表示2、队列的实现 难点：1、 队列的应用 教学手段讲授法、案例教学法作业讨论思考1、 链式队列是否受限制？2、 链式队列的实现与表示？课后小结1、 掌握队列与线性表之间的联系；2、 了解队列与栈之间的区别；3、 区分栈与队列在实现细节上的不同；4、 熟悉栈的特点是先进后出，队列的特点是先进先出； 参考资料1严蔚敏等，数据结构（第二版）清华大学出版社,19932 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室 授课教师： 编号：6授课时间第 5 周 第9-10次课授课题目第4章 串授课类型理论课( 是 )；实践课( ) 教学时数4学时教学目的及要求通过本章的学习，应使学生掌握串的各种基本操作以及串的实际应用。教学内容提要4.1 串类型的定义4.2 串的表示和实现4.2.1 定长顺序存储表示4.2.2 堆分配存储表示4.2.3 串的块链存储表示4.3串的模式匹配算法4.3.1 求子串位置的定位函数Index(S，T，pos)4.3.2 模式匹配的一种改进算法4.4 串操作应用举例（选讲）4.4.1 文本编辑4.4.2 建立词索引表 教学重点及难点重点： 1、串在定长顺序存储结构下的各种基本操作；2、理解有回溯的模式匹配和无回溯的模式匹配（KMP）算法数组的应用难点： 模式匹配算法教学手段讲授法、案例教学法作业、讨论、思考 1、讨论串的两种表示的不同？2、串的模式匹配与传统的匹配有那些方面的改进？课后小结本章介绍了串的表示与实现，以及串的应用模式匹配算法，该算法在图形图像处理方面应用非常的广泛。 本章主要的讲解内容如下：1 串的存储方式2 在不同的存储方式下的实现3 模式匹配算法参考资料1严蔚敏等，数据结构（第二版）清华大学出版社,19932 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室 授课教师： 编号：7授课时间第6-7 周 第1114次课授课题目第5章 数组与广义表授课类型理论课( 是 )；实践课( ) 教学时数7学时教学目的及要求1、 掌握数组的抽象数据类型的定义；2、熟练掌握稀疏距阵的表示与地址的计算；3、掌握 三元组的定义和使用；4、了解广义表的定义；5、掌握广义表的各种计算；6、了解广义表的各种存储方式；教学内容提要 5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.3.1 特殊矩阵5.3.2 稀疏矩阵5.4 广义表的定义5.5 广义表存储结构5.6 m元多项式的表示5.7 广义表的递归算法5.7.1 求广义表的深度5.7.2 复制广义表5.7.3 建立广义表的存储结构教学重点及难点重点：1、稀疏矩阵的定义与表示2、三元组的定义和应用3、 广义表各种计算难点：1、稀疏矩阵求地址2、三元组的应用3、 广义表的存储结构的表示教学手段讲授法、案例教学法作业、讨论、思考 思考：1、 稀疏矩阵中各种特殊矩阵的地址的计算？ 2、 用三元组实现一元多项式的相加？ 3、广义表中各种操作的实现？课后小结1、掌握对特殊矩阵的压缩存储以及三元组存储2、熟练运用特殊矩阵的基本操作3、了解广义表的概念、应用范围和基本操作参考资料1严蔚敏等，数据结构（第二版）清华大学出版社,19932 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室 授课教师： 编号：8授课时间第8-9 周 第1518次课授课题目第6章 树和二叉树 授课类型理论课( 是 )；实践课( ) 教学时数8学时教学目的及要求1、了解树的基本概念 ；2、理解二叉树的性质和存储结构；3、掌握遍历二叉树和线索二叉树；4、熟悉树的存储结构和遍历；5、了解集合的一种表示方法；6、掌握哈夫曼树及其应用 教学内容提要 1、树的定义和存储结构（1学时） 2、二叉树的定义、性质、存储结构（2学时） 3、二叉树的遍历、线索算法 （2学时） 4、树和二叉树的转换（1学时） 5、哈夫曼树及其应用 （2学时） 教学重点及难点重点：1、二叉树的概念、性质；2、二叉树的遍历方式；3、构造二叉排序树难点：1、二叉树的遍历方式；2、二叉排序树的构造方法；3、 二叉树的线索化。教学手段讲授法、案例教学法作业、讨论、思考。 完成课本中没有完成的有关二叉树的基本操作的实现。课后小结树及二叉树在实际应用中使用很广，通过本章的学习，学生要熟练掌握二叉树的性质、基本操作以及二叉树的各种应用。参考资料1严蔚敏等，数据结构（第二版）清华大学出版社,19932 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室 授课教师： 编号：9授课时间第 10-11 周 第19-21次课授课题目 第7章 图 授课类型理论课(是)；实践课( ) 教学时数2学时教学目的及要求1、 学习图的基本概念 ；2、 掌握图的存储结构；3、 理解图的遍历及应用最小生成树,最短路径等；4、 理解并掌握拓扑排序和关键路径等内容的学习，能解决生活中网络问题。教学内容1、图的定义 2、图的存储结构 3、图的遍历操作 （2学时） 4、图的几个典型应用问题（4学时 重点及难点重点：1、图的存储结构 、典型应用问题难点：图的典型应用问题教学手段讲授法、案例教学法作业、讨论、思考编程完成拓扑排序、最短路径和关键路径。课后小结本章介绍了一种重要的数据结构图，图的逻辑描述和物理描述都是比较复杂的，因此，在存储上也比较复杂，同时有4中不同类型的图的存在，丰富的类型，导致了图的广泛应用，尤其在网络描述上用的更多；几种常见的应用是需要同学们理解并掌握的：最小生成树、最短路径、拓扑排序和关键路径。 参考资料1严蔚敏等，数据结构（第二版）清华大学出版社,19932 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室 授课教师： 编号：10授课时间第 1112 周 第2124次课授课题目第9章 查找授课类型理论课( 是 )；实践课( ) 教学时数8学时教学目的及要求1、 掌握静态查找表(顺序表,有序表,索引顺序表)；2、 理解动态查找表(二叉排序树,平衡二叉树的建立和查找；3、 掌握哈希表的建立，查找及分析的查找性能 ，在应用中选择合适的查找方法。教学内容提要1、静态查找表及查找算法：顺序查找、折半查找（2学时）2、 动态查找表及查找算法：二叉排序树（2学时）3、 哈希表及查找算法（2学时）教学重点及难点重点：1、二叉排序树的构造方法；2、二叉平衡树的建立方法；3、哈希表的构造、应用；难点：1、二叉排序树的构造及应用；2、哈希表的构造方法；3、查找的性能分析教学手段讲授法、案例教学法作业、讨论、思考1、举例完成一个静态查找：要求用三种不同的查找方法实现，并指出用二分查找的注意事项；2、用一个实例完成二叉排序树，并将顺序打乱，看看相同的数据，不同的顺序构造的二叉排序树是否相同？并描述影响二叉排序树性能的因素；3、了解平衡二叉树的构造，当一棵树不是平衡二叉树时如何调整成一棵平衡二叉树；4、分析哈希表与其他存储方式的不同，并比较哈希查找与构造哈希表之间的联系。课后小结本章主要介绍了三种不同的查找方法：静态查找和动态查找以及哈希查找方法。其中静态查找有三种典型的算法：顺序查找适用于任何数据结构；二分查找只用于顺序存储的有序表的查找；索引查找。动态查找介绍了两种典型的查找算法二叉排序树和平衡二叉树。哈希表是一种特殊的查找方式，必须先找到一种构造查找表的函数即哈希函数，然后根据哈希函数得到关键字的存储位置，构造查找表，查找过程和构造表的过程相同，在构造哈希表的时候要注意冲突的处理。参考资料1严蔚敏等，数据结构（第二版）清华大学出版社,19932 William Ford，William Topp，Data Structure with C+ 清华大学出版社Prentice Hall联合出版,19963 李春葆等，数据结构与算法教程，清华大学出版社，20054 （美）Mark Allen Weiss著 冯舜玺译，数据结构与算法分析c语言描述，机械工业出版社，2004（6）5 郝文化，数据结构考研辅导教程，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室 授课教师： 编号：11授课时间第 1314 周 第2528次课授课题目第10章 内部排序授课类型理论课( 是 )；实践课( ) 教学时数8学时教学目的及要求掌握插入排序、交换排序(起泡排序,快速排序)、选择排序(简单选择,树形选择,堆)、归并排序、基数排序等算法。教学内容提要1、插入排序（2学时） 2、交换排序（2学时） 3、选择排序（2学时） 4、归并排序 5、基数排序（2学时）教学重点及难点重点：1、各种排序方法的特点及其应用；实现排序的各种算法 难点：各种排序算法的时间复杂度分析及应用中排序方法的选择教学手段讲授法、案例教学法作业、讨论、思考1、用一组数据，采用不同的方法进行排序，比较各种排序方法在最好和最坏的情况下的比较次数。2、分析各种排序方法的适用场合。课后小结本章主要介绍了多种内部排序方法：插入