数据结构课程中理论证明的不足及加强策略

程欣宇，张 丽，汪 健，叶 晨

（贵州大学 计算机科学与技术学院，贵州 贵阳 550025）

0 引言

数据结构课作为计算机专业的核心课程，既有理论分析数据之间的逻辑关系、存储效率和算法执行效率，又有解决实际问题的案例。但目前的教材、教学案例、考核中，几乎没有各种经典案例的理论证明［1-2］。例如：为什么最小生成树的Kruskal算法每次选择两个联通代价最小的连通分量进行连通？Dijkstra算法为什么选择离源顶点直接路径最短的顶点？Huffman树为什么选择权值和最小的两个根结点合并？匹配字符串的KMP、BM算法效率高，但会漏配错配吗？通过教学，学生学会了这些算法的操作步骤，能通过画图、填表和分析复杂度，完成相应的作业和考试，也能编写程序对输入的问题实例进行求解。但是，学生大概率并不知道，也未曾思考过：这些数据结构的操作算法在任何情况下都能保证正确性吗？如何证明这些算法的正确性？更进一步地，这些算法是如何被前人设计出来的？有没有更统一的规律存在，以指导人们获得更广泛的问题求解能力？“道技关系”是教书育人者应该思考的［3］。若不引导学生思考这些问题，当出现的实际问题需要学生设计数据结构和算法时，学生即便能够设计出高性能的数据结构和算法，也很难去证明或者证伪一个算法的正确性。本文重点讨论形成这种现象的原因、可能产生的危害以及相应的改进对策。

1 数据结构课程不重视算法理论证明的原因

数据结构算法的理论证明包括性能、性质和正确性的证明。定量分析在教学中有大量讨论，如二叉树的度为2的结点数量是多少？合并排序最坏情况的比较次数是多少？但是，性质和正确性的证明鲜有讨论，如搜索匹配的错配漏配问题、最优化目标是否能够保证的问题，本文归纳原因如下：

1.1 课程侧重点

数据结构课程信息量大，各种逻辑结构、物理结构的组合繁多，对应可以解决的问题案例也非常多。需要讲授大量概念、方法和案例分析，又要强调掌握计算步骤，要能够上机实践，还要做性能分析，再加上学时数有限，导致教学中很容易放弃对理论证明的要求。虽然实验验证仅仅是证明了相关算法在少量的典型数据上有效，但其并不能像理论证明一样，能够更全面地证明算法的正确性，后者仍然被挤占掉。

1.2 学科侧重点

计算机科学与技术作为最热门的学科，新理论新技术层出不穷，新应用遍地开花。编程动手能力成为评价学生的一大指标，编程本身就容易出现各种问题导致学生放弃，因此但凡学生能够熟练编程，甚至做出一些直观演示效果好的程序或应用，教师就会给予很大鼓励，很容易放松对理论严谨性的要求。

计算机科学与技术作为可以授予理科或者工科的一级学科，一流学科建设中的大多数学校选择了授予工科学位，也导致了对理论深度要求的欠缺。

1.3 教学与考核难点

教学和考核数据结构的基本概念、基本性质、基本运算方法，如记住什么叫稳定的排序、学会将插入结点后的AVL树调整平衡、分析一个数据操作最坏情况下的复杂度相对容易。但是理论证明或者证伪一个算法，就如同考核一个现实问题的算法设计到程序设计一样难。由于涉及到不同的算法规模、底层逻辑，因此解题思路灵活，非常难以判卷给分，出题难度和灵活性也不好控制，一不小心就难住大部分学生。

