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

基于工程认证的数据结构与算法课程教学研究 翻开文本图片集 摘 要：数据结构与算法课程作为计算机与信息类专业的根底课程，传统教学过程中存在重视理论教学，无视实践教学的问题。为适应工程认证要求，对数据结构与算法课程实践教学环节进行研究与改革。将原有以理论教学为主的教学方式，转换为以理论教学为根底、实践教学为核心的教学体系，从而锻炼和培养学生的工程实践能力。围绕实践教学环节，以兰州交通大学效劳大交通行业的特色为切入点，结合数据结构与算法课程特点，构建6～8个科学可行的实践教学案例，填补现阶段数据结构与算法课程实践教学环节无标准化、科学化、系统化教学案例的空白。 关键词：课程教学;工程教育;实践教学;教学案例 DOI：10. 11907/rjdk. 181674 中图分类号：G434文献标识码：A文章编号：1672-7800〔2023〕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]为根底。以2022年中华人民共和国教育部发布的关于成立教育部工程教育认证专家委员会的通知为起点，我国开展工程教育认证[2]工作已有十余年时间。2023年我国成为华盛顿协议预备成员国。2023年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到顶点j的有向弧，[i∈Sk，j∈Sl]，那么存在k<l。每个顶点子集代表同一学期开设的课程。 基于上述讨论，该实践教学案例可以归结为对拓扑排序知识改良，利用拓扑排序思想对顶点集合进行划分，将其划分为不同的子集，实现步骤如下： 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个左右的数据进行测试。