数据结构与算法（Java语言版） 教案全套（48+8）耿祥义

参考教案（共计56学时，含4个上机实践教案）耿祥义编写《数据结构与算法（java语言版）清华大学出版社出版耿祥义，张跃平主编28个样例教案的有关说明如下：教案应该是担任课程教学的教师本人根据教学大纲和自己的教学方法、经验、硬件和软件环境以及学生的具体接受能力和其他实际情况事先预备的教学实施预案。教师可能还需要动态的调整，即根据实际教学过程的具体情况和经验，进行必要的调整。因此，这里给出28个样例教案完全是只具有参考意义的资料，即仅仅供参考。56学时（含8学时实践）的参考教案分配表如下。参考教案分配表序号内容学时（56）参考教案（28个，含实践）1数据结构简介，算法复杂度2教案12递归算法6教案2，教案3，教案43上机实践2教案5（实践）4数组与Arrays类6教案6，教案7，教案85链表与LinkedList类6教案9，教案10，教案116顺序表与ArrayList类6教案12，教案13，教案147上机实践2教案15（实践）8栈与Stack类2教案169队列与ArrayDeque类2教案177上机实践2教案18（实践）8二叉树与TreeSet类4教案19，教案209散列结构与HashMap类4教案21，教案2210集合与HashSet类2教案2311上机实践2教案24（实践）12常用算法与Collections类2教案2513图论4教案26，教案2714经典算法思想2教案28

参考教案1（2学时）主要内容1.数据结构简介2.算法复杂度教材第1章和第2章数据结构(教材第1章)算法与复杂度（教材第2章）基础知识1.逻辑结构，物理结构，存储结构，算法与结构（第1章）。2.算法以及算法的复杂度（教材2.2节）重点知识常见复杂度（教材2.3节）基础算法1.找出1至n的连续多个自然数中缺失的某个数（例子2.5）2.起泡法重点算法二分法(例子2.9)，欧几里得算法（例子2.10)难点算法给出包含若干个正整数的最短等差序列（例子2.12）。两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时结合24节气，感性理解线性结构，可以和学生交流，让学生给出他自己熟悉的生活中的线性结构。然后给出线性结构的定义。结合年级结构，感性理解树结构，可以和学生交流，让学生给出他自己熟悉的生活中的树结构。然后给出树结构的定义，特别讲解图1.2示意的二叉树的特点。结合焊接点形成的框架结构，感性理解图结构，可以和学生交流，让学生给出他自己熟悉的生活中的图结构。然后给出图结构的定义。简单介绍集合，以及物理结构和算法与结构第2个学时1.介绍算法和复杂度时候，要特别强调什么是基本操作：耗时仅仅依赖于特定的硬件设施，不依赖于一个正整数n，即不会随着n的增加而增大。2.结合对应的例子讲解常见复杂度、重点讲解基础算法：找出1至n的连续多个自然数中缺失的某个数（例子2.5）、起泡法（例子2.7）、重点算法：二分法，欧几里得算法，特别注意分析二者的复杂度（例子2.9和例子2.10）、仔细分析难点算法：给出包含若干个正整数的最短等差序列（例子2.12）。多媒体辅助PPT电子讲义。作业在习题1和习题2中挑选有关内容布置相关作业。

参考教案2（2学时）主要内容教材第3章（递归算法）3.1-3.4递归算法教材3.1线性与非线性递归教材3.2问题与子问题教材3.3递归与迭代教材3.4基础知识递归算法。重点知识1.线性与非线性递归。2.问题与子问题基础算法1.计算星期数（例子3.1）2.Fibonacci序列（例子3.2）3.反转字符序列（例子3.4）4.计算圆周率重点算法判断某个数是否是数组的元素值（例子3.6）难点算法求两个正整数的最大公约数（例子3.7）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图3.1和3.2讲解什么是递归以及特点，说明如何计算其复杂度。结合例子3.1（基础算法，求星期数）讲解线性递归，以及复杂度的计算。结合例子3.2（基础算法Fibonacci序列）讲解非线性递归，特别要结合图3.6和3.7说明其空间复杂度是On（初学者容易误解其空间复杂度是O2第2个学时：1.结合例子3.3，说明什么是问题与子问题，重点讲解例子3.4，即基础算法：反转字符序列。2.结合例子3.5（计算圆周率），说明递归与迭代的特点和关系，重点讲解例子3.6和例子3.7，即重点算法：判断某个数是否是数组的元素值和难点算法：求两个正整数的最大公约数。多媒体辅助PPT电子讲义。作业在习题3中挑选有关内容布置相关作业。

