文章

261

粉丝

19

获赞

402

访问

86.4k

头像
2020年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年12月3日 08:13
阅读数 40

(1)使用三层循环,分别遍历三个数组,计算s1与s2,s1与s3,s2与s3的最小距离 并且保存对应的最小距离,直至遍历结束后输出最小三元组

(2)int a[3] ,d=0,min= 1e10;

for( int i = 0; i <n;i++){for(int j =0;j < s2.len();j++){for (int k =0;k < s3.len();k++){ d = abs(s1[i] - s2[j]) + abs(s2[j] - s3[k]) + abs(s2[j] - s3[k]);  if (d <= min) { min = d; a[0] = s1[i]; a[1] = s2[j];a[2] = s3[k];}}}}

return a;

(3) 空间复杂度为O(3) 时间复杂度为O(n^3)


评分及理由

(1)得分及理由(满分3分)

学生给出的基本设计思想是三层循环遍历三个数组,计算所有三元组的距离并保存最小值。这属于暴力枚举法,思路正确但不够高效,没有体现“尽可能高效的算法”的要求。由于题目要求“尽可能高效”,而学生仅给出暴力法的思想,未能提出更优的算法设计(如多指针法),因此扣1分。得分:2分。

(2)得分及理由(满分8分)

学生用代码实现了三层循环的暴力枚举,但存在以下问题:
1. 代码不完整,缺少函数定义和必要的头文件,且数组长度获取方式不明确(如s2.len()在C语言中不合法)。
2. 距离计算公式有误:abs(s2[j] - s3[k])重复计算了两次,而abs(s3[k] - s1[i])缺失,导致逻辑错误。
3. 返回类型为int a[3],但函数未声明返回数组,且题目要求输出最小距离,而非三元组本身(虽然示例中要求输出距离,但通常算法返回距离即可)。
4. 代码风格不规范,缺少注释。
基于以上逻辑错误和代码不完整问题,扣5分。得分:3分。

(3)得分及理由(满分2分)

学生正确分析了暴力法的时间复杂度为O(n^3),空间复杂度为O(3)(即O(1)),但空间复杂度表述不规范(应写O(1))。由于分析基本正确,扣0.5分。得分:1.5分。

题目总分:2+3+1.5=6.5分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发