高中信息技术选择性必修1“树结构及其实现”作业教学设计

高中信息技术选择性必修1“树结构及其实现”作业教学设计本作业面向普通高中信息技术选择性必修1《数据与数据结构》中“树结构及其实现”的学习任务，对应学生已经掌握线性表、栈、队列并能用类或字典记录结点关系之后的进阶阶段。作业不以“会做一道遍历题”为终点，而把目标放在三种能力的同步形成：能从现实情境中抽象出层次关系，能用指针思想或嵌套结构表达结点，能在遍历、构造、统计、优化中解释树形结构为何比平铺数据更有表达力。学生完成本组作业后，应能把目录树、组织架构、表达式求值、检索剪枝、编码压缩等问题放进同一套概念框架中辨认，知道根、叶、度、深度、高度、子树、路径、祖先与后代并非术语堆叠，而是解决问题的操作入口。设计依据来自高中信息技术课程对计算思维、数字化学习与创新的要求，也来自数据结构内部的知识逻辑：线性结构强调先后，树结构强调分支与归属；栈队列解决“次序暂存”，树解决“层级组织”；遍历不是背诵先序中序后序，而是规定访问结点的稳定秩序；实现不是只会写递归，而是能在递归定义、显式栈模拟、数组下标、邻接表表示之间作合理选择。作业表述尽量接近真实任务，少用空泛背景，多给可检验的数据、可复现的步骤与可争辩的方案。评价关注学生是否能说明“为什么这样组织数据”，而不只检查程序是否侥幸通过样例。学情判断建立在三类常见困难上。其一，学生容易把树看成图形记忆，忽视递归同构，导致会画不会算，会背不会改。其二，学生常把二叉树与普通树混同，把“每个结点最多两个孩子”的前提误带进家谱、目录、科目分类等多叉场景。其三，学生对遍历序的生成机制理解不稳，常把访问输出、递归展开、栈帧变化混在一起。作业因此安排“辨认—构造—追踪—迁移—反思”的阶梯：先用无代码任务厘清结构，再用半完成代码盯住关键语句，再进入小项目实现，最后用错误史记录促成元认知。作业总目标分解为四层。概念层，学生能用规范语言判定一棵树并指出结点属性，能区分子树形态与森林，能说明满二叉树、完全二叉树、二叉搜索树、平衡趋势的边界条件。表示层，学生能在顺序存储、链式存储、孩子兄弟表示、父指针表示之间说明适用限制，并能把嵌套字典、对象结点、二维表外键三种classroom常见写法互相转换。算法层，学生能稳定写出深度优先三种遍历与层序遍历，能把未知输入建树，能完成高度、叶数、路径和、最近公共祖先等基础统计，并能解释时间代价主要来自每个结点被有限次访问。迁移层，学生能在表达式求值、压缩编码直觉、自动补全剪枝、知识图谱局部查询中选出树形方案，并说明不选线性表的理由。作业周期建议安排十个课后碎片时段与一次九十分钟的集中调试课，总量控制在必修压力可承受范围内。纸笔任务约百分之三十五，上机任务约百分之五十，互评与修订约百分之十五。允许学生使用教材允许的语言完成代码，默认Python，也接受Java或C++思路说明；不允许提交由生成工具直接得到却说不清执行轨迹的答案。凡提交程序，必须附三条自造数据、一次边界失败记录和一段复杂度口头稿。这样做并非增加负担，而是把“能跑”与“会想”分开计分，避免样例巧合遮蔽概念空洞。一、作业内容与结构蓝图本单元作业以“层级问题实验室”为统摄情境，分五个任务群。任务群A叫“看见了树”，要求学生从校园网盘目录、赛事淘汰签表、行政区隶属、教材章节目录、生物分类阶元中选两例，画出不超过三十个结点的局部树，并标注根、内部结点、叶子、某结点的深度与整棵树高度。评分看抽象是否一致，例如淘汰赛若把“轮次”也画成父亲，就要追问轮次是事件还是参赛者；目录若把快捷方式当成孩子，就要讨论引用边会不会破坏树性。任务群B叫“一棵树有几种住法”，聚焦表示。学生用同一棵二叉树分别给出嵌套字典、结点类、数组堆式下标与边清单四种表示，写清空孩子如何标记，比较插入、找父、找子、序列化恢复的代价。普通树部分用“部门—岗位—人员”做多叉树，要求孩子兄弟表示和父指针表示各实现一次查询：给定结点列出全部后代，给定两个结点判断是否同层。作业故意不规定唯一格式，留出空间让学生发现表达自由越大，越需要约束空值、环、重名与孤立点。任务群C叫“沿着树的秩序走”，核心是遍历。纸笔部分给一棵带空位标记的二叉树，要求写先序、中序、后序与层序序列，再反向给中序加先序重建，给中序加层序讨论是否唯一。程序部分要求先写递归版本，再把先序改成显式栈版本，把层序改成队列版本；三者输出必须一致，否则不进入下一档。学生要在注释里标明“访问发生在何时”：进入结点、从左孩子返回、从右孩子返回，还是出队瞬间。这个区分是防止背模板的关键。任务群D叫“让树替我们减小无效劳动”，强调性质利用。二叉搜索树任务给定若干次插入、查找、删除叶结点操作，要求输出中序并解释它为何有序；退化链情形必须出现一次。堆任务用数组维护小顶堆，完成插入、弹出、堆化，并要求用层序数组反推形状。表达式树任务把带括号四则表达式转成树或直接由后缀表达式建树，再求值；哈夫曼思想只要求根据词频贪心合并并比较定长编码与变长前缀编码的位数，不追求工程完备。此处加入“贪心选择的局部理由是否充分”的答辩点，促使学生区分性质保证与经验直觉。任务群E叫“把树交还给问题”，是小项目。学生在三个主题中任选其一：班级图书角分类检索树，支持按主题路径定位与误放提醒；算术练习器，随机生成表达式树并给出分步求值痕迹；校园植物挂牌导览，依据特征二歧检索表识别植物。项目必须提交问题陈述、数据模型图、核心算法、测试矩阵、失败案例、同伴评审意见与最终反思。质量高低不看界面华丽，而看树是否真正承担组织、约束与加速作用。二、实施过程与课堂嵌入式作业指导第一次布置放在新授“树的基本概念”之后，时间控制在二十分钟。教师不急于讲定义，而投出三张图：一张公司组织图，一张无向连通但含环的好友关系局部图，一张只有一个结点向自身回指的异常图。学生用纸笔判断哪张能称为树，并把理由压缩成两句。教师收集的典型回答大致分三类：看分叉多少，看有没有回路，看是否像家谱。作业讲评从这三类出发，指出分叉多少只是形态感受，根唯一、连通且无环、任意两结点路径唯一才更贴近本质；有向树还要补充边的方向从父到子且入度除根外为一。此处不写成板书结论让学生抄，而要求每人把自己原句改成可判定条件，形成“原判断—漏洞—修订”三栏。第二次嵌入在递归思想回看。学生完成“高度与叶数”小卷，题目给出树T和子树关系，要求口算提议：若某结点有两个孩子，左子树高度为三，右子树高度为负一，能否成立。多数人能抓住空树高度约定，却会为负一与零争吵。作业指令明确采用本班统一约定：空树高度记负一，单结点树高度记零；若采用空树高度为零的教材旁注，则全体同步换算。这个约定不是为了标准答案本身，而是让学生理解递归出口必须与定义一致。教师巡视时只问三句：空树返回什么，非空树比较哪两个值，返回值向谁汇报。学生把这三句写进代码注释，递归函数的可信度明显提高。第三次嵌入在遍历课，采用“人即栈”的身体化活动。六名学生持结点卡站成二叉树形状，教师拿访问铃，学生按指令模拟递归：进入结点先举手表示到达，访问铃响才输出；左返回写L，右返回写R。台下同学记录显式栈内容，把到达、完成左子树、完成右子树三种状态转成三元组。活动后立刻布置同构作业：把课堂肉身模拟翻译成代码，禁止直接默写网络模板。学生常在这里暴露出把递归函数当成“自动全部做完”的黑箱倾向；教师要求画出一次调用的活动记录，标出参数、局部变量、返回地址，哪怕只画三层，也足以让先序与后序差别落地。第四次嵌入在建树与还原。作业给出先序ABDGGCEF与中序DGBAECF的示例，故意设置同名风险前先教“无重复值”前提。学生先画递归拆解表：先序首元素定根，中序按根切左右，左右规模决定先序下一段边界。随后反例追问：只给先序和后序能否唯一恢复二叉树；若能，需要补什么条件；若每个结点度已知又如何。教师不把话说死，要求学生提交一个可构造反例或一条充分条件。评分强调论证而非结论，鼓励用两个结点、三个结点的小反例推翻直觉。这个环节把遍历从输出练习提升为结构信息量的比较。第五次嵌入集中调试课，采用“故障门诊”。教师课前收集隐藏缺陷：把层序队列写成栈导致序反；二叉搜索树插入时未处理相等键导致丢失；数组堆下标一开始就混用零基与一基；表达式树把减法结合性当成可交换；多叉树删除子树后仍保留悬挂引用。门诊桌分四站，学生带自己的最小失败用例挂号，同伴先用一句话复述症状，再给出一项只改局部的建议。教师不直接替修，先把缺陷归于“结构约束被破坏”“访问时机错误”“边界约定漂移”“别名共享未隔离”四类。学生离场前必须在作业单写下缺陷类别、触发输入、修复前后输出、预防策略。这样，错误不再被红笔吞没，而成为可复用经验。第六次嵌入项目里程碑。项目不允许到期末一次性验收，而设三关：模型关看树是否必要，算法关看操作是否闭环，证据关看测试是否覆盖普通、边界、异常。模型关的否决项包括用树包装纯线性流水、根结点无意义、孩子含义随层变化。算法关的否决项包括全表扫描冒充检索、删除后完整性未检查、统计仍靠把树展开成列表再循环。证据关要求测试矩阵最少含空树、单结点、左斜链、右斜链、均衡树、重复键、非法字符、超深输入八类。学生每次过关只在ChangeLog写三行：改了什么，为什么改，哪条测试证明了它。第七次嵌入跨学科短时链接。生物的二歧检索表、数学的归纳定义、语文的篇章层级、通用技术的流程分解，都能成为树感来源，但作业不追求热闹拼盘。要求每组选一个外部情境，回答同一个技术问题：这个领域原先靠什么组织层级，转成计算模型后哪条规则被保留、哪条被简化、哪条必须新增。学生会发现生物检索强调二选一的判别特征，表达式树强调配对与优先级，目录树强调命名空间与路径解析。比较之后，树不再是屏幕里的箭头，而是把复杂世界切成可管理子问题的方式。三、代表性作业题组与作答要求概念辨认题给出一串操作：结点x有孩子y与z，y有孩子u，z为空叶子，另有一个未连接结点w。要求画出树或说明不成立，并求x的高度、y的深度、叶子数、度为二的结点数。满分答案必须处理w带来的歧义：若w游离，则整体是森林而非一棵树；若题目声明研究对象仅为x子树，则w不计。此类“条件先行”的回答比数字更重要。表示转换题给出嵌套字典表述的二叉树，要求转成数组下标表示并列出空位。学生需说明根放索引一还是索引零，左右孩子公式相应为二i与二i加一，或二i加一与二i加二。作业允许两种都被接受，但同一份答案不得混用。教师批改重点看孩子存在性判断、越界处理与完全性假设是否写出；若用于普通歪斜树，学生应指出空间浪费并改选链式。遍历追踪题给一棵八结点二叉树，要求写出四种序列。程序题不许只交输出，要交一张“访问时刻表”：递归进入、左返、右返、出队各发生什么。显式栈版本要求结点入栈次数可解释，后序可用右子树根标记或上次访问指针法其一，学生需说明采用哪一派并给出不变量。层序要求解释queue中保存的是“已发现但未访问”的结点，访问时机在出队；若把入队当访问，重复统计就会随之而来。重建题给中序BDAEC与先序ABDCE，恢复树后追问树高。拓展问给中序与后序是否同样可做，给先序与后序在二度结点存在时为何失效。学生可用“中序负责定界，先序或后序负责定根”作答；高阶回答会指出非二叉的普通有序树需要度数或孩子列表才能避免结构歧义。评价不奖励背口诀，奖励能构造二解反例。二叉搜索树题要求依次插入七、三、九、一、五、八、十，画出结果，再删除叶子一与只有单孩子的九之一侧情境改写。随后给同一批数改按已排序输入插入，比较高度变化，并由此说明随机化、平衡策略或输入清洗的意义。学生易错在把二叉搜索树中序有序当成定义本身，作业要求补一句：有序是左小右大约束与遍历规则共同推出的现象。删除部分本单元只到叶子与单孩子，双孩子删除作为选做，避免一次吞并过多机制。堆题给定数组十二、五、九、三、七，要求建成小顶堆，连续弹出两个最小值后给数组。作答要呈现下换与上浮方向，说明堆序只约束父子不约束兄弟，因此层序输出通常非有序。常见误区以为是把数组排序；作业反诘“若每次只要当前最小，是否有必要整体有序”，把学生引回部分排序的收益。与优先队列相连的口述稿要说明插入与弹出都为对数级依赖高度，而高度受完全二叉形态控制。表达式题给后缀序列342乘5加减的语义等价形式，要求建表达式树并求值，再说明括号在树中为何可以消失。学生需区分操作数成叶、运算符成内部结点、子树优先级由结构而非括号承担。遇到减法与除法，必须记录左右操作数来自出栈先后，不能凭感觉交换。选做层允许多元函数结点，但以普通树而非二叉树回应。编码直觉题给字符频率a五、b二、c一、d一，让学生按最小两项合并构造带权外部路径，比较等长两位编码与得到的前缀码总位数。答案不必追求与教材示例逐一相同，但合并步骤、码长分配、外部带权路径和要一致。教师要追问前缀性如何保证解码无歧义：任何一个码字不为另一码字前缀，恰与叶子承担符号、内部结点只作分流有关。学生由此看见树结构性质直接转成通信可靠性。四、评价量规与等级描述评价采用四维二十级量规，维度分别为结构抽象、表示实现、算法正确、证据表达。每维五档，不以细密扣分压迫学生，而以能力描述定位下一动作。结构抽象达到高档的标志，是能在真实材料中主动排除非层次噪音，发现环、重名、多父、悬空引用并给出处置。表示实现高档，是能根据操作频率选择存储，预知查询走父指针、枚举走孩子表、序列化讲究可逆。算法正确高档，不只所有公开测试通过，还能解释每个结点被处理次数与栈队列规模上界。证据表达高档，是结论、图、代码、测试之间能互相指认，读者无需问作者就能复现。等级转化避免一分定终身。纸笔概念占二十五，程序任务占三十五，项目占二十五，修订与互评占十五。若程序运行平平但反思能准确定位结构性误解，可在证据表达维度上调一档；若项目界面精致却树模型空洞，结构抽象直接降档。所有主观档必须落到可观察行为，例如“说出了空树约定与递归出口一致”，而非“态度认真”。教师给出的每次评语须包含一个可执行下一步，不超过二十八字，如“把后序访问改成从右返后触发，再测左斜链”。互评实行陌生作者制。学生拿到隐去姓名的作业，先不问对错，先复述对方模型：根是什么，孩子边表示什么，空值怎样写，最怕哪类输入。复述得到原作者确认后才可提建议。这个顺序能显著降低只看代码风格的浅层评论。互评记录纳入成绩，但只评价帮助质量，不评价感情色彩。有效建议要指到行、条件或不变量；无效建议如“多练习”“再认真点”不计分，退回重写。五、差异化支持与边界控制基础支持包提供三样东西：约定卡、空表、最小样例库。约定卡写明本班采用的空树高度、数组起点、相等键策略、非法输入处理方式。空表不是答案模板，而是必须填的空格：根判定、左界、右界、返回值、出口。最小样例库只含空、单、链、叉四类小树，帮助学生在庞大数据前先校准手势。使用支持包不扣分，但提交时必须注明用了哪几张卡，教师据此判断何时撤掉拐杖。进阶挑战不加重题量，而提高证明密度。可选题目包括：验证完全二叉树结点数为n时高度下取关系；讨论按层序列化带空位标记能否无损恢复；为普通树设计前序等价遍历并说明孩子顺序是否影响结果；在只允许常数额外空间时Morris线索化遍历的思想边界。挑战不给统一评分细则，只要求“主张—引理—反例检索—结论”四件齐备。选择挑战的学生可豁免部分重复基础题，但不能豁免测试与反思。对学习节奏较慢的学生，关键不是减少树，而是减少同时变动的量。先固定二叉，再谈多叉；先固定无损数据，再谈删除；先固定递归，再谈显式栈；先用图走查，再上机。每一步都保留可逆通道，允许学生回到上一稳定版本。作业系统或纸质袋中保存版本树本身就是隐喻，教师可借此点名：你的作业历史也是一棵树，主干是稳定提交，分支是试探，合并要留下理由。对超前学生，警戒也必要。急于套AVL、红黑树、线段树名称而无不变量意识者，要求其先证明二叉搜索树基本约束并保持五组操作后不破坏；滥用递归导致栈深风险者，要求估计深度并给迭代替代；迷信库函数者，要求在禁用结构库的小环境中重现核心。拔高不是把术语前移，而是把约束看得更清。六、作业讲评课的操作脚本讲评课不从分数开始，而从三份匿名切片开始：一份结构抽象漂亮但代码脆，一份代码通过但模型摇摆，一份反思诚恳却证据稀薄。学生先投票哪份最接近可继续研究，再说理由。教师把票型留在黑板，不立即裁决。随后三组分别修订同一处：给脆代码补边界输入，给摇摆模型写判定规则，给稀薄证据补一张能反驳自己的测试。半小时后比原稿与修订稿，学生能看见“好作业”不是天生完整，而是可被意见推动。遍历共性问题用颜色讲。先序让“根”先发声，中序让二叉搜索树说出排序，后序适合先清算孩子再处理父亲，例如求目录占用空间、释放资源、表达式求值。颜色标记访问时机后，学生重写一句总括：遍历序列的差异不来自结点移动，而来自我们把“处理”钉在递归生命周期的哪个刻度。此句允许抄进笔记，因为它凝练且可检验。项目讲评采用策展方式。墙面贴数据模型，桌面摆运行证据，走动路线按“问题是否真实—树是否必要—操作是否闭合—失败是否坦白”设置。观众不投喜欢，而投“我愿把哪条规则借到我的作业”。被借最多的规则进入班级