工程教育认证背景下数据结构课程教学实践

林 丽，薛 芳

(1.集美大学计算机工程学院；2.集美大学网络中心，福建 厦门 361021)

工程教育认证目的是构建中国工程教育的质量监控体系，深化工程教育改革，提高高校工程教育质量。工程教育认证其中一项重要的指标即是学生毕业要求的达成情况[1]。毕业要求内容包含工程知识、问题分析、设计开发解决方案、研究、使用现代工具等12个指标点。其中有8条毕业要求内容涉及“复杂工程问题”。什么是复杂工程问题？《华盛顿协议》[2-4]用如下7个特征进行刻画：(1)必须运用深入的工程原理经过分析才可能解决；(2)需求涉及多方面的技术、工程和其他因素，并可能相互有一定冲突；(3)需要通过建立合适的抽象模型才能解决，在建模过程中需要体现出创造性；(4)不是仅靠常用方法就可以完全解决的；(5)问题中涉及的因素可能没有完全包含在专业标准和规范中；(6)问题相关各方利益不完全一致；(7)具有较高的综合性，包含多个相互关联的子问题。可见,工程教育的主要目标是实现培养学生能够深入运用专业知识和工程知识的原理解决本专业领域中的复杂工程问题[5-6]。

数据结构是计算机学科中一门非常重要的专业基础课，也是人工智能、大数据技术、自然语言处理等行业应用的算法基础。数据结构不仅要求学生有扎实计算机编程语言、数学基础，也要求学生有较强分析解决问题及实践编程能力。如何把数据结构教学内容与相应工程教育认证毕业要求对应起来，达到培养学生具备解决“复杂工程问题”能力。本文提出的教学改革实践是通过对大数据技术的基础算法和数据结构课程内容做一个融合，引导学生以数据结构的理论知识解决“大数据技术的基础算法问题”。包括如何利用树结构实现机器学习的决策树算法、如何利用图结构实现社交网络问题、如何利用链表结构实现K-Means聚类算法等。数据结构课程内容与大数据技术结合的教学改革实践，不仅实现了工程教育认证要求的培养学生“解决复杂工程问题”能力的目标，也能提高教师的研究水平及教学成果，丰富教学案例。

一 课程教学改革实践

传统的数据结构教学存在偏理论、知识点抽象、不好理解等问题。很多学生掌握数据结构理论知识，但是不知道这些知识用在哪里，怎么用。更不懂得如何利用数据结构知识去解决工程问题。工程教育认证强调培养学生“解决复杂工程问题的能力”，而课程支持与否是该能力培养能否真正落实的重要依据。显然，当前的数据结构教学设计必须以培养学生解决“复杂问题”的能力为目标，统一规划课程内容，设计每个知识点对应教学案例及实验，教学目标引导学生利用数据结构知识点来解决相应的“复杂问题”。

目前，大数据技术在各个行业应用越来越广泛，而大数据技术中用到机器学习算法，如K-Means聚类算法、决策树算法都需要在合适数据结构基础实现。本文提出的教学改革方向是对数据结构的基础理论和机器学习算法做一个融合，设计相应教学案例及应用，引导学生应用数据结构理论知识去解决“复杂机器学习算法问题”。课程综合设计环节，指导学生结合行业数据，完成一个完整性的数据分析系统。课程实践结果表明，结合机器学习算法改进数据结构的教学内容不仅大大激发学生学习兴趣，提高学生学习积极性，也可以引导学生获得期望的学习成果[7]，有效协助学生成功学习。

(一)以“解决复杂问题”为目标的教学方案设计(见表1)

表1 以“解决复杂问题”为目标的数据结构教学设计方案

数据结构主要知识点包含：链表、栈和队列、字符串、树、查找、图及排序。教学内容主要包括每种数据结构的基础理论及构造方法，实验内容包含数据结构的增、删、改操作。这种教学方法测重在“教什么”，比较少讲“怎么用”、“能解决什么问题”。尤其在树、图这2个非线性结构内容中，理论知识更加复杂、抽象，如果不知道能学来“怎么用”，学习的积极性就会很差，学生取得学习成果一般。表1列举部分数据结构传统教学内容及对其改进的教学方案、实验方案。改进后的教学方案，以“解决复杂问题”为目标，课程教学内容加入如何用链表结构解决机器学习中的“聚类算法”问题、如何用树结构解决代码查重问题、如何利用图结构设计知识图谱问题。表2罗列每个教学设计对应的“复杂工程问题”7个特征。通过这些“复杂工程问题”，学生不仅学会了数据结构知识，还会用数据结构理论解决复杂问题。教学设计中选择的代码查重、知识图谱作为教学实践案例，贴近行业应用，不仅能激励学生主动去探索相关算法理论知识，而且综合培养学生编程实践能力、数据结构模型构建能力、数据表达及分析能力等，实现培养学生“解决复杂工程问题”的目标，协助学生获取最大的学习成果。

表2 教学设计对应的“复杂工程问题”特征

