文章

81

粉丝

0

获赞

0

访问

5.0k

头像
2016年计算机学科专业基础综合试题 - 第43题回答
数据结构
发布于2025年10月18日 17:05
阅读数 8


评分及理由

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

得分:2分

理由:学生提出了"排序后从中间分开"的基本思路,这与标准答案中"将最小的⌊n/2⌋个元素放在A₁中"的思想是一致的,能够满足题目要求。但是学生没有提到使用快速选择算法来优化时间复杂度,而是直接使用快速排序,这在效率上不是最优方案。基本设计思想描述不够完整和深入。

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

得分:4分

理由:

  • 学生实现了快速排序算法,但存在多个逻辑错误:
  • huasten函数(应为partition)中,在第一个内层循环中,high--后立即执行A[low] = A[high],这不符合快速排序的划分逻辑
  • quick_sort函数缺少递归终止条件,会导致无限递归
  • divide函数中,A2数组的赋值逻辑有误,第二次识别中A2[t-i]是正确的,但第一次识别中A2[n-i+t]是错误的
  • 算法没有返回|S1-S2|的值,不符合题目要求
  • 没有实现标准答案中的部分排序思想,而是进行了完整的排序

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

得分:1分

理由:学生正确识别了快速排序的时间复杂度为O(n),但空间复杂度分析不准确。对于完整的快速排序,最坏情况下空间复杂度为O(n),平均情况下为O(log₂n)。但学生没有考虑到标准答案中部分排序的空间复杂度优势。

题目总分:2+4+1=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发