文章

137

粉丝

0

获赞

0

访问

8.3k

头像
2018年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年10月24日 16:53
阅读数 15


评分及理由

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

学生给出的基本设计思想是:先对数组进行快速排序,然后遍历数组寻找相邻正数差值大于1的位置来确定未出现的最小正整数。这种思路虽然可行,但并不是时间上尽可能高效的算法(题目要求时间上尽可能高效)。标准答案使用了O(n)时间复杂度的原地哈希方法,而学生的排序方法需要O(n log n)时间复杂度,效率较低。不过思路本身是正确的,只是不够高效。扣1分。

得分:2分

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

学生的代码实现存在多处逻辑错误:

  • 快速排序的划分函数中,内层循环缺少必要的边界检查,可能导致数组越界
  • 快速排序递归调用没有终止条件,会导致无限递归
  • find函数中的循环条件有误,当i = n-1时,A[i+1]会访问越界
  • 返回值的逻辑不完整,比如当所有元素都是负数时应该返回1,但代码逻辑不够清晰
  • 代码中有明显的语法错误,如函数名大小写不一致(Huafen和huafen)

虽然整体思路正确,但实现存在较多问题。根据错误严重程度扣4分。

得分:4分

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

学生正确分析了算法的时间复杂度为O(n log n)和空间复杂度为O(log n),这与快速排序的复杂度分析一致。这部分分析正确,不扣分。

得分:2分

题目总分:2+4+2=8分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发