文章

60

粉丝

0

获赞

0

访问

3.7k

头像
2025年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年12月2日 17:08
阅读数 5

(1)

算法的基本设计思想:

第一步:构建长度和A数组长度一样的辅助数组;

第二步:将A中的元素放进辅助数组,用快速排序将辅助数组的序列排列成升序;

第三步:对于A[i]的元素是正数就与辅助数组最高位的元素相乘,是负数则与辅助数组最低位的元素相乘。

第四步:用一个变量max记录每一次遍历产生的最大值,并将max存进res[i]

(2)

(3)

时间复杂度:O(nlogn)

空间复杂度O(n)


评分及理由

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

得分:2分

理由:学生的设计思想存在逻辑错误。其核心思路是“对于A[i]的元素是正数就与辅助数组最高位的元素相乘,是负数则与辅助数组最低位的元素相乘”。这忽略了关键约束条件:题目要求 j ≥ i。排序后的辅助数组完全打乱了原始数组的顺序,无法保证找到的“最高位”或“最低位”元素对应的索引 j 满足 j ≥ i。因此,该思路无法正确求解问题。但学生给出了一个解决问题的框架(构建辅助数组、排序、根据正负选择乘数),并非完全离题,故给予部分分数。

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

得分:0分

理由:学生未提供任何算法代码描述。根据评分要求,未作答部分不得分。

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

得分:1分

理由:学生正确分析了其所述算法(基于排序)的时间复杂度O(nlogn)和空间复杂度O(n)。虽然其算法思路本身是错误的,但对其所描述方法的复杂度分析是准确的,故给予一半分数。

题目总分:2+0+1=3分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发