文章
52
粉丝
0
获赞
0
访问
4.5k
评分及理由
(1)得分及理由(满分4分)
学生答案的基本设计思想是:先对数组进行快速排序,然后统计排序后数组中间位置元素(即A[n/2])的出现次数,若超过n/2则返回该元素,否则返回-1。这种思路基于“主元素若存在则一定是排序后的中间元素”的特性,是正确的。但标准答案采用了更高效的摩尔投票法(时间复杂度O(n),空间复杂度O(1)),而学生的排序方法时间复杂度为O(n log n),虽然正确但并非“尽可能高效”。根据题目要求“尽可能高效”,此方法效率较低,但思路正确,因此扣1分。得分:3分。
(2)得分及理由(满分7分)
学生实现了快速排序和统计逻辑,但存在以下问题:
1. `huafen`函数中返回的`mid`应为划分位置(即L或R),但学生返回的是基准值(mid),这会导致递归调用错误(Qsort中M应为下标,但实际是值)。这是一个逻辑错误,扣2分。
2. `func`函数参数应为`int A[]`,但第一次识别中写为`int A`(第二次识别正确),根据识别规则,若一次正确则不扣分。
3. 快速排序平均时间复杂度为O(n log n),但最坏情况为O(n²),不符合“尽可能高效”的要求,但算法功能正确,扣1分。
其他部分(排序和统计)逻辑正确。得分:7 - 2 - 1 = 4分。
(3)得分及理由(满分2分)
学生未说明时间复杂度和空间复杂度。但根据代码,时间复杂度为快速排序的O(n log n)(平均)或O(n²)(最坏),空间复杂度为递归栈的O(log n)(平均)或O(n)(最坏)。未回答扣2分。得分:0分。
题目总分:3+4+0=7分
登录后发布评论
暂无评论,来抢沙发