参考教案3（2学时）主要内容教材第3章（递归算法）3.5-3.6多重递归教材3.5经典递归教材3.6基础知识递归算法。重点知识1.杨辉三角形。2.老鼠走迷宫基础算法求n-位十进制数中，出现含有偶数多个数字6的数的数量（例子3.8）重点算法输出杨辉三角形（例子3.9）难点算法老鼠走迷宫（例子3.10）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：复习递归的基本知识，然后引出什么是多重递归。结合例子3.8（基础算法：求n-位十进制数中，出现含有偶数多个数字6的数的数量）讲解多重递归，其复杂度留给学生自己思考。介绍经典递归：杨辉三角形的两个递归公式①和②，以及相应的代码，并强调二者的时间复杂度的不同，反复演示例子3.9的运行效果。加深学生对这个重点算法的理解。第2个学时：1.叙述老鼠走迷宫的递归算法，并解释其正确性。2.仔细分析例子3.10老鼠走迷宫的递归算法，并修改代码，给出几种迷宫，比如，迷宫有出口，老鼠能找到出口；迷宫有出口，但老鼠无法到达出口，即迷宫不通；迷宫无出口。演示运行效果。多媒体辅助PPT电子讲义。作业在习题3中挑选有关内容布置相关作业。

参考教案4（2学时）主要内容教材第3章（递归算法）3.6-3.7经典递归教材3.6优化递归教材3.7基础知识递归算法，汉诺塔重点知识优化递归基础算法汉诺塔的递归算法和迭代算法（例子3.11，例子3.12）重点算法优化递归，计算Fibonacci数列（例子3.13）难点算法优化递归，输出杨辉三角形（例子3.14）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：复习递归的基本知识，然后讲解汉诺塔的递归算法（例子3.11）。结合表3.1，介绍汉诺塔的一些规律，引出汉诺塔的迭代算法。然后讲解例子3.2，最后总结递归和迭代算法各自的优缺点：递归优缺点：优点是代码简练，容易理解解决问题的思路或发现数据的内部的逻辑规律，具有很好的可读性。缺点是可能导致运行时刻的栈溢出。迭代优缺点：优点是同一问题的迭代算法的空间复杂度通常低于递归算法的空间复杂度，缺点是代码可能比较复杂，处理数据的过程也可能比较复杂，代码不如递归简练。第2个学时：1.讲解优化递归算法，并解释其手法：用空间换取时间，简要介绍散列表的用法，不必深究其细节。2.仔细分析例子3.13（重点算法：优化递归，计算Fibonacci数列）和例子3.14（难点算法：优化递归，输出杨辉三角形），体现优化的作用。演示运行效果。多媒体辅助PPT电子讲义。作业在习题3中挑选有关内容布置相关作业。

