基于工程认证的数据结构与算法课程教学研究

张冰涛 王小鹏 王履程

摘 要：数据结构与算法课程作为计算机与信息类专业的基础课程，传统教学过程中存在重视理论教学，忽视实践教学的问题。为适应工程认证要求，对数据结构与算法课程实践教学环节进行研究与改革。将原有以理论教学为主的教学方式，转换为以理论教学为基础、实践教学为核心的教学体系，从而锻炼和培养学生的工程实践能力。围绕实践教学环节，以兰州交通大学服务大交通行业的特色为切入点，结合数据结构与算法课程特点，构建6～8个科学可行的实践教学案例，填补现阶段数据结构与算法课程实践教学环节无标准化、科学化、系统化教学案例的空白。

关键词：课程教学;工程教育;实践教学;教学案例

DOI：10. 11907/rjdk. 181674

中图分类号：G434文献标识码：A文章编号：1672-7800（2019）001-0201-04

Abstract： The course of Data Structure and Algorithm is a basic course for computer and information majors. There is the problem of focusing on theory teaching and neglecting practice teaching in traditional teaching process. In order to meet the requirements of engineering certification， the practice and teaching part of this course are studied and reformed. The original teaching method， which is based on theory teaching， is converted into a teaching system based on theoretical teaching as a？foundation？and practice teaching as the core to train and temperi students' engineering practical ability. In practical teaching， we take the characteristics of Lanzhou JiaoTong University's major transportation trade as the breakthrough point combined with the characteristics of data structure and algorithm course to construct 6 to 8 scientific and feasible practice teaching cases which fill the blank of standardized， scientific and systematized teaching cases for the practice teaching part.

Key Words： curriculum instruction; engineering certification; practice teaching; teaching cases

0 引言

工程教育專业认证作为工程师资格国际互认的标准，以由美、英等6国在1989年发起并签署的《华盛顿协议》[1]为基础。以2006年中华人民共和国教育部发布的《关于成立教育部工程教育认证专家委员会的通知》为起点，我国开展工程教育认证[2]工作已有十余年时间。2013年我国成为《华盛顿协议》预备成员国。2016年6月，我国正式加入《华盛顿协议》[3]，成为该协议第十八个正式成员国，标志着我国工程教育专业认证工作获得了里程碑式的突破。由于工程教学认证在国际人才市场上具有很高的含金量，并且为工科院校学生培养提供了依据，目前我国多数工科院校都在积极开展工程专业认证工作。

数据结构与算法课程[4-6]是程序设计的基础，在计算机、软件工程、物联网等专业的学习中占有重要地位。完成程序设计不仅需要掌握编程语言 （如C语言[7]、C++[8]、C#[9]、Java[10]等），还需了解数据间的组织关系、数据物理结构等。通过对数据结构与算法课程的学习，可以培养学生利用计算机处理数据的能力。此外，数据结构与算法课程作为后续编译原理[11]、操作系统[12]、数据库系统[13]等课程的前修课程，对知识的贯穿起到承前启后的作用。为了适应工程教育认证的要求，兰州交通大学对该课程教学环节进行改革。数据结构与算法课程常被作为报考计算机相关专业硕士研究生或者博士研究生的初试专业课程[14]。为了契合应试教育需要，传统教学过程中存在重视理论环节、忽视实践环节的问题，然而课程相关知识被广泛应用于不同的研究和实践领域，如无线传感器网络[15-18]、入侵检测[19-20]等，因此课程改革存在必要性和紧迫性。

在当前工程教育专业认证体系背景下，工程教育通用认证标准要求计算机专业学生能够运用所学专业知识建立抽象模型以解决复杂工程问题，并持续改进、优化解决方案。为更好地满足工程教育、课程体系与学生毕业要求，本文对本课程改革进行探索，首先以坚实理论为基础，充分发掘本课程涉及的4方面基本内容：纯集合数据结构、线性数据结构、树形数据结构、图形（网状）数据结构。结合工程认证要求构建6～8个实践教学案例，应用于实践教学以达到锻炼学生工程实践能力的目的，从而培养学生在实践过程中解决复杂工程问题的能力，最终为工业界培养出符合工程认证要求的合格人才。

