ABSTRACT

This paper analyzed the supporting effect of the practical session of data structure course on the graduation requirements of engineering education certification, proposed an online practice mode of ACM-like model. It also constructed a data structure practice platform based on ACM/ICPC online evaluation technology and a data structure-oriented practice topic database. The practice process is illustrated by the case.

Keywords:Engineering Education Certification, Graduation Requirements, Data Structure, Practical Session, Practice Platform

面向工程教育认证的“数据结构”实践课程强化建设

冯向阳，王梅，黄秋波

东华大学，计算机科学与技术学院，上海

收稿日期：2018年12月30日；录用日期：2019年1月8日；发布日期：2019年1月15日

摘 要

分析数据结构课程实践环节对工程教育认证毕业要求的支撑作用，提出类ACM模式的在线实践方式，构建基于ACM/ICPC在线评测技术的数据结构实践平台以及面向数据结构的实践题目库，并以案例说明实践过程。

关键词 :工程教育认证，毕业要求，数据结构，实践环节，实践平台

Copyright © 2019 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

工程教育认证是国际通行的工程教育质量保证制度，也是实现工程教育国际互认和工程师资格国际互认的重要基础 [1] 。2016年6月2日，我国成为《华盛顿协议》的正式成员，标志着我国工程教育认证的结果将得到其他成员认可，通过认证专业的毕业生在相关国家申请工程师执业资格时，也将享有与本国毕业生同等待遇。因此，国内各大高校均积极申报工程专业认证。据中国工程教育专业认证协会统计，截止2017年底，全国共有198所高校的846个工科专业通过认证。上述工作的开展，不仅极大的提高了我国毕业生的国际竞争力、专业认证的先进理念，更有力地推动了我国工程教育专业的教学改革。

以成果为导向、以学生为中心以及持续改进的教学机制是我国工程教育认证主要倡导的基本理念。工程教育认证标准对工程类本科毕业生提出了12条毕业要求，包括工程知识、问题分析、研究、使用现代工具、工程与社会、环境和可持续发展、职业规范、个人和团队、沟通、项目管理以及终身学习等 [2] 。在实际的教学环节中，如何建设课程内容、改进教学过程，培养学生的抽象思维能力，提高计算机应用能力是计算机工程教育教学所需考虑的重要问题。

“数据结构”作为计算机学科实践性较强的专业基础必修课，其教学目标是要求学生掌握各种常用数据结构的定义、特点以及基于这些数据结构的基本算法，具备一定的数据抽象能力，学会分析算法复杂度、比较算法性能和优化算法，提高应用计算机技术解决实际问题的能力。由此可见，通过该课程教学目标的实现，将对学生达到工程认证毕业要求，如具备解决复杂工程问题的所具有的扎实的工程知识、问题分析能力、深度研究能力以及终身自主学习习惯等起到重要的支撑作用。

虽然工程知识和基础理论可通过课堂教学传授获得，但是如何分析实际问题，通过数据抽象建立数学模型，选择合适的数据结构转换为计算机能够处理的问题形式等抽象思维过程很难在传统的课堂教学模式中培养出来。学生只有通过针对性的系统化实践训练，方能真正培养和提高抽象思维能力，理解和掌握课程的内容，培养主动和深入学习的习惯，提高分析和解决问题的能力，以满足专业认证对学生素质和能力的要求。

2. 数据结构实践教学实践的问题

数据结构理论知识点多，涉及各种常用数据结构的定义、特点以及基于这些基本数据结构的基本算法等。由于数据结构主要是基于抽象数据类型(Abstract Data Type, ADT)进行描述和实现 [3] ，要求学生具有一定的逻辑推导和抽象思维能力 [4] 。传统的教学模式主要通过教师的课堂讲授，使用伪代码来描述数据结构及其算法实现，教学内容比较抽象。学生被动地接收理论知识，普遍感觉课程内容过于抽象，对抽象数据类型的理解比较肤浅，不知道如何利用ADT进行相关算法的设计，无法满足工程认证教育的基本要求。

作为实践性较强的专业基础必修课程，实践教学环节是数据结构教学的重要组成部分。面向工程教育认证，课程的实践教学应注重培养学生的抽象思维能力。基于抽象数据类型，通过选择合适的数据结构，建立相应的数学模型，提高算法设计能力和动手实践能力。

