文章

27

粉丝

0

获赞

0

访问

1.2k

头像
2010年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年9月25日 15:45
阅读数 49


评分及理由

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

学生作答的基本设计思想是使用一个辅助数组,通过计算新下标 (i + n - p) % n 来实现循环左移。这种方法在功能上是正确的,能够实现题目要求。然而,题目要求“在时间和空间两方面都尽可能高效”,标准答案中给出了时间复杂度O(n)、空间复杂度O(1)的三次逆置法,而学生的方法空间复杂度为O(n),在空间效率上并非最优。考虑到题目要求“尽可能高效”,且学生的思路是可行的(只是非最优),扣1分。

得分:3分

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

学生根据其设计思想,使用C语言描述了算法。代码逻辑清晰,正确实现了其辅助数组的思路。但是,代码存在两个问题:

  1. 函数名为change,与题目要求的“循环左移”操作语义上不够贴切,但属于小问题,不扣分。
  2. 代码中使用了可变长数组int new[n];,这在C99标准中是允许的,但并非所有C环境都支持。更重要的是,题目要求“空间尽可能高效”,此代码显式地使用了O(n)的额外空间,与最优解相比存在不足。考虑到代码正确实现了所述功能,但空间效率非最优,扣2分。

得分:5分

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

学生正确分析了自己算法的时间复杂度O(n)和空间复杂度O(n)。分析正确,与代码实现相符。

得分:2分

题目总分:3+5+2=10分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发