文章

59

粉丝

0

获赞

0

访问

9.0k

头像
2025 年 5 月第 1 次 408 月考试卷 - 第41题回答
数据结构
发布于2025年11月5日 18:35
阅读数 5

1.维护一个长度为2的滑动窗口,当窗口中有两个同样的元素时清空,当窗口满且元素不一样时必然是第二个元素为要找的元素。

int find_singleton(int * arr, int n){

int i = 0;

while(i<n){

if(arr[i] == arr[i+1]){

i+=2;

}else{

return i+1;

}

}

只需遍历一次集合,复杂度O(n)


评分及理由

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

学生给出的基本设计思想是维护滑动窗口并比较相邻元素,当遇到相邻元素不相等时返回第二个元素。虽然描述不够精确(例如"清空窗口"的表述不准确),但核心思想是通过比较相邻元素来定位唯一出现一次的元素,与标准答案的遍历偶数位置比较相邻元素的思想本质一致。因此不扣分,得3分。

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

算法实现存在以下问题:
1. 代码逻辑错误:当相邻元素不相等时,返回的是索引i+1而不是元素值arr[i+1],这会导致返回错误结果(返回的是索引位置而非元素值)。
2. 边界情况处理不完整:如果唯一元素在最后一个位置,代码会访问越界(arr[i+1])且无法正确处理。
3. 缺少对最后一个元素的特殊处理。
基于上述逻辑错误,扣4分。代码结构基本正确,得4分。

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

学生正确指出算法时间复杂度为O(n),分析正确,得2分。

题目总分:3+4+2=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发