由于课堂教学任务量大，造成实践课时严重不足，在课后学生也很少有渠道获得系统练习的机会。而有限的实践教学过于注重基本理论的验证性实验，实验题目比较陈旧，多是围绕消化课堂内容而设计的一些碎片式的题目，缺乏系统化的实践题目设计，尤其缺乏对数据结构的核心内容，即抽象数据类型(Abstract Data Type, ADT)的系统性训练。对于学生而言，由于没有针对性的实践题目，几乎所有的课堂讲授的基本数据结构的ADT依然停留在伪代码的抽象阶段，没有实现将算法从伪代码到实际代码的真正转换。由于算法设计能力并未从实践环节中得到实质性的锻炼和提高，学生普遍对实践教学的积极性不高，缺乏学习能动性，实践教学效果不好。这种状况显然不利于学生分析和解决问题能力的培养。

而要真正领悟和掌握抽象思维能力，不仅需要从理论上掌握基本的知识点，更需要通过实践环节对学生的抽象思维能力进行系统的训练，提高算法设计能力，掌握各种数据结构和算法的意义和精髓，将具体的数据结构和相关算法应用到具体的项目中去 [5] 。为了提高教学质量，满足工程认证教育的要求，亟需通过实践课程建设，特别是在实践教学环境探索新的教学模式，以真正实现以成果为导向，以学生为中心。

3. 实践课程建设方案

在实践课程建设方面，将“类ACM模式”引入“数据结构”的实践教学中。众所周知，ACM国际大学生程序设计竞赛(简称ACM/ICPC)是由国际计算机界历史最悠久、最具权威性的计算机组织ACM (Association for Computer Machinery)学会主办，是世界上公认的规模最大、水平最高、最为公平的国际大学生程序设计竞赛，其目的在于让大学生运用计算机知识来充分展示自己在压力情况下，分析和解决问题的能力。国内很多高校已经尝试将ACM/ICPC训练模式引入数据结构的实践教学，用以刺激学生的挑战欲望，鼓励学生多动手、多动脑、多实践，进而提高学生学习的主观能动性，达到提高教学质量的最终目的。

ACM是以竞赛为目的，针对的是少数具有特别突出的算法设计能力的学生；数据结构的实践课程是以教学为目的，针对的是普通的计算机专业的本科生。由于二者的目的和针对对象的不同，不能简单地照搬ACM的训练模式，必须遵循本科教学以及工程认证教育的规律，进行数据结构的实践课程建设。

1) 基于ACM/ICPC在线评测技术的数据结构实训平台：学院已有的PCOJ平台针对ACM训练和竞赛设计，没有班级管理、课程管理等功能，不适合本科实践教学使用。为此，自主开发了用于数据结构实践教学的实践平台(Online Judge, OJ)。该平台的用户分为3种角色：管理员、教师、学生。管理员的功能包括教师注册、题目维护等；教师的功能包括学生批量导入、训练试题库与标准答案维护、学生提交代码查看及批改等功能；学生的功能包括题目浏览、代码提交等功能。为了防止少数学生的懒惰行为，平台提供对提交程序的查重功能。在规定时间内，学生可以多次提交代码进行在线测评。系统也会及时反馈所提交的算法是否正确。教师也可以将不合格的代码退回，要求学生重做。由于实践教学在网络上进行，不受时间和空间的限制，无形之中解决了实践课程教学课时不足的问题。

2) 面向数据结构的实践题目库：虽然ACM竞赛题库中有大量应用数据结构知识点的题目，但由于起点较高，并不适合于大多数初次接触数据结构的本科学生。因此，基于数据结构教学大纲，适应工程认证教育的要求，设计了系统化的数据结构实践题目。这些题目均以ACM训练题目的形式添加到平台的实训题目库中。目前，试题库已包含了100余道题目，7个专题试题集系统化的实践内容包括：基本数据结构(线性表、链表、栈、队列、二叉树、最优树、图)的完整ADT设计、建立在ADT基础上的数据结构应用算法题目以及查找和内部排序方面的算法设计题目等。

3) 面向对象的数据结构描述：由于每种基本的数据结构都有相应的存储结构，如二叉树的存储结构为二叉链表，建立对应的抽象数据类型(ADT)。由于二叉树的ADT具有自身的属性和基本操作，这实际上和面向对象语言中类的特点是一致的。同时，C++语言中的模板类可以用来描述ADT中元素类型不确定的因素。因此，面向对象的程序设计语言(如C++语言)更适用于描述数据结构。大部分学生虽然选修过C++的相关课程，但普遍缺乏实战训练，对模板类和指针的掌握比较薄弱，更不说将其应用于数据结构的描述上。因此，在OJ上部署的所有实践题目，均要求学生使用C++语言，基于模板类进行基本数据结构对应的模板类和应用算法的设计和实现。

