文章

54

粉丝

21

获赞

0

访问

4.0k

头像
2010年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年10月27日 20:31
阅读数 13

(1)先将整个数组进行逆转,然后将逆转的数组的第1到第n-p+1的元素进行逆转,将第n-p到第n个元素逆转。

(2)

(3)采用了循环遍历数组,时间复杂度为O(n),并没有建立新的数组,空间复杂度为O(1)。


评分及理由

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

学生的基本设计思想是:先将整个数组逆转,然后将前n-p个元素逆转,再将后p个元素逆转。这与标准答案中“三次逆转”的思想本质相同,但顺序不同。标准答案是:先逆转前p个,再逆转后n-p个,最后整体逆转;学生的方法是:先整体逆转,再逆转前n-p个,最后逆转后p个。这两种方法都是正确的,都能实现循环左移p位。因此,思路正确,不扣分。得4分。

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

学生给出的代码描述如下:

  • 定义了一个reverse函数,参数为数组a和左右索引left、right,使用双指针法进行逆转,逻辑正确。
  • 在main函数中,调用了三次reverse函数:第一次整体逆转(0到n-1),第二次逆转前n-p个元素(0到n-p),第三次逆转后p个元素(n-p+1到n-1)。

但代码存在以下问题:

  1. reverse函数没有返回值类型,应改为void(代码中写成了int,但函数体内没有return语句,逻辑上不影响,但语法不规范)。
  2. main函数中使用了未定义的变量a、n、p,这属于代码不完整,但核心算法逻辑正确。
  3. 第二次reverse的区间是0到n-p,但根据学生的设计思想,应该是逆转前n-p个元素,即索引0到n-p-1,这里写成了0到n-p,会导致多逆转一个元素,属于逻辑错误。
  4. 第三次reverse的区间是n-p+1到n-1,但根据设计,应该是逆转后p个元素,即索引n-p到n-1,这里写成了n-p+1到n-1,会导致少逆转一个元素,属于逻辑错误。

由于区间设置错误,代码无法正确实现循环左移,因此扣分。根据错误严重程度,扣3分。得4分。

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

学生正确分析了时间复杂度为O(n)和空间复杂度为O(1),与标准答案一致。得2分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发