本文举一个真实的教学案例，用以反映OJ测试可能存在的不严谨性。在某大学的OJ系统中，为了考察学生对字符串快速匹配算法的掌握情况，有这么一道题：输入为两个字符串A和B，要求设计程序判断A是否为B循环左移的结果。命题者希望学生能够将A复制拼接成AA后，判断B是否在AA中出现。但在给测试用例时，没有考虑到：如果A和B满足循环左移后的相等关系，A、B循环相邻字符的共生矩阵也必然相等，而计算共生矩阵只需要线性时间［4］。因此，用很短的代码，只检查了必要性，未真正用高性能字符串匹配算法检查充分性，也能欺骗过OJ，拿到此题的满分，运行耗时还比严谨正确的算法快不少。

2 数据结构课程中理论性证明不足的危害性

从本科生到工程师或者研究生，总会面临一些数据结构和算法设计，如果对正确性证明认知不足［5］，迟早会暴露以下问题：

2.1 理论支撑欠缺，学生理论水平难获提升

即便所设计的算法高效可靠，但是因为缺乏理论证明方法，哪怕通过大量测试，也无法在根本上保证算法程序的正确性［6］，客户和团队也担心关键时刻失效。面对重大项目就不敢上马，不能承担重任，难以获得技术创新的红利。这在教学时不能立即感受到，需要持续和重点关注一定量的学生工作后的长期发展，具有丰富项目经验的教师越能体会到这点。如一个动手能力较强的学生，参与了实战型的毕业设计，他采用邻接矩阵存储3 000个道路卡口的连接情况。答辩时提问：“你用邻接矩阵存储，难道不考虑存储的代价是n?0?5吗？”，学生回答是：“我用了json存储，比较紧凑。”其实，不管是json还是yml、bson，都是一种紧凑的数据交换格式，仅仅能够将系数的存储空间优化，并不能解决稀疏矩阵的存储和高效检索。这个案例很典型，反映了不少学生和教师，一旦重视动手能力培养，就容易放松理论水平的修炼。

2.2 严谨性不足，算法“失效”情况难以预料

与上述难以证明导致无法上马的情况不同，市场讲究竞争、业绩和“快鱼吃慢鱼”，更多算法的理论正确性证明会以各种测试进行代替，继而上线。如上文所举例子，测试用例本身是难以全面覆盖的，稍有疏忽，系统就会出现漏洞，继而导致数据完整性、一致性和计算结果可靠性降低。

再以数据结构循环队列的一个应用教学案例为例。循环队列的应用很多，一个抽象但能够映射很多现实问题的案例［7］是这样的：已知一个集合A中有n个元素及其冲突关系矩阵R，希望将A划分为若干个子集，使得相同子集中的元素不冲突。此案例充分利用了循环队列：将A中元素所有入队，循环从A中取出队首元素，若该元素与当前子集中的元素不冲突，就放入当前子集，否则就放回队尾。队列中的元素出队一遍前，创建一个当前子集，直到队列空。案例中9个元素的冲突关系为：R=｛（2，8），（9，4），（2，9），（2，1），（2，5），（6，2），（5，9），（5，6），（5，4），（7，5），（7，6），（3，7），（6，3）｝。按方法操作下来划分的子集为：｛1，3，4，8｝、｛2，7｝、｛5｝、｛6，9｝。但更好的划分方案为：｛1，3，5，8｝、｛2，4，7｝、｛6，9｝。如果不讲清楚这个算法的不足，学生会默认这是一个高效且完全正确的算法。

3 改进对策

针对数据结构课程中理论性证明不足的原因及危害，提出以下改进对策：

3.1 指导思想上，“术”“道”兼备

在学科指定培养方案时，要有理工兼备的指导思想，既传授“术”，也探讨“道”。具体到数据结构课程中，除强调数据的逻辑关系、存储结构、访问效率，也应当注重数据访问算法的正确性。

3.2 教学实操上，以学生为中心，注重正确性考察

（1）充分相信

提醒您：因为《数据结构课程中理论证明的不足及加强策略》一文较长还有下一页，点击下面数字可以进行阅读！

《数据结构课程中理论证明的不足及加强策略》在线阅读地址：数据结构课程中理论证明的不足及加强策略