相对于传统的实践教学，该模式具有以下几方面的优势：1) 实践教学在网络上进行，不受时间和空间的限制。教师可以通过在线评测系统由浅入深的布置系统的实验内容，为帮助学生掌握扎实的数据结构工程知识，为进一步应用数据结构进行抽象分析提供了可能。学生可以根据自己的情况，选择合适的时间完成实验题目。学生完成编程后，通过提交程序代码可以立刻得到评测结果。学生根据评测结果查阅资料、分析与解决问题，学生的自主学习能力得到进一步锻炼。2) 在数据结构课程学习目标达成中，最大的困难点是学生不善于对现实世界中问题所涉及到的数据进行分析，通过数据结构来抽象表达需要求解问题中的客观事物，不易掌握数据之间的关系，缺乏系统解决问题的方法。将ACM模式应用于数据结构的实验教学中，学生通过完成量身定做的系统化的数据结构实验题目，建立一组数据对象及数据关系的定义，在其上完成基本操作的实现，即实现各种数据结构完整的抽象数据类型，对学生的抽象思维能力和应用实践能力起到良好的训练和提升。3) 有利于创造学生之间良好的学术交流氛围。在完成题目的过程中，学生和学生、学生和老师之间会自主地进行算法和程序的交流讨论，有利于创造良好的学习交流氛围，提升学生的交流沟通能力。

4. 课程实践案例

以二叉树为例，实践平台的实践题目数据库中共设计了33道实训题目，其中19题为建立完善的二叉树抽象数据类型，14题为二叉树抽象数据类型的应用。如表1所示，上述题目可对应于四个阶段：阶段1，建立二叉树的二叉链表存储结构；阶段2：在二叉树的二叉链表存储结构之上，完成各种遍历操作，包括前序、中序、后序的递归遍历算法、非递归算法以及层次算法，完成后将其加入到二叉树的ADT基本操作集中。阶段3：在存储结构及各种遍历算法的基础上，实现ADT的其它基本操作，包括统计节点个数，查找节点、删除节点，查找父节点等，完成后将其加入到二叉树的ADT基本操作集中。阶段4：通过完成的二叉树抽象数据类型，完成简单的应用算法设计。

表1. 二叉树实践题目安排(部分)

对于实践平台上的每一道题目，其题目信息主要包含问题描述、基本操作参考函数原型、输入说明、输出说明、输入范例以及输出范例，为学生提供了规范化的说明及良好的注释。表2给出了二叉树的层次遍历算法题目实例。

表2. 二叉树层次遍历算法题目实例

教师在实践平台上布置完题目后，学生根据课堂教学内容，完成实践平台上相应的题目；老师登录实践平台查看学生的完成进度与完成质量；安排课内实验课，根据同学的完成情况进行针对性的问题解答。此时，由于学生已经完成相应的内容，同时老师已经对学生的完成情况进行了解，因此教师和学生在课内实践的互动中，更有针对性，效率更高。在实验内容的设置上，根据内容深浅，由浅到深逐层深入，一道实践题目对应ADT的基本操作，随着实践进度的推进，逐渐完善，由学生自己最终完成完整的ADT。在此基础上，再通过具体的应用，体会如何使用ADT抽象数据类型解决实际问题，提高学生运用抽象分析能力和理论知识解决实际问题的能力，同时为下一步的数据结构课程设计打下了坚定的基础。

5. 结语

以工程认证毕业要求为主导，针对数据结构课程目标，通过建设系统化的数据结构实训平台和实训题库，利用面向对象的方法和手段设计有效的数据结构，进行数据抽象、设计抽象数据类型，注重算法设计能力的提高和解题思维能力的训练，使学生解决复杂工程问题的能力得以提高。

基金项目

2017年度上海市教委本科重点课程建设项目。

文章引用

冯向阳,王 梅,黄秋波. 面向工程教育认证的“数据结构”实践课程强化建设
Construction of Practical Course of “Data Structure” for Engineering Education Certification[J]. 教育进展, 2019, 09(01): 38-42. https://doi.org/10.12677/AE.2019.91009

参考文献