1. 引言
近年来，学科交叉融合已成为全球高等教育改革与发展的主流趋势。这种融合不仅是培养复合型创新人才的有效路径，还对解决经济社会发展和国计民生中的重大社会问题具有重要意义[1]。生物信息学作为生命科学、数学和计算机科学与技术等多学科交叉的产物，涵盖了生物信息的采集、处理、存储、传播、分析和解释等多个方面。在多学科复合型人才培养的需求下，生物信息等交叉学科的专业人才培养应着重提升学生的实践应用能力和创新能力[2]。为了有效培养生物信息工程专业人才所需的计算思维和系统构建能力，新工科计算机教育需要与学科需求紧密结合。数据结构课程作为计算机专业的核心基础课程，主要研究非数值计算问题，涉及数据的逻辑结构、存储结构以及相关操作的实现，旨在培养学生的问题分析、抽象和求解能力。掌握数据结构课程有助于提升生物信息专业学生的信息素养和解决实际问题的能力。然而，由于数据结构课程内容较为抽象，非计算机专业的学生往往难以理解，学习兴趣不高，导致以往的教学效果不尽如人意。
2. 课程现状及分析
依托学校“大数据智能”特色学科优势和“大数据生物智能重庆市重点实验室”的研发实力，重庆邮电大学生物信息专业以生物学、数学为基础，以计算机科学与技术为核心，致力于培养具有信息学科优势的生物大数据信息分析处理特色的人才。数据结构为重庆邮电大学生物信息工程专业的必修课。数据结构主要包括线性表、栈、队列、串、数组、广义表、树、图、查找、排序、相应算法的设计与分析等内容模块。课程理论内容抽象，实验课程编程复杂，导致以往的教学效果不理想。通过调研分析、归纳总结发现在教学过程中主要存在以下问题。
1) 教师在组织教学过程中，未充分结合学生的专业背景，学生不理解数据结构这门课程在专业领域的应用。数据结构与专业课程的内在关系未得到充分挖掘，缺乏具有领域特色的实践与应用。学生不知道在数据结构课程中学习的知识可以用于专业领域哪些地方，解决什么问题，导致学习主动性和积极性不高。
2) 非计算机专业的学生编程基础相对薄弱，且数据结构课程本身比较抽象，从而导致学生学习课程时难以捕获主要教学内容和教学难点。学生缺乏从计算机角度考虑问题的思维习惯，前序课程基础C语言中指针、结构体等知识掌握不牢固，从而影响到数据结构相关知识的学习。
鉴于此，针对生物信息等交叉学科的数据结构课程教学迫切需要打破固有的模式，结合学生专业背景推行教学改革势在必行。
3. 结合专业背景的问题驱动教学模式
数据结构课程的总体教学目标是培养学生的数据抽象、算法设计和程序编制的能力，提高学生对实际问题的分析与解决能力[3]。针对目前学生学习积极性不高的问题，在课程内容教学中，结合专业背景，采用问题驱动教学模式。具体的教学模式如图1所示。
Figure 1. Problem driven teaching mode
图1. 问题驱动教学模式
课前教师结合学生专业背景创设问题情境，并设计驱动问题，录制问题驱动微课视频，然后利用雨课堂等教学平台发布录制的微课视频，布置在线预习任务和课前自测题。学生提前浏览学习任务，对教师发布的在线资源进行预习，并完成课前预习自测题。课堂教学过程中，教师根据设计的驱动问题对知识点进行启发式教授，通过案例拆解引导学生对相关问题进行讨论，还可通过发布即时随堂限时测验检验学生知识点的掌握情况。课后教师根据学生的专业背景和问题情境设计作业，并设计专业拓展思考题。学生完成作业对所学知识进行练习巩固，并对教师发布的拓展问题进行思考和探索。教师建立线上交流群，学生遇到困难时可通过线上或线下方式在群内发起讨论。教师定期归纳共性难题，并对薄弱知识点巩固讲解。通过问题驱动教学方法，线上线下结合的混合式教学模式，不断引导学生进行探索、反思、优化改进，推动教学的革新和进步[4]。
4. 融合专业背景的问题驱动教学改革
针对关键知识点，结合生物信息工程专业背景设计问题驱动案例库。以字符串的模式匹配算法为例，结合生物信息工程专业背景，融合问题驱动的教学设计案例如下。
4.1. 教学案例设计
针对串的模式匹配算法课程知识点教学目标有：① 通过实际应用需求，理解模式匹配的应用价值；② 掌握串的模式匹配BF (Brute-Force)算法和KMP (Knuth-Morris-Pratt)算法。基于教学目标，从教学思路、问题设计和教学方法三个方面深入思考教学案例的设计，细化问题驱动教学模式。
4.1.1. 教学思路
教师首先介绍病毒感染后需要进行DNA序列检测的问题情境，以如何设计高效的检测方案作为问题前导。接下来，以人的DNA序列为主串，以病毒的DNA序列为子串，引出串的模式匹配问题。进一步，针对待解决的问题，教师进行问题驱动的启发式讲授，学生分组进行讨论；最后，教师总结问题的核心，并启发学生将解决方法和思维方式用到类似的问题上，从而培养学生的问题解决能力。整个教学过程贯穿问题驱动、层次递进的教学方法。
4.1.2. 问题设计
以串的模式匹配为例，创设问题情境，并设计表1中描述的问题。
问题情境：医学领域的专家们最近发现了几种新型病毒，他们通过检测分析，得知这些病毒的DNA结构都是环状的，这种环状结构显著提升了病毒的复制效率。为了快速判断人们是否感染了这些病毒，研究者们现在收集了这些病毒的DNA数据和人体DNA数据。为了研究便利，他们将这些DNA信息转化为由特定字母组成的字符串序列。接下来，研究者们将检测患者的DNA序列中是否包含某种病毒DNA序列。如果检测结果显示存在这样的序列，则意味着患者已经感染了该病毒；若未检测到，则表明患者未感染该病毒。例如，假设病毒A的DNA序列为baa，患者1的DNA序列为aaabbba，患者2的DNA序列为babbba，请检测患者1和2是否感染病毒A(注意，人的DNA序列是线性的，而病毒的DNA序列是环状的)。
思路分析：这个案例的核心在于字符串的操作。将病毒的DNA序列看作是子串，患者的DNA序列看作是主串。检测过程的核心就在于确定这个子串(病毒DNA片段)是否在主串(患者DNA序列)中出现过。这种查找子串在主串中位置的过程通常称为串的模式匹配或简称为串匹配。在模式匹配的过程中，需要设定两个角色：一个是主串S，也称正文串；另一个是子串T，也称为模式串。检测的目标是在主串S中搜索与模式T相匹配的子串。如果找到了匹配的子串，确定并返回子串中第一个字符在主串S中出现的位置。针对这种模式匹配任务，存在多种著名的算法，其中最常用的有BF算法和KMP算法。这些算法可为检测任务提供高效且准确的解决方案。
教学难点分析：在教材[5]中，BF算法和KMP算法均采用了顺序存储结构，其基本原理是通过游标i和j来定位主串S和模式串T中当前参与匹配的字符，并逐一进行比较。然而，在实际教学过程中，存在一些潜在的难点：
处理“失配”情况：当在匹配过程中发现主串S中的字符与模式串T的当前字符不匹配时，如何有效地对游标i进行回溯是一个关键的问题。
BF算法中的回溯可读性：在BF模式匹配算法中，当发生“失配”时，通常使用语句“i = i – j + 2”来更新游标i的位置。然而，这条语句的可读性较差，学生难以理解其背后的逻辑和原因。
KMP算法中的next数组介绍：在描述KMP算法时，教材跳过最长公共前后缀的介绍，直接讲解next数组，这种做法虽然简洁，但对于初学者来说增加了理解的难度。
针对以上教学难点，需对特定条件进行判断，然后分情况进行处理，并通过实际案例的可视化图解来帮助学生理解算法的原理和细节，问题设计如表1所示。
Table 1. Question design
表1. 问题设计
问题序号 |
问题描述 |
1 |
请结合病毒感染检测案例，谈谈串的模式匹配算法在生物信息领域的应用。 |
2 |
教材中串的模式匹配算法是基于串的顺序存储结构实现的。请结合教材中的结构体定义，谈谈串的定长顺序存储结构与串的堆式顺序结构之间的差别。 |
3 |
利用pos表示主串S的匹配起始位置，分别利用计数指针i和j表示主串S和模式T中当前正待比较的字符位置。i初值为pos，j初值为1。结合图示，提炼S[i] = T[j]时BF算法i和j指针如何变化，并用类C语言进行描述。 |
4 |
当S[i]≠T[j]时，指针后退，j回退到1，结合，i指针回退到主串的下一个字符，结合图示，计算i指针的回溯位置。 |
5 |
结合3和4两种情况，归纳BF算法的类C语言描述。 |
6 |
分组讨论，S=’aaaaaba’，T=’ba’和S=’aaaaaab’，T=’aab’这两种情况下BF算法的效率。并分析BF算法的优缺点。 |
7 |
在理解BF算法不足的基础上，谈谈KMP算法的核心思想。 |
8 |
结合图示，在理解最长公共前后缀的基础上，归纳总结如何求解next数组。 |
9 |
在掌握next数组求解的基础上，归纳KMP算法的类C语言描述。 |
10 |
比较BF算法和KMP算法。 |
4.1.3. 教学方法
在教学实践中，采用线上线下相结合的混合教学模式。首先，在课前阶段，根据课程内容精心设计问题，并提前发布给学生，鼓励他们以教材为基础，自主预习并进行相关的学习探索。接着，在课中环节，教师根据学生的实际需求，灵活地引入问题导向，组织学生进行深入的讨论与交流，以此丰富课堂教学内容。最后，课后阶段，学生需要对课程知识点进行归纳与总结，从而达到提升能力的目的。整个过程中，采用包括雨课堂教学平台、线下讲授、互动交流以及总结点评等多种方式实现多元化、一体化教学。
4.2. 教学案例实施
在明确教学思路、进行问题设计和制定教学方法的基础上，以字符串模式匹配为例，进行问题驱动的启发式教学案例设计。参考文献[6]的做法，将教学过程分为两个阶段，首先学习BF算法，然后深入探讨KMP算法，后者是在前者的基础上进行了优化和改进。
4.2.1. 第一阶段—BF算法的问题驱动教学
教师首先引入3.1中的问题情境，并且提出问题1，激发学生兴趣。其次，教师简要回顾字符串的顺序存储结构，并且提出问题2。接下来，教师结合图示(见图2)向学生讲解字符匹配“成功”时i指针和j指针如何变化，并提出问题3。引导学生归纳出当字符匹配成功时，继续比较下一个字符，i = i + 1；j = j + 1。然后，教师结合图示(见图3)向学生讲解字符串匹配“失败”时i指针如何回溯，j指针如何变化，并提出问题4。当发生失配时，教材中介绍应从主串的下一个字符(i = i − j + 2)起重新和模式串的第一个字符比较，但并未解释为何i = i − j + 2，这一点对初学者来说理解起来有一定难度。教师可引导学生将pos + 1(主串的下一个字符)作为未知数，将i和j的当前位置视为已知数，通过解方程求出pos + 1的值，即i − j + 2。结合问题3和问题4，教师提出问题5，引导学生归纳BF算法的类C语言描述。最后，教师提出问题6，让学生分组讨论BF算法在最好情况和最坏情况下的效率，并通过思考和讨论，总结BF算法的优点和缺点。在此基础上，教师提出问题7，请同学们带着问题了解KMP算法的核心思想。
Figure 2. BF algorithm successfully matches characters, the i pointer and the j pointer are moved back one position
图2. BF算法字符匹配成功时i指针和j指针各向后挪一位
Figure 3. BF algorithm character matching fails, the i pointer backtracks to pos + 1 and the j pointer backtracks to 1
图3. BF算法字符匹配失败时i指针回溯到pos + 1，j指针回退到1
4.2.2. 第二阶段—KMP算法的问题驱动教学
教师介绍KMP算法，通过构建具体的学习支架，着重指出相较于BF算法，该算法的改进之处在于避免字符匹配失败时i指针无意义的回溯。核心在于利用已经得到的“部分匹配”的信息将模式串向右“滑动”尽可能远的一段距离。为什么可以这样做呢？教材中并没有深入阐述，但这对于初学者构成了一定的理解障碍。教师应指出这是因为模式串中“部分匹配”的部分存在公共前后缀。教师可结合图示(见图4)，向同学们介绍最长公共前后缀的概念，让同学们从原理上理解KMP算法的核心思想。这里以主串S = “…ababaababcbab”，模式串T = “ababc”为例。当匹配至i = pos + 4，j = 5时遭遇不匹配。此时，教师可引导学生观察模式串，会发现在匹配的部分里，存在相同前后缀子串。基于这一发现，下一趟的比较就可以像图4这样做，这也是KMP算法效率高的关键所在。也就是前缀直接滑到了后缀的位置上。为什么可以这么做呢？因为在与主串匹配的部分中，模式串第1个和第2个元素与第3个和第4个完全一样。此时主串的比较指针i就可以继续从i = pos + 4开始比较，模式串的比较指针j也不需要从1开始直接比较，可以从j = 3的位置开始比较。
Figure 4. KMP algorithm character matching fails, the pointer j slides to the right
图4. KMP算法字符匹配失败时j指针向右滑动
Table 2. The process of finding k using the pattern string T = “ababc” as an example
表2. 以模式串T = “ababc”为例求k的过程
字符 |
a |
b |
a |
b |
c |
j |
1 |
2 |
3 |
4 |
5 |
T1 − Tj构成的模式串 |
a |
ab |
aba |
abab |
ababc |
子串M = T1 – Tj − 1 |
不存在 |
a |
ab |
aba |
abab |
M的前缀子串 |
不存在 |
空 |
a |
a、ab |
a、ab、aba |
M的后缀子串 |
不存在 |
空 |
b |
a、ba |
b、ab、bab |
相同的前后缀子串 |
不存在 |
无 |
无 |
a |
ab |
相同的最大前后缀子串 |
不存在 |
无 |
无 |
a |
ab |
k |
0 |
1 |
1 |
2 |
3 |
推广到一般情况，遭遇不匹配时，模式串向右滑动多远的距离呢？问题就可以转换成对模式串中的每一个字符pj，找出p0p1…pj串中相同的最长前缀子串与后缀子串的长度k，k取值只与模式串有关，与目标串无关。k的数值存在next数组中。教材中通过公式推导出next数组，这并不容易理解。教师可首先介绍用于构造next表格的穷举方法，如表2所示。然后提出问题8，让同学们归纳出next数组的构造方法。在掌握next数组求解的基础上，教师提出问题9，请同学们归纳KMP算法的类C语言描述。最后，教师提出问题10，并引导学生以讨论的形式对两个算法进行优缺点比较。在讨论过程中，教师扮演导航者的角色，确保讨论聚焦于关键点，并最终归纳出两点共识：1) 当需要从外部存储器加载主串的情况下，KMP算法可展现出其优越性。2) 尽管有优势，KMP算法并非在所有情况下都优于BF算法，两者各有千秋。
5. 教学改革效果
启发式教学改革，融入问题驱动机制，有效契合了复合型创新人才培养的新要求，显著降低了学生在理论课程理解上的难度。为评估这一改革成效，我们利用“问卷星”平台进行了教学满意度调查，内容聚焦于课程与教学满意度、问题驱动教学法对提升学习动力的影响、图解辅助理解算法核心原理的有效性，以及学生对结合专业实例作为学习辅助的期望。调查反馈显示：69.34%的学生肯定问题驱动教学对学习积极性的正面效应，74.59%的学生支持图解作为学习辅助手段，而65.78%的学生则希望教师能结合专业背景提供实例。生物信息工程专业数据结构两个教学班教学改革试行前后学生平均成绩及学评教结果对比如表3所示。这些数据充分表明，在课程教学中实施的问题驱动教学改革成效显著，并获得了学生的广泛认可。
Table 3. Students’ average grades and teaching evaluation results before and after the implementation of problem driven Teaching Reform
表3. 问题驱动教学改革试行前后学生平均成绩及学评教结果
|
教学改革试行前 |
教学改革试行后 |
2023~2024 (1) 01 |
2023~2024 (1) 02 |
2024~2025 (1) 01 |
2024~2025 (1) 02 |
平时成绩平均分 |
80.57 |
81.5 |
84.65 |
85.975 |
卷面成绩平均分 |
55.34 |
60.97 |
70.99 |
74.02 |
课程满意度 |
74.1 |
82.5 |
84.2 |
80.2 |
学评教得分 |
94.253 |
96.475 |
96.963 |
96.779 |
6. 结语
为满足交叉学科计算机人才培养的需求，并有效缓解当前交叉学科数据结构课程教学中的诸多挑战，以生物信息工程专业为例，引入了一种问题驱动的启发式教学改革模式。该模式通过在整个教学过程中持续融入问题导向的教学方法，辅以严谨的教学过程管理，激发了学生的学习主动性与积极性。通过这些启发式教学改革，学生不仅可以学习到数据结构的理论知识，还能够获得专业领域的应用实践经验，提升问题解决和创新能力。
基金项目
重庆市高等教育教学改革研究项目，工程教育认证背景下的智能产业创新型人才培养模式改革研究与实践，编号：203395。
NOTES
*通讯作者。