1 课程与工程认证标准的差距

由工程教育认证通用标准和补充标准可知，工程教育认证以社会需求为导向，以学生为核心，其实质是以社会需求为基础，倒推毕业要求，以达到培养合格工程人才的目标。通用标准各部分之间的关系如图1所示。然而，目前我国高校本科教学往往以应试教育为导向，以专业骨干教师为核心开展教学工作，与工程教育以社会需求为导向、以学生为核心的理念相背离，导致工程人才培养与社会需求脱节。

对于数据结构与算法课程而言，传统上按照线性结构、树形结构、图形结构为顺序主线，逐章进行理论知识讲解，虽然满足了应试教育的要求，取得了一定效果，但与工程教育专业认证导向和核心要求还存在一定差距。其主要问题表现在：①教学方法方面，以理论教学为重点，忽视实践教学环节，甚至缺失实践教学环节，从而严重限制了学生工程实践能力的培养，以至于学生在毕业时很难达到工程教育认证要求的毕业条件，不能满足社会需求;②考核评价方面，以期末考试分数为主，平时表现为辅，虽然能在一定程度上衡量学生对知识的掌握程度，但是该考核评价体系存在局限性，不能有效评价学生实际工程应用能力，从而无法满足社会对工程人才的实际需求。

2 基于工程认证的数据结构与算法课程改革

针对目前数据结构与算法课程存在的问题，本文提出以实践教学案例为支撑，满足社会需求为导向，基于反向课程设计为基本原理，面向社会需求为起点，设计数据结构与算法课程实践教学案例，完善课程体系，支撑学生毕业指标点。毕业指标点主要包括：①针对计算机专业中存在的复杂工程问题，进行抽象分析，建立或选择合适的数学模型;②运用计算机技术相关理论对复杂工程问题的解决方案进行研究分析并改进;③能够运用专业理论和知识正确分析、评价工程中存在的复杂工程问题，提出相应的预防措施或解决方案，并制定合理课程评价体系。

由于篇幅限制，本文仅列出具有代表性的实践教学案例：课程计划辅助制定实践教学案例和汽车牌照快速查找实践教学案例，并介绍课程评价体系。

2.1 课程计划辅助制定实践教学案例

2.1.1 问题描述

每学期一个学生允许同时学习多门课程，同一学期各课程之间不存在次序关系，使用拓扑排序知识制定课程计划使学生可在最短时间内完成所有课程。

2.1.2 实验数据（待完成的全部课程）

课程包括计算机导论、线性代数、离散数学、Passcal语言、汇编语言、C语言、数据库、数据结构、操作系统、编译原理及微机原理。此外，课程之间的先后关系可描述为如图2所示的活动顶点网络（AOV网络）。

2.1.3 案例构建核心思想

课程计划制定是将AOV网络中的顶点集合划分成互不相交的顶点子集{S1，S2，…，Sn}，并且获得的子集数量最少。对于任意通过弧相连的顶点应该属于不同的顶点子集。此外，假如代表一条从顶点i到顶点j的有向弧，[i∈Sk，j∈Sl]，则存在k

基于上述讨论，该实践教学案例可以归结为对拓扑排序知识改进，利用拓扑排序思想对顶点集合进行划分，将其划分为不同的子集，实现步骤如下：

Step 1：在AOV网络中寻找当前全部入度为0的顶点，构成一个新的顶点子集S;

Step 2： 删除AOV网络中子集S中全部顶点以及从这些顶点出发的弧。

重复上述两步，直到AOV网络为空。具体实现采用栈进行处理。当前栈为存储当前入度为0的顶点，备用栈为存储新生成入度为0的顶点。通过两个栈间相互交替，最终完成课程计划的制定。

