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

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

0 引言

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

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

数据结构算法的理论证明包括性能、性质和正确性的证明。……