参考教案5（2学时，实践）1.实践前的复习完成下列选择题。（1）对于线性表L=(A,R)，下列叙述正确的是(A.对于A中任意一个节点a,一定存在唯一的一个节点b(b≠a),使得(a,b)∈RB.对于A中任意一个节点a,一定存在唯一的一个节点b(b≠a),使得(b,a)∈RC.A中一定存在一个节点a,使得对A中任意一个节点b,都有(a,b)∉R。D.对于A中每个节点a，都有(a,a（2）下列叙述正确的是()。A.3+4-100+6*19不属于基本操作。B.一个算法里可以有无限多个局部变量。C.算法里出现无限循环，它的时间复杂度就是O(D.基本操作是在有限时间内能被完成的计算步骤、不依赖于一个正整数n、不会随着n的增加而增大。（3）下列叙述正确的是()。A.O(n)复杂度小于O(logn)B.O(nlogn)大于O(nC.O(n!)复杂度大于OD.O(nlogn)复杂度小于（4）下列叙述正确的是()。A.所有线性递归的空间复杂度一定是线性复杂度O(n)B.某些线性递归的空间复杂度是对数复杂度O(C.所有线性递归的时间复杂度一定是线性复杂度O(n)D.通过优化非线性递归，可以降低其空间复杂度。（5）下列叙述正确的是()。A.Fibonacci序列的递归算法优化后的时间复杂度仍然是O(B.汉诺塔的递归算法的时间复杂度是O(C.汉诺塔的递归算法的时间复杂度是O(D.杨辉三角形的递归算法的空间复杂度是O(2.实践内容完成后，要向老师展示程序的运行效果，老师根据完成情况，记载相关成绩。（1）在一个类中编写一个方法，计算正整数各位上的数字之和，比如方法是intdigitSum(intnumber)，如果number是352，该方法返回10。要求publicstaticintdigitSum(intnumber)的时间复杂度是O(n)，空间复杂度是O1，n是正整数（2）用递归方法计算阶乘的后j位上的数字组成的数，比如递归方法是longD(intn,intj)，当n!的长度不足j时，该方法返回n!，如果n!的长度大于等于j时，返回n!的后j位上的数字组成的数，如果（3）调试例子3.5，修改代码，让程序运行时刻出现栈溢出。

参考教案6（2学时）主要内容教材第4章数组与Arrays类4.1-4.3引用与参数存值教材4.1数组与排序教材4.2数组的二分查找教材4.3基础知识数组的引用与参数存值。重点知识1.数组与排序。2.数组的二分查找基础算法1.用参数存放面积（例子4.2）2.返回出现次数最多的字母（例子4.3）重点算法1.按体重快速排序（例子4.4）2.归并排序数组（例子4.5）难点算法1.用二分法统计数字出现的次数（例子4.6）2.过滤数组(例子4.7)两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：通过例子1掌握数组的引用，然后讲解基础算法：用参数存放面积（例子4.2）和返回出现次数最多的字母（例子4.3）介绍快速排序算法的思想，特别要强调什么是稳定和不稳定排序，不必纠结快速排序的代码实现，可以留给学生自学，重点是会使用Arrays类的sort()快速排序方法即可，并知道这个快速排序的时间复杂度是nlog(n),是不稳定排序，而起泡法是稳定排序。然后讲解重点算法：按体重快速排序（例子4第2个学时：介绍归并排序算法的思想，特别要强调什么是稳定和不稳定排序，不必纠结归并排序的代码实现，可以留给学生自学，重点是会使用Arrays类的parallelSort()归并排序方法，和它的优点即可，并知道这个归并排序的时间复杂度是nlog(n),是稳定排序，而Arrays类的sort()快速排序方法是不稳定排序。然后讲解重点算法：归并排序数组（介绍二分法的算法思想，强调学会使用Arrays类中的binarySearch()方法，然后讲解难点算法：用二分法统计数字出现的次数（例子4.6）和过滤数组（例子4.7）。多媒体辅助PPT电子讲义。作业在习题4中挑选有关内容布置相关作业。

参考教案7（2学时）主要内容教材第4章数组与Arrays类4.4-4.6数组的复制教材4.4数组的比较教材4.5公共子数组教材4.6基础知识数组的引用。重点知识1.copyOf(int[]a,intnewLength)方法。2.copyOfRange(int[]a,intfrom,intto)方法。基础算法1.模拟买福利彩票“双色球”（例子4.8）2.围圈留一问题（例子4.9）重点算法1.处理数组中重复的数据（例子4.10）2.寻找单词并输出单词出现的次数（例子4.11）难点算法寻找一个最大公共子数组（例子4.12）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：说明使用数组之间的引用赋值无法实现数组的复制，然后介绍copyOf(int[]a,intnewLength)和copyOfRange(int[]a,intfrom,intto)方法的作用。讲解基础算法：模拟买福利彩票“双色球”（例子4.8）和围圈留一问题（例子4.9），讲解重点算法：处理数组中重复的数据（例子4.10）和寻找单词并输出单词出现的次数（例子4.11）第2个学时：讲解难点算法：寻找最大公共子数组的算法（例子4.12）时，一定要结合图4,14仔细讲解所使用的算法：向左滑动法，并复习“异或”运算的作用。在讲解例子4.12的代码过程中可以抓住重点代码，说明其功能和作用，至于代码技术的细节可以留个学生课后自己慢慢琢磨，课堂上主要讲清楚算法实现的主要思路即可。多媒体辅助PPT电子讲义。作业在习题4中挑选有关内容布置相关作业。

参考教案8（2学时）主要内容教材第4章数组与Arrays类4.7-4.11数组的更新教材4.7数组的前缀运算教材4.8动态遍历教材4.9数组与洗牌教材4.10数组与生命游戏教材4.11基础知识单值更新和动态更新。重点知识动态遍历。基础算法1.数组的前缀运算（例子4.14）2.动态遍历数组（例子4.15）重点算法数组与洗牌（例子4.18）难点算法生命游戏（例子4.19）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合例子4.13讲解动态更新的方法。然后介绍基础算法：数组的前缀运算（例子4.14）。讲解动态遍历的好处，接着讲解基础算法：动态遍历数组（例子4.15），以及例子4.16，即自己编写动态方法，可以加强对动态遍历技术的理解。多线程遍历可以留给学生自学。第2个学时：讲解重点算法：数组与洗牌（例子4.18），特别要讲清楚洗牌算法和普通的抽取随机数的不同（洗牌算法的特点:每张牌都不在最初的位置上(对于非单张牌)）。结合图4.22讲解生命游戏的算法。然后可以仔细讲解难点算法：生命游戏的代码（例子4.19），并修改代码：修改生命的初始状态，让学生体会生命游戏的效果，激发学生的兴趣。多媒体辅助PPT电子讲义。作业在习题4中挑选有关内容布置相关作业。

参考教案9（2学时）主要内容教材第5章链表与LinkedList类5.1-5.6链表的特点教材5.1创建链表教材5.2查询节点教材5.3添加节点教材5.4删除节点教材5.5更新节点教材5.6基础知识链表的特点。重点知识创建链表基础算法1.模拟随机布雷（例子5.3）2.球队的淘汰赛（例子5.4）重点算法模拟双色球和过滤链表（例子5.6）难点算法处理链表中重复的数据（例子5.7）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图5.1至5.5讲解链表的特点，使用例子5.1讲解如何创建链表，结合例子5.2讲解如果查询链表。讲解基础算法：模拟随机布雷（例子5.3），球队的淘汰赛（例子5.4）。第2个学时：结合例子5.5讲解添加节点。讲解重点算法：解模拟双色球和过滤链表（例子5.6）。讲解难点算法：处理链表中重复的数据（例子5.7）。结合例子5.8讲解如何更新节点。多媒体辅助PPT电子讲义。作业在习题5中挑选有关内容布置相关作业。

参考教案10（2学时）主要内容教材第5章链表与LinkedList类5.7-5.9链表的视图教材5.7链表的排序教材5.8遍历链表教材5.9基础知识链表的视图。重点知识链表的排序，遍历链表。基础算法1.使用视图更新链表节点中的数据（例子5.9）2.排序链表（例子5.10）重点算法使用单项迭代器和双向迭代器遍历链表（例子5.11）使用链表解决约瑟夫问题（例子5.12）难点算法1.动态遍历链表计算消费总额（例子5.13）。2.动态遍历链表计算数组元素值的和（例子5.14）。两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图5.15至5.16讲解链表的特点，讲解基础算法：使用视图更新链表节点中的数据（例子5.9）。讲解基础算法：排序链表（例子5.10）。结合图5,21，讲解重点算法：使用单项迭代器和双向迭代器遍历链表（例子5.11）。第2个学时：讲解重点算法：使用链表解决约瑟夫问题（例子5.12）。讲解难点算法：动态遍历链表计算消费总额（例子5.13），动态遍历链表计算数组元素值的和（例子5.14）。多媒体辅助PPT电子讲义。作业在习题5中挑选有关内容布置相关作业。

参考教案11（2学时）主要内容教材第5章链表与LinkedList类5.10-5.12链表与数组教材5.10不可变链表教材5.11编写简单的链表教材5.12基础知识链表与数组。重点知识编写简单的链表。基础算法1.将链表节点中的对象放到数组中(例子5.15)。2.把数组元素值放到不可变链表中(例子5.16)。重点算法例子5.17中的Note类。难点算法例子5.17中的Linkedint类。两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：讲解基础算法：将链表节点中的对象放到数组中(例子5.15)，把数组元素值放到不可变链表中(例子5.16)。第2个学时：讲解重点算法：例子5.17中Note类。讲解难点算法：例子5.17中Linkedint类。多媒体辅助PPT电子讲义。作业在习题5中挑选有关内容布置相关作业。

参考教案12（2学时）主要内容教材第6章顺序表与ArrayList类6.1-6.4顺序表的特点教材6.1创建顺序表教材6.2顺序表的常用方法教材6.3遍历顺序表教材6.4基础知识顺序表的特点。重点知识创建顺序表基础算法遍历顺序表并添加新节点（例子6.4）重点算法动态遍历顺序表输出二进制、八进制和十六进制码值（例子6.5）难点算法用筛选法求素数（例子6.6）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：讲解顺序表的特点，并注意和链表的不同之处。使用例子6.1讲解如何创建链表，结合例子6.2和例子6.3讲解顺序表的常用方法。遍历顺序表并添加新节点（例子6.4）。第2个学时：讲解重点算法：动态遍历顺序表输出二进制、八进制和十六进制码值（例子6.5）。讲解难点算法：用筛选法求素数（例子6.6）。多媒体辅助PPT电子讲义。作业在习题6中挑选有关内容布置相关作业。

参考教案13（2学时）主要内容教材第6章顺序表与ArrayList类6.6顺序表与全排列教材6.6基础知识全排列。重点知识递归或迭代求全排列。基础算法用递归法求全排列（例子6.7）重点算法数字填空（例子6.8）难点算法迭代法求全排列（例子6.9）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：讲解基础算法：用递归法求全排列（例子6.7）。然后讲解重点算法：数字填空（例子6.8），体现基础算法在解决这类的问题中的作用。第2个学时：讲难点算法：迭代法求全排列（例子6.9）。一定结合图6.10至6.13讲清楚求全排列使用的字典序算法，然后结合图6.10至6.13讲例子6.9中代码的细节。多媒体辅助PPT电子讲义。作业在习题6中挑选有关内容布置相关作业。

参考教案14（2学时）主要内容教材第6章顺序表与ArrayList类6.7，6.8，6.9顺序表与组合教材6.7顺序表与记录教材6.8Vector类教材6.9基础知识组合，顺序表与一维数组。重点知识迭代法求全组合。基础算法顺序表与记录（例子6.14）重点算法用迭代法（例子6.10）或递归法求组合（例子6.11）难点算法用天平秤重量（例子6.12）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：讲解重点算法：用迭代法求组合（例子6.10）。递归法求组合（例子6.11）第2个学时：讲难点算法：用天平秤重量（例子6.12），特别强调重点算法递归法求组合（例子6.11）在用天平秤重量中的重要性，甚至可以记忆下该重点算法，在需要用组合来解决实际问题时，可以直接使用该重点算法：递归法求组合。讲解顺序表与一维数组（例子6.13）,讲解基础算法：顺序表与记录（例子6.14）。简单介绍Vector泛型类或让学生自学。多媒体辅助PPT电子讲义。作业在习题6中挑选有关内容布置相关作业。

参考教案15（2学时，实践）1.实践前的复习完成下列选择题。（1）Arrays类的sort()方法是()。A.双轴快速排序。B.稳定排序。C.时间复杂度比气泡法高的排序。D.时间复杂度比选择法高的排序。（2）下列叙述正确的是()。A.链表的单向迭代器在遍历链表时也可以删除节点。B.链表的单向或双向迭代器在遍历链表时，不允许链表调用set(intindex，Eobj)方法更新节点中的数据。C.如果增加或删除链表节点，链表之前的视图仍然能被使用。D.可以对不可变链表经行排序操作。（3）顺序表的时间复杂度不是O(1)的方法是()A.publicEget(intindex)。B.publicintindexOf(Objectobj)。C.publicbooleanadd(Ee)。D.publicEset(intindex,Eelement)。（4）对于下列代码，下列叙述错误的是()。importjava.util.LinkedList;importjava.util.ListIterator;publicclassC{publicstaticvoidmain(Stringargs[]){LinkedList<String>list=newLinkedList<>();for(charc='A';c<='F';c++){list.add(""+c);}ListIterator<String>iterTwoWay=list.listIterator();System.out.println(iterTwoWay.next());//代码ASystem.out.println(iterTwoWay.previous());//代码BiterTwoWay.next();System.out.println(iterTwoWay.next());//代码CiterTwoWay.next();iterTwoWay.next();System.out.println(iterTwoWay.next());//代码D}}A.代码A输出的结果是A。B.代码B输出的结果是B。C.代码C输出的结果是B。D.代码D输出的结果是E。（5）对于下列代码，下列叙述错误的是()。importjava.util.ArrayList;publicclassC{publicstaticvoidmain(Stringargs[]){ArrayList<String>list=newArrayList<>();list.add("A");list.add("B");list.add("F");list.add("F");list.add("B");list.add("G");System.out.println(list.lastIndexOf("F"));//代码ASystem.out.println(list.remove("B"));//代码BSystem.out.println(list.indexOf("B"));//代码CSystem.out.println(list.remove(2));//代码D}}A.代码A输出的结果是3。B.代码B输出的结果是true。C.代码C输出的结果是1。D.代码D输出的结果是F。2.实践内容完成后，要向老师展示程序的运行效果，老师根据完成情况，记载相关成绩。（1）输出int型数组的一个最长的递增子数组，例如，对于int[]a={15,16,6,8,9,10,11,11,11,8,2,10};程序输出[6,8,9,10,11]。（2）链表删除头节点和尾节点的时间复杂度都是O(1)。对于某些问题，可以利用链表的这一特点快速的处理数据。编写一个程序，判断字符串是否是回文串。算法提示：将字符串中的全部字符按顺序依次添加到链表，然后开始分别从头、尾删除链表的节点，如果字符串是回文串，那么从头删除的节点中的字符一定和从尾删除的节点中的字符相同，当链表中剩余的节点数目不足2个时，停止删除操作。（3）将一个节点是Integer的顺序表listOne升序排序，然后将另一个节点是Integer的顺序表listTwo中的节点插入到listOne，并继续保持listOne是升序。

参考教案16（2学时）主要内容教材第7章栈与Stack类7.1-7.8栈的特点教材7.1栈的创建与独特的方法教材7.2栈与回文串教材7.3栈与递归教材7.4栈与undo操作教材7.5栈与括号匹配教材7.6栈与深度搜素教材7.7栈与后缀表达式教材7.8基础知识栈的特点。重点知识栈的创建与独特方法。基础算法1.利用栈判断一个字符串是否为回文串（例子7.2）2.使用栈实现撤销操作（例子7.5）3.检查括号是否匹配（例子7.6）重点算法用栈模拟老鼠走迷宫（例子7.7）难点算法1.使用栈计算后缀表达式（例子7.8）2.把中缀表达式转换为后缀表达式（例子7.9）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图7.1讲解栈的特点，使用例子7.1讲解如何创建栈以及栈的独特方法。讲解基础算法：利用栈判断一个字符串是否为回文串（例子7.2）。例子7.3和7.4可以作为自学内容（根据课堂时间情况）。讲解基础算法：使用栈实现撤销操作（例子7.5），检查括号是否匹配（例子7.6）。第2个学时：讲解7.7节，讲清什么叫深度优先搜索，以及栈为何能体现深度优先搜索。结合例子5.5讲解添加节点。讲解重点算法：用栈模拟老鼠走迷宫（例子7.7）。讲解难点算法：使用栈计算后缀表达式（例子7.8），要特别结合图7.10介绍后缀表达式的算法。对于中缀表达式转换为后缀表达式（例子7.9），老师课堂可以只讲算法的思想，其详细代码可以留作学生自学。多媒体辅助PPT电子讲义。作业在习题7中挑选有关内容布置相关作业。

参考教案17（2学时）主要内容教材第8章队列与Stack类8.1-8.8队列的特点教材8.1队列的创建与独特的方法教材8.2队列与回文串教材8.3队列与加密解密教材8.4队列与约瑟夫问题教材8.5队列与广度搜素教材8.6队列与网络爬虫教材8.7队列与排队教材8.8基础知识队列重点知识队列的创建与独特方法。基础算法1.利用队列判断一个字符串是否为回文串（例子8.2）2.使用队列加密、解密字符序列（例子8.3）3.队列与约瑟夫问题（例子8.4）重点算法使用广度优先搜索法进行排雷（例子8.5）难点算法1.使用网络爬虫爬去网页（例子8.6）2.用队列模拟排队（例子8.7）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图8.1讲解队列的特点，使用例子8.1讲解如何创建队列以及队列的独特方法。讲解基础算法：利用队列判断一个字符串是否为回文串（例子8.2）。讲解基础算法：使用队列加密、解密字符序列（例子8.3），队列与约瑟夫问题（例子8.4）。第2个学时：讲解7.7节，讲清什么叫广度优先搜索，以及队列为何能体现广度优先搜索。讲解重点算法：使用广度优先搜索法进行排雷（例子8.5）。讲解难点算法：使用网络爬虫爬去网页（例子8.6）。对于难点算法：用队列模拟排队（例子8.7），可以根据时间情况，只讲解思想，代码细节留给学生自学。多媒体辅助PPT电子讲义。作业在习题8中挑选有关内容布置相关作业。

参考教案18（2学时，实践）1.实践前的复习完成下列选择题。（1）Stack<E>的时间复杂度不是O(1)的方法是()A.publicbooleanempty()。B.publicsynchronizedintindexOf(Objectobj)。C.publicsynchronizedEpeek()。D.publicsynchronizedbooleanadd(Ee)。（2）下列叙述错误的是()。A.队列擅长在线性表的头、尾两端实施删除和添加操作。B.栈擅长在线性表尾端实施删除和添加操作。C.顺序表擅长在线性表的中间实施删除和添加操作。D.双链表擅长在线性表的头、尾两端实施删除和添加操作。（3）对于下列代码，下列叙述错误的是()。importjava.util.Stack;publicclassC{publicstaticvoidmain(Stringargs[]){intm=0;intm1=0,m2=0;Stack<Integer>stack=newStack<>();stack.push(13);stack.push(17);m2=stack.pop();m1=stack.pop();m=m1+m2;System.out.println(m);//代码Astack.push(m);stack.push(6);m2=stack.pop();System.out.println(m2);//代码Bm1=stack.pop();m=m1*m2;System.out.println(m);//代码Cm=m1/m2;System.out.println(m);//代码D}}A.代码A输出的结果是30。B.代码B输出的结果是6。C.代码C输出的结果是180。D.代码D输出的结果是0。（4）对于下列代码，下列叙述错误的是()。importjava.util.ArrayDeque;publicclassB{publicstaticvoidmain(Stringargs[]){ArrayDeque<Integer>deque=newArrayDeque<>();deque.offer(10);deque.offerFirst(20);deque.offer(30);deque.offerFirst(50);deque.forEach((v)->{System.out.println(""+v);});System.out.println(deque.peek());//代码ASystem.out.println(deque.poll());//代码BSystem.out.println(deque.pollLast());//代码CSystem.out.println(deque.size());//代码D}}A.代码A输出的结果是50。B.代码B输出的结果是20。C.代码C输出的结果是30。D.代码D输出的结果是2。（5）下列叙述正确的是()。A.Stack<E>的isEmpty()方法是线程安全的。B.Stack<E>的empty()方法是线程安全的。C.Stack<E>的elementAt(intindex)。方法不是线程安全的。D.Stack<E>的intsearch(Objectobj)方法不是线程安全的。2.实践内容完成后，要向老师展示程序的运行效果，老师根据完成情况，记载相关成绩。（1）借助栈，在一个类中编写一个方法publicstaticStringreverse(Strings)，方法返回的String对象中的字符序列是参数s的字符序列的反转（倒置）字符序列。（2）农夫携带狼、羊、菜从河东岸到西岸，桥上限制农夫每次至多只能携带狼、羊、菜中的一种。另外，如果没有农夫看着，羊会吃菜，狼会吃羊，但狼不吃菜。农夫带羊过河办法之一：①农夫带羊过河，返回。②农夫带狼过河，带羊返回。③带菜过河、返回。④带羊过河。编程程序，通过两个队列：一个东岸队列和西岸队列，来模拟农夫过河。用数字1代表菜，数字2代表羊，数字3代表狼。将数字1，2，3存入东岸的队列中。东岸出列到西岸入列时，如果导致东岸的队列的长度是2，必须保证东岸的队列中的数字之和是4，否则重新入列东岸。如果西岸的队列的长度是2，必须保证西岸的队列中的数字之和是4，否则西岸出列，然后再入列东岸。

参考教案19（2学时）主要内容教材第9章二叉树与TreeSet类9.1-9.5二叉树的基本概念教材9.1遍历二叉树教材9.2二叉树的存储教材9.3平衡二叉树教材9.4二叉查询树和平衡二叉查询树教材9.5基础知识二叉树的基本概念重点知识二叉查询树和平衡二叉查询树。基础算法遍历与查询二叉树（例子9.1）重点算法中序遍历二叉查询树（例子9.2）难点算法创建平衡二叉查询树并查询（例子9.3）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图9.1讲解二叉树的基本概念。结合图9.2讲解遍历二叉树：前序遍历，中序遍历，后序遍历。讲解基础算法：遍历与查询二叉树（例子9.1）。第2个学时：讲解9.4节：平衡二叉树。结合图9.4讲解重点算法：中序遍历二叉查询树（例子9.2）。讲解难点算法：创建平衡二叉查询树并查询（例子9.3）。多媒体辅助PPT电子讲义。作业在习题9中挑选有关内容布置相关作业。

参考教案20（2学时）主要内容教材第9章二叉树与TreeSet类9.6-9.11TreeSet树集教材9.6树集的基本操作教材9.7树集的视图教材9.8树集与数据统计教材9.9树集与过滤数据教材9.10树集与节目单教材9.11基础知识TreeSet树集重点知识树集的基本操作。基础算法1.借助树集模拟双色球（例子9.5）2.使用树集存放节目单（例子9.11）重点算法1.统计随机数（例子9.8）2.使用树集过滤数据（例子9.9）3.处理重复的数据（例子9.10）难点算法借助树集求最大、最小连接数（例子9.6）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合例子9.4，讲TreeSet树集和它的基本操作。讲解基础算法：借助树集模拟双色球（例子9.5）。讲解难点算法：借助树集求最大、最小连接数（例子9.6）第2个学时：讲解9.8节：树集的视图（含例子9.7）。讲解重点算法：统计随机数（例子9.8），使用树集过滤数据（例子9.9），处理重复的数据（例子9.10）。讲解基础算法：使用树集存放节目单（例子9.11）。多媒体辅助PPT电子讲义。作业在习题9中挑选有关内容布置相关作业。

参考教案21（2学时）主要内容教材第10章散列表与HashMap类10.1-10.5散列结构的特点教材10.1简单的散列函数教材10.2HashMap类教材10.3散列表的基本操作教材10.4遍历散列表教材10.5统计字符、单词出现的次数和频率教材10.6基础知识散列结构的特点重点知识简单的散列函数。基础算法遍历散列表（例子10.4）难点算法统计字符、单词出现的次数和频率（例子10.5）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图10.1讲清楚散列结构。借助图10.2至10.4和例子10.1讲重点知识点：简单的散列函数。第2个学时：借助例子10.2和例子10.3讲解HashMap类和散列表的基本操作。讲解基础算法：遍历散列表（例子10.4）。讲解难点算法：统计字符、单词出现的次数和频率（例子10.5）多媒体辅助PPT电子讲义。作业在习题10中挑选有关内容布置相关作业。

参考教案22（2学时）主要内容教材第10章散列表与HashMap类10.1-10.5散列表与单件模式教材10.7散列表与数据缓存教材10.8TreeMap类教材10.9Hashtable类教材10.10基础知识TreeMap类，Hashtable类。重点知识单件模式。基础算法使用树映射排序数据（例子10.10）重点算法使用散列表缓存数据（例子10.7）难点算法用单件模式模拟只有一个太阳（例子10.6）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图10.11讲解单件模式，然后讲解难点算法：用单件模式模拟只有一个太阳（例子10.6）。讲解重点算法：使用散列表缓存数据（例子10.7）。第2个学时：讲解10.9节：TreeMap类，特别注意讲解和HashMap类的不同，讲解基础算法：使用树映射排序数据（例子10.10），对于例子10.8，如果时间不允许，可以让学生自学。介绍Hashtable类，重点介绍其线程安全的特点，有关代码可留给学生自学。多媒体辅助PPT电子讲义。作业在习题10中挑选有关内容布置相关作业。

参考教案23（2学时）主要内容教材第11章集合与HashSet类11.1-11.6集合的特点教材11.1HashSet类教材11.2集合的基本操作教材11.3集合与数据过滤教材11.4正整数集合的生成集教材11.5获得随机数的速度教材11.6基础知识集合的特点，HashSet类。重点知识集合的基本操作。基础算法使用集合和树集过滤数据（例子11.2）重点算法比较借助数组、链表、树集、集合获得随机数的速度（例子11.4）难点算法返回集合的生成集（例子11.3）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合例子1讲解集合的特点，HashSet类，集合的基本操作。特别强调：集合的添加、查找和删除元素等操作的时间复杂度通常为O(1)。讲解基础算法：使用集合和树集过滤数据（例子11.2）。第2个学时：讲解难点算法：返回集合的生成集（例子11.3）。讲解重点算法：比较借助数组、链表、树、集合获得随机数的速度（例子11.4）多媒体辅助PPT电子讲义。作业在习题11中挑选有关内容布置相关作业。

参考教案24（2学时，实践）1.实践前的复习完成下列选择题。（1）对于平衡二叉查询树，叙述正确的是()。A.查询时间复杂度OnB.查询时间复杂度是O(logn)。C.查询时间复杂度是O(nlogn)。D.查询时间复杂度是O(1)。（2）下列叙述错误的是()。A.红黑树是平衡的二叉查询树。B.AVL树是平衡的二叉查询树。C.红黑树的查询时间复杂度是O(logD.AVL树的查询时间复杂度是O(（3）对于图示意的二叉树，()是中序遍历的结果。注意这个二叉树不是查询二叉树。12121117613915图二叉树A.691113151712。B.121196131517。C.691113121517。D.961115131712。（4）叙述正确的是()。A.TreeMap<K,V>映射树也是散列结构。B.TreeMap<K,V>映射树是红黑树结构。C.TreeMap<K,V>映射树查询、添加和删除等操作的时间复杂度都是O(n)D.TreeMap<K,V>映射树中的Value中不能有两个相同的对象。（5）叙述正确的是()。A.HashSet集合中的元素仅仅同属一个集合，无任何关系。B.HashSet集合中的元素的存储是链式存储。C.HashSet集合中的元素形成的关系是线性关系。D.HashSet集合中的元象的逻辑关系是树形关系。2.实践内容完成后，要向老师展示程序的运行效果，老师根据完成情况，记载相关成绩。（1）某种学生小档案的中的数据是一个"键-值"(key,value)，其中key是学号，value是学生名称或介绍。编程用HashMap散列表存储学生小档案。使