文章

119

粉丝

0

获赞

1

访问

10.0k

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


评分及理由

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

得2分。学生的基本设计思想是先对整个数组进行快速排序,然后取前一半和后一半分别求和,对于奇数个元素的情况,尝试将中间元素加入前一半或后一半,取绝对值较大的差值。这个思路可以满足题目要求,但效率较低,因为需要完全排序整个数组,而标准答案采用基于快速选择的部分划分,平均时间复杂度为O(n)。学生的思路虽然正确但不够高效,因此扣2分。

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

得5分。学生实现了快速排序和划分函数,但代码存在以下问题:
1. 快速排序函数缺少递归终止条件(如l>=r),这会导致无限递归,属于逻辑错误,扣2分。
2. 划分函数中,内层循环条件重复(外层while已检查l 3. solve函数中,对于奇数个元素的处理逻辑有误:计算中间元素加入后的差值时,表达式"sum1 - sum2 + A[n/2]"和"sum1 - sum2 - A[n/2]"不正确(应为分别加入sum1或sum2后计算差值),但思路正确,扣1分。
4. 代码未实现标准答案中基于枢轴的高效划分方法,而是完全排序,效率较低,但功能正确,扣1分。
总体代码能实现功能,但存在逻辑错误和效率问题,因此扣4分。

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

得1分。学生正确给出了时间复杂度O(nlog₂n)和空间复杂度O(log₂n)(快速排序的递归栈深度),但标准答案要求的是平均O(n)时间复杂度和O(1)空间复杂度。学生的算法复杂度高于标准答案,因此扣1分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发