文章

81

粉丝

0

获赞

0

访问

5.0k

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


评分及理由

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

得分:2分
理由:学生提出了排序后从中间划分的基本思路,这与题目要求的方向一致,能够满足|n1-n2|最小且|S1-S2|最大的要求。但设计思想描述过于简单,没有说明具体采用什么排序方法,也没有提到不需要完全排序的优化思想。相比标准答案中基于快速选择的思想,学生的思路不够高效和具体。

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

得分:4分
理由:代码实现存在多个问题:
1. huaten函数(应为partition)基本实现了划分功能,但缺少将枢轴值放回正确位置的步骤
2. quick_sort函数存在严重问题:递归调用没有终止条件,会导致无限递归;参数传递有误(n参数多余)
3. divide函数中quick_sort调用参数错误(high应为n-1而不是n)
4. A2数组赋值存在索引问题(第一次识别中A2[t+8-i]明显错误,第二次识别中A2[t-i]基本正确)
5. 没有计算和返回S2-S1的值
虽然代码框架基本正确,但实现细节存在较多逻辑错误。

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

得分:0分
理由:时间复杂度分析错误。学生写的是O(n),但实际实现的快速排序时间复杂度是O(nlogn)。空间复杂度O(log₂n)分析基本正确,但基于错误的时间复杂度分析。

题目总分:2+4+0=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发