(二)课程教学流程

表1设计的教学内容，会导致理论学时不够的问题。可以先引导学生配合线上慕课视频提前预习数据结构知识点，再在课堂中着重介绍每个知识点如何应用在机器学习算法等复杂问题中，同时穿插数据结构知识点理论讲解，达到复习课程理论知识目标。最后结合编程实验，巩固课程知识点。以“图”这章内容为例，设计教学具体环节，考虑学生水平及兴趣不一致，课程实验可以设置不同难度级别。水平一般的同学主要完成数据结构基础实验(结合在线编程平台实现)；水平好的同学可以继续完成机器学习算法设计。不同水平的同学都能掌握数据结构基础理论，也能掌握数据结构知识怎么用来解决机器学习算法问题。数据结构课程结束后，还有一个对应的综合设计实践，这个阶段就可以引导所有同学把课堂学的所有理论知识、编程方法，结合一个应用项目，做一个综合系统，达到培养学生利用数据结构及其他课程如高等数学解决“复杂工程问题”的学习目标。

二 课程实践环节改革

(一)课程综合实践

课程综合实践是培养实践能力、解决复杂工程问题能力过程中重要的实践教学环节。但是数据结构综合实践题目存在比较老旧、单一问题。如图书管理系统、银行管理系统、校园导航等。这些题目不仅在网络上有大量解题方案，而且题目没有创新性，与应用结合弱。课程设计完成后的程序，很难有学习成果，导致学生编程的积极性弱，也不满足目前工程认证教育强调的“解决复杂工程问题”的需求。

按照表1的课程教学内容，学生不仅掌握数据结构的理论知识，还要掌握部分大数据算法基础。综合实践主题则以“会用”数据结构知识解决“机器学习算法问题”为方向，结合行业数据，设计一个行业应用。这个实践阶段引导学生主动去分析数据、研究数据结构模型、设计算法、实现可视化展示。表4所示为综合实践主题内容及其对应的数据结构课程知识点。所有的实践主题需要使用链表、栈、树、图等多个知识点解决机器学习的算法问题。

表4 实践主题和涉及的数据结构知识点

表4所示的综合实践主题并不是枯燥的算法实现，而是结合行业数据实现某个大数据方面的行业应用。这些主题不仅可以激发学生学习兴趣，主动研究算法原理，实现系统设计，同时每个主题涉及数据结构、高等数学、汇编原理等多个课程知识，实现了多学科的融合。

(二)课程实践开发流程

实践开发流程共分为8个步骤，表5罗列的是实践开发环节具体内容，每个环节培养的学生能力，每个环节对应工程教育认证毕业要求的指标点。

表5 实践开发环节对应的工程认证教育指标点

续表5 实践开发环节对应的工程认证教育指标点

(三)课程设计成果

课程设计一般只有一周时间，比较短。课程设计周期结束后，对于完成质量好的课设作品，教师引导学生在寒假或暑假时间，继续完善、优化算法，课程设计作品可以通过发表学术论文、发布软件产品、参加大学生创业创新设计比赛等方式作为学生实践成果。对于完成质量一般学生，引导学生在其他程序设计课程中，用其他开发工具继续完善算法，作为课程设计实践一个阶段性成果。

工程认证教育实施的目标是学生通过专业教育过程最后所取得的学习成果，我们想让学生取得的学习成果是什么？为什么要让学生取得这样的学习成果？如何有效地帮助学生取得这些学习成果？不同学生能达到学习成果不一样。表6列举部分数据结构实践项目能帮助学生学取得的学习成果。

表6 数据结构实践项目对应的学习成果

为了让学生有效取得课程的学习成果，教师可以根据学生完成质量，设计适应不同学生的学习成果。这里分成初阶和高阶学习成果。初阶学习成果主要能综合运用数据结构的知识点解决实践项目的问题，学习整个系统设计、建模、开发、调试过程。高阶学习成果，针对质量高的作品，引导学生学习继续优化算法，自学其他工具完善系统，做更多数据测试实验。优化后的算法可以发表在学术期刊上，转化为学术成果。也可以做成软件成品，在其他课程、毕业设计继续研究实践。高阶的学习成果，需要教师与学生之间建立一个紧密联系，课后继续交流课程知识。

三 课程评价及持续改进

(一)学生对数据结构课程评价

本次教改方案面向本校网络1911、1912班级共55位同学做教学改革实践。课程结束后，通过问卷调查方式了解学生对本次教学方案的评价。

1.学生对课程教学内容及课程设计内容的满意度调查结果。调查结果如图1所示。学生对课堂教学效果和课程设计内容评价非常满意分别有50.9%、52.7%。评价满意分别有47.2%、45.5%。总体满意度高达98%。可见，学生对“解决复杂问题”为目标的教学改革内容的认可。

图1 课程满意度调查结果