2.1.4 程序设计过程

输入课程名称作为顶点，以及顶点之间先后关系，建立有向图G;

对有向图G集合划分，输出各学期课程计划。

}

（2） 栈程序模块：设计栈的抽象数据类型。

（3） 有向图G模块：构建有向图，实现拓扑集合划分。

（4） 程序的伪代码实现：

2.1.5 课程计划辅助制定结果

课程计划辅助制定结果如图3所示。从图3可以看出所获得的4个课程子集，即某位学生4个学期课程计划安排。S1={計算机导论、线性代数}，S2={Passcal语言，微机原理、离散数学}，S3={数据结构、C语言、汇编语言}，S4={操作系统、编译原理、数据库}。

2.2 汽车牌照快速查找实践教学案例

2.2.1 问题描述

对一批汽车牌照进行排序查找，利用基数排序和二分查找的思想完成程序设计任务。

2.2.2 实验（测试）数据

人工录入，或者自动随机生成一批以车牌号为关键的记录集合。

2.2.3 需求分析

（1） 利用基数排序的思想对一批具有结构特征的汽车牌照进行排序，并且利用二分查找的思想对排好序的汽车牌照记录实现查找。

（2） 测试数据的每个记录包括5项，分别为牌照号码、汽车商标、颜色、注册日期和车主的姓名，其中牌照号码一项的输入形式如图4所示。

其中K0和K1输入值为01～31（代表地区），K2输入值为A～Z（代表车的使用性质），后4位输入值为0000～9999（代表车号），例如01B7395。这种牌照号码具有多关键字的特征，可以将其分为3段分析，即数字、字母和数字。其余4项纪录内容由于不涉及到核心算法思想，因此只要一步字符串类型即可。查询时，必须输入合法的汽车牌照号码。

（3） 运行程序，输入要求的一批数据记录后，屏幕输出排好序的车牌号码以及相关信息。查询时，程序查找到匹配的数据，输入该关键字的其它数据项。

（4） 测试数据要求至少用30个左右的数据进行测试。

2.2.4 程序设计过程

（1） 主程序模块为：

（2） 静态链表模块：实现静态链表的数据类型。

（3） 排序模块：对数据记录进行排序。

（4） 查找模块：对排好序的数据记录进行二分查找。

2.2.5 程序的伪代码实现

2.3 课程考核评价体系

数据结构与算法属于应用类型课程，若采用单一闭卷考试，则无法客观评估学生对所学知识的应用能力。基于该原因，本研究设计并提出新的课程评价体系。新评价体系以工程教育专业认证的理念为主导，侧重实践过程分段考核评价，围绕课程知识点展开工程实践应用考核评价。结合分段考核（实践能力评价）与终结考核（期末理论考试）的方式，避免了学期末突击式学习，更加符合工程教育认证要求。具体课程考核评价标准见表1。

3 案例分析推广与改进

为了让更多学生受益，本研究对行动研究法进行改进，将其应用于数据结构与算法课程实践教学案例的分析推广与持续改进中。

3.1 原始行动研究法

Kurt Lewin[21]首次提出行动研究法，并将其应用于计划的制定。70年代后该方法被广泛应用于教育研究领域，通常可分为2个阶段：调研与判断、反馈研究与分析。

3.2 基于工程教育认证的改进行动研究法

基于工程教育认证的改进行动研究法主要包括5个阶段：

（1）分析工程教育认证通用标准与补充标准对数据结构与算法课程实践环节的要求，依据其课程特点设计科学、合理、可行的实践教学案例，并将教学案例设计付诸实践。

（2）将兰州交通大学电子信息工程学院作为试点，开设本课程。

（3）实践教学案例评估，评估每个教学案例的优劣性。采用问卷方式和教学效果测试相结合的方法完成实践教学案例优劣性评估任务。

