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

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

2、案例DOI：10.11907/rjdk.181674中图分类号：G434 文献标识码：A 文章编号：1672-7800（2019）001-0201-04Abstract：The course of Data Structure and Algorithm is a basic coursefor computer and information majors.There is the problem of focusing ontheory teaching and neglecting practice teaching in traditional teachingprocess.In o

3、rder to meet the requirements of engineering certification，thepractice and teaching part of this course are studied and reformed.Theoriginal teaching method，which is based on theory teaching，is convertedinto a teaching system based on theoretical teaching as a？foundation？andpractice teaching as the

4、core to train and temperi students engineeringpractical ability.In practical teaching，we take the characteristics ofLanzhou JiaoTong Universitys major transportation trade as the breakthroughpoint combined with the characteristics of data structure and algorithm courseto construct 6 to 8 scientific

5、and feasible practice teaching cases which fillthe blank of standardized，scientific and systematized teaching cases for thepractice teaching part.Key Words：curriculum instruction;engineering certification;practiceteaching;teaching cases0 引言工程教育專业认证作为工程师资格国际互认的标准，以由美、英等 6 国在 1989 年发起并签署的华盛顿协议1为基础。以 2

6、006 年中华人民共和国教育部发布的关于成立教育部工程教育认证专家委员会的通知为起点，我国开展工程教育认证2工作已有十余年时间。2013 年我国成为华盛顿协议预备成员国。2016 年 6 月，我国正式加入华盛顿协议3，成为该协议第十八个正式成员国，标志着我国工程教育专业认证工作获得了里程碑式的突破。由于工程教学认证在国际人才市场上具有很高的含金量，并且为工科院校学生培养提供了依据，目前我国多数工科院校都在积极开展工程专业认证工作。数据结构与算法课程4-6是程序设计的基础，在计算机、软件工程、物联网等专业的学习中占有重要地位。完成程序设计不仅需要掌握编程语言（如 C 语言7、C+8、C#9、Ja

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

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

9、充标准可知，工程教育认证以社会需求为导向，以学生为核心，其实质是以社会需求为基础，倒推毕业要求，以达到培养合格工程人才的目标。通用标准各部分之间的关系如图 1 所示。然而，目前我国高校本科教学往往以应试教育为导向，以专业骨干教师为核心开展教学工作，与工程教育以社会需求为导向、以学生为核心的理念相背离，导致工程人才培养与社会需求脱节。对于数据结构与算法课程而言，传统上按照线性结构、树形结构、图形结构为顺序主线，逐章进行理论知识讲解，虽然满足了应试教育的要求，取得了一定效果，但与工程教育专业认证导向和核心要求还存在一定差距。其主要问题表现在：教学方法方面，以理论教学为重点，忽视实践教学环节，甚至缺

10、失实践教学环节，从而严重限制了学生工程实践能力的培养，以至于学生在毕业时很难达到工程教育认证要求的毕业条件，不能满足社会需求;考核评价方面，以期末考试分数为主，平时表现为辅，虽然能在一定程度上衡量学生对知识的掌握程度，但是该考核评价体系存在局限性，不能有效评价学生实际工程应用能力，从而无法满足社会对工程人才的实际需求。2 基于工程认证的数据结构与算法课程改革针对目前数据结构与算法课程存在的问题，本文提出以实践教学案例为支撑，满足社会需求为导向，基于反向课程设计为基本原理，面向社会需求为起点，设计数据结构与算法课程实践教学案例，完善课程体系，支撑学生毕业指标点。毕业指标点主要包括：针对计算机专业

11、中存在的复杂工程问题，进行抽象分析，建立或选择合适的数学模型;运用计算机技术相关理论对复杂工程问题的解决方案进行研究分析并改进;能够运用专业理论和知识正确分析、评价工程中存在的复杂工程问题，提出相应的预防措施或解决方案，并制定合理课程评价体系。由于篇幅限制，本文仅列出具有代表性的实践教学案例：课程计划辅助制定实践教学案例和汽车牌照快速查找实践教学案例，并介绍课程评价体系。2.1 课程计划辅助制定实践教学案例2.1.1 问题描述每学期一个学生允许同时学习多门课程，同一学期各课程之间不存在次序关系，使用拓扑排序知识制定课程计划使学生可在最短时间内完成所有课程。2.1.2 实验数据（待完成的全部课程

12、）课程包括计算机导论、线性代数、离散数学、Passcal 语言、汇编语言、C 语言、数据库、数据结构、操作系统、编译原理及微机原理。此外，课程之间的先后关系可描述为如图 2 所示的活动顶点网络（AOV 网络）。2.1.3 案例构建核心思想课程计划制定是将 AOV 网络中的顶点集合划分成互不相交的顶点子集S1，S2，Sn，并且获得的子集数量最少。对于任意通过弧相连的顶点应该属于不同的顶点子集。此外，假如代表一条从顶点 i 到顶点 j 的有向弧，iSk，jSl，则存在 kl。每个顶点子集代表同一学期开设的课程。基于上述讨论，该实践教学案例可以归结为对拓扑排序知识改进，利用拓扑排序思想对顶点集合进行

13、划分，将其划分为不同的子集，实现步骤如下：Step 1：在 AOV 网络中寻找当前全部入度为 0 的顶点，构成一个新的顶点子集 S;Step 2：删除 AOV 网络中子集 S 中全部顶点以及从这些顶点出发的弧。重复上述两步，直到 AOV 网络为空。具体实现采用栈进行处理。当前栈为存储当前入度为 0 的顶点，备用栈为存储新生成入度为 0 的顶点。通过两个栈间相互交替，最终完成课程计划的制定。2.1.4 程序设计过程输入课程名称作为顶点，以及顶点之间先后关系，建立有向图 G;对有向图 G 集合划分，输出各学期课程计划。（2）栈程序模块：设计栈的抽象数据类型。（3）有向图 G 模块：构建有向图，实现

14、拓扑集合划分。（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）利用基数排序的思想对一批具有

15、结构特征的汽车牌照进行排序，并且利用二分查找的思想对排好序的汽车牌照记录实现查找。（2）测试数据的每个记录包括 5 项，分别为牌照号码、汽车商标、颜色、注册日期和车主的姓名，其中牌照号码一项的输入形式如图 4 所示。其中 K0 和 K1 输入值为 0131（代表地区），K2 输入值为 AZ（代表车的使用性质），后 4 位输入值为 00009999（代表车号），例如 01B7395。这种牌照号码具有多关键字的特征，可以将其分为 3 段分析，即数字、字母和数字。其余 4 项纪录内容由于不涉及到核心算法思想，因此只要一步字符串类型即可。查询时，必须输入合法的汽车牌照号码。（3）运行程序，输入要求的一批数据记录后，屏幕输出排好序的车牌号码以及相关信息。查询时，程序查找到匹配的数据，输入该关键字的其它数据项。（4）测试数据要求至少用 30 个左右的数据进行测试。