文章
60
粉丝
0
获赞
0
访问
3.7k
(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分
登录后发布评论
暂无评论,来抢沙发