计算机与信息科学系教案

计算机与信息科学系教案教研室：计算机应用教研室授课教师：编号：1授课时间第2周第1-2次课授课题目第1章绪论授课类型理论课(是)；实践课()教学时数2学时教学目的及要求1、理解计算机信息处理中数据组织与运算处理的关系；2、熟悉各名词、术语的含义，掌握数据结构相关基本概念，特别是数据、数据元素、数据对象、数据结构、逻辑结构、存储结构等；3、了解数据的逻辑结构和存储结构之间的关系，了解常见的“集合、线性表、树、图”的逻辑结构形式和“顺序、链表、索引、散列”存储组织方法；4、了解抽象数据类型的定义、表示与实现方法。5、算法教学内容提要1、数据结构研究的主要内容与涉及的基本概念；2、数据类型与抽象数据类型。3、算法教学重点及难点1、数据的逻辑结构、存储结构与运算方法之间的关系2、算法时间复杂度的衡量教学手段讲授法、案例教学法作业、讨论、思考思考：1、抽象数据类型与数据类型的区别？2、时间复杂度的比较？课后小结本章重点讲解了数据结构的相关概念、几种常见的数据结构，难点是抽象数据类型的定义以及算法时间复杂度的分析。参考资料[1］严蔚敏等，《数据结构题集》,1995［2］WilliamFord，WilliamTopp，《DataStructurewithC++》清华大学出版社PrenticeHall联合出版,1996[3]李春葆等，《数据结构与算法教程》，清华大学出版社，2005[4]（美）MarkAllenWeiss著冯舜玺译，《数据结构与算法分析—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］严蔚敏等，《数据结构》（第二版）清华大学出版社,1993［2］WilliamFord，WilliamTopp，《DataStructurewithC++》清华大学出版社PrenticeHall联合出版,1996[3]李春葆等，《数据结构与算法教程》，清华大学出版社，2005[4]（美）MarkAllenWeiss著冯舜玺译，《数据结构与算法分析—c语言描述》，机械工业出版社，2004（6）[5]郝文化，《数据结构考研辅导教程》，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室授课教师：编号：3授课时间第3周第5次课授课题目第2章线性表授课类型理论课(是)；实践课()教学时数4学时教学目的及要求1、掌握线性表的应用教学内容提要1、线性表的合并；2、一元多项式的相加的实现教学重点及难点重点：1、线性表的应用难点：1、一元多项式的链式实现教学手段讲授法、案例教学法作业、讨论、思考1、一元多项式相加与有序表的合并有什么异同？课后小结本节介绍了线性结构的应用实例—有序表的合并和一元多项式的相加。参考资料[1］严蔚敏等，《数据结构》（第二版）清华大学出版社,1993［2］WilliamFord，WilliamTopp，《DataStructurewithC++》清华大学出版社PrenticeHall联合出版,1996[3]李春葆等，《数据结构与算法教程》，清华大学出版社，2005[4]（美）MarkAllenWeiss著冯舜玺译，《数据结构与算法分析—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］严蔚敏等，《数据结构》（第二版）清华大学出版社,1993［2］WilliamFord，WilliamTopp，《DataStructurewithC++》清华大学出版社PrenticeHall联合出版,1996[3]李春葆等，《数据结构与算法教程》，清华大学出版社，2005[4]（美）MarkAllenWeiss著冯舜玺译，《数据结构与算法分析—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］严蔚敏等，《数据结构》（第二版）清华大学出版社,1993［2］WilliamFord，WilliamTopp，《DataStructurewithC++》清华大学出版社PrenticeHall联合出版,1996[3]李春葆等，《数据结构与算法教程》，清华大学出版社，2005[4]（美）MarkAllenWeiss著冯舜玺译，《数据结构与算法分析—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］严蔚敏等，《数据结构》（第二版）清华大学出版社,1993［2］WilliamFord，WilliamTopp，《DataStructurewithC++》清华大学出版社PrenticeHall联合出版,1996[3]李春葆等，《数据结构与算法教程》，清华大学出版社，2005[4]（美）MarkAllenWeiss著冯舜玺译，《数据结构与算法分析—c语言描述》，机械工业出版社，2004（6）[5]郝文化，《数据结构考研辅导教程》，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室授课教师：编号：7授课时间第6-7周第11－14次课授课题目第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.6m元多项式的表示§5.7广义表的递归算法5.7.1求广义表的深度5.7.2复制广义表5.7.3建立广义表的存储结构教学重点及难点重点：1、稀疏矩阵的定义与表示2、三元组的定义和应用3、广义表各种计算难点：1、稀疏矩阵求地址2、三元组的应用3、广义表的存储结构的表示教学手段讲授法、案例教学法作业、讨论、思考思考：1、稀疏矩阵中各种特殊矩阵的地址的计算？2、用三元组实现一元多项式的相加？3、广义表中各种操作的实现？课后小结1、掌握对特殊矩阵的压缩存储以及三元组存储2、熟练运用特殊矩阵的基本操作3、了解广义表的概念、应用范围和基本操作参考资料[1］严蔚敏等，《数据结构》（第二版）清华大学出版社,1993［2］WilliamFord，WilliamTopp，《DataStructurewithC++》清华大学出版社PrenticeHall联合出版,1996[3]李春葆等，《数据结构与算法教程》，清华大学出版社，2005[4]（美）MarkAllenWeiss著冯舜玺译，《数据结构与算法分析—c语言描述》，机械工业出版社，2004（6）[5]郝文化，《数据结构考研辅导教程》，北京希望电子出版社，2005（9）。计算机与信息科学系教案教研室：计算机应用教研室授课教师：编号：8授课时间第8-9周第15－18次课授课题目第6章树和二叉树授课类型理论课(是)；实践课()教学时数8学时教学目的及要求1、了解树的基本概念；2、理解二叉树的性质和存储结构；3、掌握遍历二叉树和线索二叉树；4、熟悉树的存储结构和遍历；5、了解集合的一种表示方法；6、掌握哈夫曼树及其应用教学内容提要1、树的定义和存储结构（1学时）2、二叉树的定义、性质、存储结构（2学时）3、二叉树的遍历、线索算法（2学时）4、树和二叉树的转换（1学时）5、哈夫曼树及其应用（2学时）教学重点及难点重点：1、二叉树的概念、性质；2、二叉树的遍历方式；3、构造二叉排序树难点：1、二叉树的遍历方式；2、二叉排序树的构造方法；3、二叉树的线索化。教学手段讲授法、案例教学法作业、讨论、思考。完成课本中没有完成的有关二叉树的基本操作的实现。课后小结树及二叉树在实际应用中使用很广，通过本章的学习，学