2020年（408）计算机学科专业基础综合试题 - 第41题回答

评分及理由

（1）得分及理由（满分3分）

学生给出的基本设计思想是“利用3层循环，每次计算D的值，比较出最小的那个，然后输出”。这描述了暴力枚举所有三元组的思路，与标准答案中的方法一（暴力法）一致。该思想正确，但并非题目要求的“尽可能高效的算法”。考虑到题目要求“尽可能高效”，而学生给出了最基础的可行思路，可以给予部分分数。得2分。

（2）得分及理由（满分8分）

学生根据设计思想给出了C语言代码。代码框架正确，使用了三层循环遍历所有组合，计算距离D并更新最小值。但存在以下问题：

1. 函数参数声明不标准，应为int S1[], int m, int S2[], int n, int S3[], int q。
2. 第二次识别结果中，内层循环for(int p; p < q; p++)缺少初始化p=0，这是一个逻辑错误。
3. 函数在return min;后有一句printf，该语句永远不会执行，属于逻辑错误。
4. 题目要求输出最小距离，但并未要求输出对应的三元组。学生代码中记录了a, b, c但并未在返回值中体现，且最后的printf不可达，这属于冗余但不影响核心算法逻辑，根据“禁止扣分”原则，不因此扣分。但循环初始化错误需要扣分。
5. 空间复杂度分析错误（见第(3)部分）。

核心算法逻辑（三层循环计算距离）是正确的。考虑到参数声明不规范、循环初始化遗漏和不可达代码等错误，但主要逻辑正确，扣去相应分数。得5分。

（3）得分及理由（满分2分）

学生分析时间复杂度为O(m*n*q)，这是正确的。但空间复杂度分析为O(m*n*q)是错误的。该算法只使用了常数个额外变量（min, D, a, b, c, i, j, p等），空间复杂度应为O(1)。因此扣1分。得1分。

题目总分：2+5+1=8分

赞同