2021~2022学年第一学期 《数据结构B》课程教学实施方案 (2019级 财务管理专业） 计算机科学与技术系 曾爱群 一、 课程概况 【课程名称】 数据结构B 【课程性质】专业基础课 【教学对象】财务管理（智能财务）管理专业（19-1、2班），68人 教学班号：001。 【教学总学时】48学时。 【学分】3学分。 【先修课程】JAVA语言程序设计。 【后修课程】财务管理信息系统 二、 教学地位与作用及主要教学目的 数据结构是财务管理专业的一门专业理论选修课，它不仅是财务管理学科的重要选修课程，也是其他理工专业的热门选修课程。 数据结构课程是财务管理信息系统等后续课程的重要基础，同时也是程序设计技术的必备知识。通过学习该课程使学生学会分析和研究计算机进行数据加工的数据结构特性，掌握算法的复杂度分析技术，并初步具有对实际应用问题的认识和分析能力，对于实际应用问题能选择适当的数据结构和存储结构以及相应的算法编制出高效率的程序，同时为后续专业课程打下坚实基础。 数据结构课程的主要内容包括：算法分析、线性表及其应用、栈和队列、串及其应用、数组和广义表、树和二叉树及其应用、图的表示及其应用、查找方法及其分析、排序算法及其分析技术等。 三、 课程选用教材 【使用教材】 1．教材：朱战立编著．《数据结构》（JAVA语言描述）[M]. 北京:清华大学出版社,2005年11月出版 2．教材选用依据：该教材概念表述严谨，逻辑推理严密，语言精练，是计算机类一本极好的教科书、同时也是对有JAVA基础的学生来说比较好懂的一本教材。 【参考教材】 1. 王红梅．数据结构（C++版）[M]．北京：清华大学出版社，2007年7月出版。 2. 李根强主编.《数据结构》（C++版）[M]. 北京:中国水利电力出版社,2005年1月出版 3. 陈倩诒等编著.《数据结构》（C语言版）.武昌: 华中科技大学出版社,2014年7月修订版。 4. 严蔚敏，吴伟民编著.《数据结构》（C语言版）.北京: 清华大学出版社,2010年3月修订版。 四、本课程的特点及教学手段和方法 1． 课程特点： 《数据结构》以严谨的数学和JAVA语言为基础，既有抽象的数据类型的定义，又有严格的C语言类型定义和算法描述，既有直观的图形表示，又有丰富的系统描述手段和算法的分析技术，为计算机科学及计算机的应用提供坚实的理论基础和应用分析工具，是一门集理论和实践为一体的综合性课程。其特点是基础理论性强，既有逻辑思维、抽象思维的训练，又有联系实际的物理形象思维的锻炼，且所涉及的应用面较广。 2． 课程重点和难点： 重点：线性表、栈和队列、树与二叉树、图、查找、内部排序。 难点：多维数组、线索化二叉树、图的最短路径、算法的递归与非递归实现。 3． 教学方法与手段： 讲授时要遵循由浅入深的原则，对易混淆的概念加以详细说明，对每章的重点及各类不同类型的数据结构要作详细的分类介绍，并着重培养学生对实际应用问题进行形式化描述及构造算法的能力以及在此基础上进行算法分析的能力。为帮助学生理解较抽象的内容，同时力争在较少的学时数中讲授体系完整的教学内容，拟采用我室自制的完全符合教学大纲的电子教学课件。 四、 教学进度 该课程教学总学时为48学时，2.5学分。教学安排在1-13周进行，共13周，每周4学时。具体教学进度安排详见表1所示。 表1 教学进度计划表 教学内容 总学时 其 中 课堂 课内上机 实验 绪论 2 2 线性表 6 4 2 栈和队列 6 4 2 串 3 3 数组、集合与矩阵 4 2 2 递归算法 1 1 树与二叉树 8 4 4 图 6 4 2 内部排序 6 4 2 查找 4 2 2 哈希表 2 2 总计 48 32 16 五、 教学内容重点与难点及解决办法 1． 绪论（讲授：2学时） 教学重点： （1） 数据结构、逻辑结构、物理结构、数据类型、抽象数据类型、算法、算法的时间复杂度和空间复杂度及其计算。 （2） 算法的五要素、算法的书写规范。 教学难点：抽象数据类型。 解决办法：通过联系实际，举例说明抽象数据类型的内涵，如：复数的抽象性及其在C或C++中的描述与实现。 2． 线性表（讲授：4学时） 教学重点： （1） 线性表的逻辑定义机器各种存储结构的描述方法。 （2） 线性表基于各种存储结构之上的基本操作的实现方法。 教学难点：线性表的链式存储结构的实现。 解决办法：利用电子课件详细、动态地讲解链式结构的物理形式，并通过第一次实验上机练习加深对该存储结构的理解。 3． 栈和队列（讲授：4学时） 教学重点： （1） 栈和队列的逻辑结构。 （2） 栈和队列的基本操作在静态存储结构和动态存储结构上的实现方法。 教学难点：栈的链式存储结构的实现；队列的顺序存储结构（循环队列）的实现。 解决办法： ①首先结合实际例子帮助学生充分理解逻辑栈的特点，如：手枪的子弹夹等。然后利用对线性表的链式存储结构的理解进一步加深学生理解链式存储结构下的栈的实现方法。配合安排相应的验证性实验以加深理解。 ②首先结合实际例子帮助学生充分理解逻辑队列的特点，如：装羽毛球的圆筒盒子等。然后在利用电子课件形象地描述物理结构的实现。配合安排相应的验证性实验上机一次以加深理解。 4． 串（讲授：3学时） 教学重点： （1） 串的逻辑结构及其三种存储结构。 （2） 串的基本操作在静态存储结构和堆结构下的实现方法。 教学难点：串的模式匹配算法的理解与实现。 解决办法：先利用比较简单的串的顺序存储结构来讨论最简单的模式匹配算法的原理及其实现，然后再由浅入深地讨论其他效率较高的算法。可以要求一般同学仅掌握基本算法。利用课余时间组织学生讨论改进算法。 5． 数组、集合与矩阵（讲授：2学时） 教学重点： （1） 数组、集合、向量与矩阵的逻辑结构、存储结构和操作算法。 （2） 特殊矩阵和稀疏矩阵的压缩存储及其矩阵运算的实现。 教学难点：特殊矩阵和稀疏矩阵的压缩存储的理解与实现。 解决办法：制作直观而形象的电子课件，利用动画效果讲解物理存储结构的原理，然后在用JAVA语言进行物理结构的描述。 6． 递归算法（讲授1小时） 教学重点： （1） 递归的概念。 （2） 递归的执行过程。 教学难点：递归的执行过程。 解决办法：重点讲述讲述递归过程中参数值的变化和入栈出栈过程。 7． 树和二叉树（讲授：4学时） 教学重点： （3） 树的逻辑结构与基本操作。 （4） 二叉树的定义、性质与存储结构。 （5） 遍历二叉树与线索二叉树。 （6） 树的存储结构与树的遍历。 （7） 哈夫曼树及其应用。 教学难点：三种不同的遍历二叉树的递归和非递归算法。 解决办法：重点讲述一种（如中序遍历）算法的递归算法思想和非递归算法思想，并引导学生编写相应程序。然后举一反三地讲解其他两种遍历算法。配合安排验证性实验上机两次。 8． 图（讲授：4学时） 教学重点： （1） 图的定义与存储结构。 （2） 图的两种遍历策略。 （3） 无向图的边通分量及最小生成树。 （4） 拓扑排序与关键路径。 （5） 求网络中的最短路径。 教学难点：图的定义与存储结构；图的两种遍历策略。 解决办法：先重点讲述图的顺序（数组）存储方法的实现思想，然后再讲述图的邻接表法的存储方法；精讲深度优先遍历算法思想及其实现方法；课后组织学生讨论广度优先遍历算法，并引导学生编写相应程序，利用课余时间上机实现之。安排试验一次。 9． 内部排序（讲授：4学时） 教学重点： （1） 插入查找。 （2） 选择排序。 （3） 交换排序。 教学难点：各种排序算法的时间复杂度分析与比较。 解决办法：以两个较简单的排序算法为例（如：插入排序和选择排序）说明排序算法效率分析及其比较的一般方法。要求学生能根据一批数据建立几种不同的数据结构，采用不同的搜索或排序算法对这些数据进行查找或排序，并对其进行分析与比较。 10． 查找（讲授：2学时） 教学重点： （4） 顺序查找。 （5） 折半查找。 （6） 索引查找。 （7） 二叉排序树查找方法。 教学难点：二叉排序树查找方法。 解决办法：结合实际例子先讲述二叉排序树的存储结构。 11． 哈希表（讲授：2学时） 教学重点： （1） 哈希函数构造方法。 （2） 哈希函数冲解决突方法。 教学难点：哈希类的设计。 解决办法：先重点讲述哈希表项类设计思路，然后讲述哈希表类的设计思路，最后通过实例整合。 六、 教学辅导、作业、考试 关于教学辅导：每周安排一次课外答疑，答疑地点与时间另行通知。 关于作业：主要是针对每次理论课授课的内容在课堂上布置的作业，教师每次授课时将利用课堂的最后5分钟针对本次授课内容布置作业，学生在课后利用课余时间完成作业。 关于考试：本课程属考查课程。考试方式采取闭卷笔试的形式，其考试成绩占学期总成绩的60%；平时成绩（作业与上机）占学期总成绩的40%。 七、 作业的提交与教学意见反馈 1．学生可登陆学校数字化教学平台进入数据结构的网络教学界面后下载教学课件与教学大纲、观看教学视频内容、提交作业、询问疑难问题、查询教学通知、在线水平测试等。 2．学生还可通过“学宝”或网络教学平台下载教学资源，与老师进行互动，提交作业、提交实验报告等。 3．学生还可以直接将教学反馈意见以电子邮件的形式发到任课教师的私人邮箱中： 4.学生还可通过手机或QQ与任课教师联系： 任课教师QQ号： 835019705 任课教师手机号：13308461218 2021年9月2日