（4）案例修改再实践。依据评估结果对案例进行修改，再于试点实践教学。经过1～2年时间形成成熟的实践教学案例。

（5）案例推广。将教学案例推广至兰州交通大学（甚至更广范围）开设数据结构与算法课程的专业。

4 结语

本研究通过对数据结构与算法课程和工程教育认证标准的深入分析，发现传统教学方法与考核标准工程教育认证要求之间存在一定差距。为此提出了基于实践教学案例为核心的数据结构与算法课程教学体系，首先以代表性实践教学案例“课程计划辅助制定”和“汽车牌照的快速查找”说明该教学体系的实施;其次，提出并设计了新的考核评价标准;最后，通过对行动研究法的完善，实现了对实际教学案例的分析推广与持续改进。

参考文献：

[1] 陈永，胡晓辉. 基于工程教育认证的《软件工程》课程教学质量建设研究[J]. 软件导刊，2016，15（9）：183-185.

[2] 周国芳，钱晓山，戚珉. 高校工程教育与人文教育融合研究分析[J]. 软件导刊，2013，12（10）：3-4.

[3] 贾红艳，薛薇，牛弘. 基于工程认证的控制仪表及系统课程教学研究[J]. 中国轻工教育， 2017， 11（6）： 43-46.

[4] 严蔚敏， 陈文博. 数据结构及应用算法教程[M].修改版.北京：清华大学出版社， 2011.

[5] 李春葆. 数据结构教程[M]. 北京：清华大学出版社， 2016.

[6] 张小艳， 李占利. 数据结构与算法设计[M] . 西安： 西安電子科技大学出版，2015.

[7] 陆淑娟，吕俊. 基于计算思维能力培养的C语言课程目标导学模式研究[J]. 软件导刊， 2017， 16（8）：214-215.

[8] 李素若. 基于慕课的编程类课程混合式教学模式研究与实践——以《C++程序设计》为例[J]. 软件导刊， 2017，16（1）：189-191.

[9] 于磊. 基于C#的WinForm开发中存储过程应用研究[J] . 软件导刊，2018，17（4）：178-183.

[10] 吴玫，王海晖， 李伟波， 等. 面向混合学习的Java课程教学设计——以武汉工程大学为例[J]， 2018， 17（4）： 210-222.

[11] 王生原. 编译原理[M]. 第3版.北京： 清华大学出版社， 2015.

[12] 张尧学，宋虹， 张高. 计算机操作系统教程[M]. 北京： 清华大学出版社，2013.

[13] 王珊，萨师煊. 数据库系统概论[M]. 北京：高等教育出版社， 2014.

[14] 王昱哲.？《数据结构》课程的教学方法研究[J]. 软件导刊， 2018， 17（2）： 76-77.

[15] 张冰涛， 王小鹏，？王履程. 协议组合逻辑安全的WMNs认证密钥协商方案[J]. 计算机应用研究， 2017， 34（8）： 2473-2477.

[16] 张冰涛， 王小鹏. 基于ECC的无线传感器网络安全分簇算法[J]. 兰州交通大学学报， 2016， 35（1）： 20-24.

[17] 张冰涛，王小鹏，李延林，等. 面向铁路应急的MANET安全节点发现协议建模[J]. 兰州交通大学学报， 2015， 34（1）： 60-64.

[18] 张冰涛，王小鹏. 面向WSN安全路由协议的自适应威胁模型[J].计算机应用研究，2014， 31（4）：1208-1211.

[19] 包振， 何迪. 一种基于图论的入侵检测方法[J]. 上海交通大学学报， 2010， 44（9）： 1176-1180.

[20] 张冰涛，王小鹏，王履程，等. 基于图论的MANET入侵检测方法[J]. 电子与信息学报， 2018， 40（7）： 1086-1093.

[21] LEWIN K. Action research and minority problems[J]. Journal of Social Issues， 1946， 2（4）： 34-46.

（责任编辑：江 艳）