2025-2026学年软考软件设计师教学视频

2025-2026学年软考软件设计师教学视频科目授课时间节次--年—月—日（星期——）第—节指导教师授课班级、授课课时授课题目（包括教材及章节名称）教学内容一、教学内容本教学内容对应《软件设计师教程（第5版）》第二章“数据结构与算法”，主要涵盖线性表（顺序表、链表、栈、队列）的定义、存储结构及操作；树与树结构（二叉树、二叉搜索树、平衡二叉树、哈夫曼树）的特性、遍历及应用；图的基本概念、存储结构（邻接矩阵、邻接表）及遍历算法（DFS、BFS）；常用算法（排序、查找、递归、动态规划）的设计思想与时间复杂度分析；算法复杂度（时间复杂度、空间复杂度）的计算方法。核心素养目标分析二、核心素养目标分析通过数据结构与算法的学习，培养学生的计算思维，能够抽象问题本质，设计合理的存储结构与算法；发展数据意识，理解数据的组织方式及其对算法效率的影响；强化模型意识，运用树、图等模型解决实际问题；提升应用意识，将算法思想应用于软件开发实践；激发创新意识，优化算法设计，提升问题解决效率。学情分析三、学情分析本课程面向有一定编程基础但数据结构系统学习不足的软件设计师备考学生。知识层面，学生普遍掌握基本编程语法，但对线性表、树、图等复杂数据结构的存储特性与操作原理理解模糊，尤其在算法时间复杂度分析上存在普遍困难。能力方面，学生具备基础编码能力，但面对复杂问题时缺乏抽象建模能力，难以将实际问题转化为数据结构模型，算法设计思路单一，优化意识薄弱。素质上，学生逻辑思维参差不齐，部分习惯死记硬背代码而非理解底层原理，导致知识迁移能力差。行为习惯上，学生更关注代码实现而非算法设计思想，对理论推导存在畏难情绪，直接影响对动态规划、递归等核心算法的深度掌握，需加强案例教学与可视化演示。教学方法与手段教学方法：1.讲授法结合动态演示，重点解析线性表、树图存储结构及操作原理；2.讨论法引导算法设计思路，针对排序、查找等典型问题进行方案优化分析；3.实验法依托在线编程平台，强化递归、动态规划等算法的编码实践。

教学手段：1.动画演示数据结构操作过程，可视化呈现栈、队列等抽象概念；2.利用在线评测系统实时反馈算法复杂度分析结果；3.构建思维导图工具梳理树、图等知识点间的逻辑关联。教学过程1.导入（约5分钟）：

激发兴趣：展示社交网络好友关系图，提问“如何快速找到所有好友的二级好友？”，引出图的遍历问题。

回顾旧知：复习栈的LIFO特性及递归调用原理，关联二叉树遍历中的栈操作。

2.新课呈现（约35分钟）：

讲解新知：

（1）二叉树遍历：定义前序、中序、后序遍历的访问顺序（根-左-右、左-根-右、左-右-根），对比递归与迭代实现差异。

（2）图遍历：解释邻接矩阵/表存储结构，说明DFS（深度优先）和BFS（广度优先）的搜索策略，强调时间复杂度O(V+E)。

举例说明：

（1）二叉树案例：绘制{1,2,3,null,4}结构，演示前序遍历结果[1,2,4,3]的递归过程。

（2）图案例：用邻接矩阵表示4节点无向图，展示从节点0开始的DFS路径0→1→3→2和BFS层级序列0,1,2,3。

互动探究：

（1）分组讨论：若二叉树为满二叉树，比较三种遍历的递归深度与栈空间消耗。

（2）白板模拟：学生分组用粉笔模拟图的DFS/BFS路径，教师纠正遍历顺序错误。

3.巩固练习（约20分钟）：

学生活动：

（1）基础任务：在线编程平台实现二叉树中序遍历（迭代法），输入[1,null,2,3]验证输出[1,3,2]。

（2）进阶任务：对给定邻接表{0:[1,2],1:[2],2:[0,3]}，编写BFS算法并输出最短路径0→3。

教师指导：

（1）巡视代码，重点检查递归终止条件和队列操作逻辑。

（2）针对栈溢出问题，提示学生改用迭代法处理深度过大的树。

（3）展示BFS最优性证明，强化算法理论理解。

（1）归纳二叉树遍历的“访问顺序差异”与图遍历的“策略选择关键点”。