2.课程实践主题的兴趣度调查结果。图2是对课程实践主题内容的问卷调查结果。学生可以选择多个感兴趣的主题。从调查结果看：“代码查重”“知识图谱”和“网页爬取”这3个主题选择人数超一半，虽然这些题目难度较大，但是题目贴近行业需求，所以学生更有兴趣去解决分析此类问题。“K-Means聚类算法”选择人数较少，该题目偏理论研究，学生兴趣度较低。在后续的实践教学中，教师可以结合行业数据去设计，比如聚类算法在客户信息管理数据、校园卡消费行为数据的应用等。“倒排索引表设计”题目老旧，不够新颖，所以学生选择人数少，兴趣度低。可见，学生对实践主题的兴趣度，不是看主题难度，而是看实践的主题和行业热点间关联程度。所以，以“解决具体行业问题”为目标的实践主题设计，更能带动学生主动学习研究的积极性。

图2 课程实践主题兴趣度调查结果

3.工程教育认证毕业要求的达成度调查结果。图3为学生对照工程教育认证毕业的若干要求，评估自己获取的学习成果。其中，“问题分析”“使用现代工具”“工程知识”及“终身学习”这4个能力选择人数较多，而“工程与社会”选择人数较少。这个能力要求查学生“能够基于工程相关背景知识进行合理分析，评价专业工程实践和复杂工程问题解决方案对社会、健康、安全、法律以及文化的影响，并理解应承担的责任”。而目前的教学改革方案和文科类课程结合较少，这块能力的培养可以作为课程改革的另一个方向，如结合思政课程、体育课程、法律课程等设计相应教学案例及课程实践去改进。从调查结果看，目前数据结构教学实践与改革方法实现了培养学生解决“复杂工程问题”的教学目标，达到了培养学生“工程知识”“问题分析”“设计/开发解决方案”“研究”“使用现代工具”“终身学习”能力。

图3 工程教育认证毕业要求的达成度调查结果

(二)持续改进

引入“复杂工程问题”的教学设计在教学实践中存在的问题:

1.机器学习算法较难理解，基础薄弱同学学习困难。

2.面向行业数据，如代码查重中各种各样的C语言代码，如何建语法树；校园卡数据中大量文本类型数据怎么表示，即数据如何预处理问题。

3.算法可以理解，动手编程实现困难或实现效果不理想。

4.算法优化，需要阅读大量文献资料等，学习时间不够问题。

针对上述问题改进方向：

关于K-Means聚类算法、代码查重及其他机器学习算法，学生自学的困难比较大，教师要在课堂引导授课，如1.2节中关于知识图谱和课程内容做结合，在课堂教学中要授课指导，尤其是紧紧抓住怎么用数据结构知识点去解决这个问题。教学环节在课前、课中、课后都要设计授课内容辅助学生学习。

经过两轮教学实践，发现行业数据的预处理、算法实现方面，学生问题较多，课堂教学还需要多展示怎么预处理、前一届学生数据预处理问题、这一届要怎么优化改进。从往届学生的代码设计总结问题，为新一届学生讲解问题解决方案，避免一些常规错误，有更多时间研究算法及算法优化问题。

关于教学持续改进方面，下面分成两个内容改进。

1.课堂教学的持续改进。教师根据历届学生学习效果，递推式改进教学方案。如聚类算法、关联规则算法、知识图谱，可以结合更多行业数据设计分析，优化改进算法，实现算法迭代更新。教师也可以观察授课同学的学习能力，设计不同难度级别的教学主题，如加入更复杂机器学习算法、图论内容去实现某些功能。这些教学主题紧扣数据结构课程内容，同时引导学生不同维度思考。经过一轮教学实践，积累学生学习数据、学习问题，下一轮教学中更会引导学生如何去实践完成相应问题，教学过程可以提高教学案例难度，引导学生做更复杂工程问题。

2.实践教学的持续改进。课程设计内容每一年都要变化，但是经常变化课设题目不利于一个主题的深入研究。所以课设题目可以大方向不变，但是功能、处理数据做调整，引导新一届学生做更复杂的开发设计。比如2018级学生实现K-Means聚类在鸢尾花iris数据应用。这个是难度最低的聚类算法应用。教师根据本届学生做的效果，整理学生课程设计存在问题，继续引导2019级学生实现K-Means聚类算法在其他行业数据如校园卡消费数据、超市用户消费数据的应用。虽然做的是同一个算法，但处理数据类型更复杂。这个过程引导学生去主动研究K-Means优化版算法解决方案，设计的算法复杂度也在加深；整个教学实践过程，都在引导教师、学生共同去解决“复杂工程问题”。算法优化后的成果可以作为师生间共同研究成果。

培养学生解决“复杂工程问题”的能力是工程教育专业认证背景下计算机类专业课程的重要任务之一。本文以大数据技术的基础算法作为课程的“复杂问题”，设计教学案例及课程实践主题来引导学生以数据结构的理论知识解决聚类算法、关联规则、知识图谱等“复杂工程问题”。教学实践结果表明，融合大数据基础算法的数据结构课程教学改革，有效促进了学生解决专业领域内复杂工程问题能力的提升。