2010年计算机学科专业基础综合试题 - 第42题回答
1 可以构造一个辅助数组 数组长度位n 把数组的前n-p项赋值成 Xp,Xp+1,...Xn-1 ,后p项赋值成x0 X1..XP-1 这样新的数组就是原数组循环左移P个位置后的数组
void func(int R[],int P){
int arr[n]={ 0 };
int i=0;
int k=0;
for(i=0;i<=n-p;i++) //把原数组中Xp到Xn-1个元素的赋值到新的数组
arr[i]=R[p++];
for(int j=i;j<n;j++) //把剩余元素赋值到新数组
arr[j]=R[k++];
}
//新数组即为所求数组
}
3 时间复杂度 O(n) 空间复杂度O(n)
评分及理由
（1）得分及理由（满分4分）
得分：3分
理由：学生的基本设计思想是使用辅助数组来存储循环左移后的结果，思路正确且能够解决问题。但是，该算法需要O(n)的额外空间，而题目要求"在时间和空间两方面都尽可能高效"，标准答案中给出了空间复杂度为O(1)的原地算法，因此学生的方案在空间效率上不够优化，扣1分。
（2）得分及理由（满分7分）
得分：4分
理由：代码实现存在多处逻辑错误：
- 函数参数缺少n（数组长度）参数，无法确定数组边界
- 在第一个for循环中修改了参数P的值，这会影响到第二个循环
- 第一个for循环的边界条件有误，应该是i < n-p
- 第二个for循环的边界条件有误，应该是j < n
- 代码没有将结果复制回原数组R，只是计算了辅助数组arr
- 变量k的初始值应为0
由于存在多个逻辑错误，严重影响了算法的正确性，扣3分。
（3）得分及理由（满分2分）
得分：2分
理由：学生正确分析了算法的时间复杂度为O(n)和空间复杂度为O(n)，与实现的算法相符，得满分。
题目总分：3+4+2=9分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发