（2）预告下节课内容：最小生成树算法（Prim/Kruskal），关联图的连通性应用。学生学习效果学生通过本章节学习，在数据结构与算法核心知识层面取得系统性提升。首先，在数据结构认知上，学生能够准确描述线性表（顺序表、链表）的存储结构差异，理解栈的LIFO特性与队列的FIFO原理，并能分析不同场景下的适用性。对于树结构，学生掌握二叉树的三种遍历（前序、中序、后序）的递归与迭代实现逻辑，能独立绘制满二叉树、完全二叉树的形态，并解释平衡二叉树的旋转调整规则。图结构方面，学生可区分邻接矩阵与邻接表的存储优劣，熟练应用DFS和BFS算法完成图的遍历，并能分析时间复杂度O(V+E)的实际意义。

在算法设计能力上，学生能够运用分治思想实现归并排序、快速排序，理解动态规划在斐波那契数列计算中的状态转移方程，掌握递归与迭代的转换技巧。针对复杂度分析，学生可独立推导算法的时间复杂度（如冒泡排序O(n²)、二分查找O(logn)）和空间复杂度，并比较不同算法的效率差异。例如，在解决"社交网络好友推荐"问题时，学生能主动选择BFS算法实现最短路径查找，而非盲目使用DFS。

在问题解决能力上，学生具备将实际问题抽象为数据结构模型的能力。如将"表达式求值"问题转化为栈操作，将"文件系统目录结构"建模为树结构，将"地铁线路规划"抽象为图的最短路径问题。学生能够根据问题特性选择合适的数据结构，例如优先级队列处理任务调度，哈希表实现高效查找。

在编程实践层面，学生通过在线评测系统完成二叉树遍历、图遍历等编码任务，代码规范性与健壮性显著提升。例如，在实现中序遍历迭代算法时，学生能正确处理空树节点，避免栈溢出异常；在BFS算法中，能准确标记访问节点，防止重复遍历。

在思维素养方面，学生的计算思维得到强化：面对"迷宫寻路"问题时，能先分析图结构特性再设计算法；在优化"0-1背包问题"时，能通过空间压缩技术降低复杂度。数据意识明显增强，如通过对比顺序表与链表的插入效率，理解数据组织对算法性能的影响。模型应用能力提升，能将二叉搜索树特性应用于高效查找场景，将哈夫曼树原理应用于数据压缩设计。

在软考应试能力上，学生能够快速识别选择题中的数据结构概念辨析（如栈与队列操作差异），简答题中清晰描述算法步骤（如Prim算法构建最小生成树），案例分析题中综合运用树、图知识解决实际问题（如设计数据库索引结构）。学生普遍反映对算法复杂度分析题的解题信心增强，能准确识别时间复杂度中的常数因子与渐进阶数。

此外，学生的学习行为发生积极转变：从被动接受理论转向主动探究算法原理，如自发比较递归与迭代实现的优劣；从死记硬背代码转向理解底层逻辑，如通过可视化工具观察递归调用栈的变化；从孤立学习知识点转向构建知识网络，如将排序算法与分治思想、动态规划建立关联。

综上，学生通过本章节学习，不仅掌握了数据结构与算法的核心知识，更形成了系统的问题解决方法论，为后续学习高级算法、参与实际软件开发奠定了坚实基础。课后作业1.题目：给定二叉树结构{1,2,3,null,4}，写出中序遍历的迭代实现结果。

答案：[1,3,2]

2.题目：无向图邻接矩阵为[[0,1,1],[1,0,1],[1,1,0]]，从节点0开始DFS遍历，写出遍历序列。

答案：[0,1,2]

3.题目：分析快速排序算法在最好情况下的时间复杂度及原因。

答案：O(nlogn)，每次划分将序列均匀分为两部分。

4.题目：使用栈模拟表达式"5-3+2"的计算过程，写出每一步栈的状态。

答案：初始栈空，读5入栈，读-入栈，读3出栈计算5-3=2入栈，读+入栈，读2出栈计算2+2=4入栈，结果为4。

5.题目：给定哈夫曼树编码表：A(0),B(10),C(110)，编码字符串"010110"对应的原文是什么？

答案：ABBC教学评价课堂评价：通过提问检测学生对数据结构核心概念的掌握，如“栈的LIFO特性在表达式求值中的应用”“邻接矩阵与邻接表的存储空间复杂度差异”，观察学生能否准确回答并解释原理。互动探究环节，观察学生分组模拟图的DFS/BFS时，是否能正确遍历路径并说明策略选择依据。课堂小测设计二叉树遍历序列转换题（如已知前序、中序求后序），统计正确率，针对遍历顺序混淆问题现场演示递归调用栈变化。

作业评价：批改时重点检查算法实现的逻辑正确性，如二叉树中序遍历迭代法是否正