文章

238

粉丝

0

获赞

3

访问

33.1k

头像
2015年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年9月20日 16:53
阅读数 28


评分及理由

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

得分:2分

理由:学生的基本设计思想正确,使用了辅助数组(哈希表)来记录绝对值出现的次数,并通过遍历链表进行删除操作。但标准答案中强调“仅保留第一次出现的结点”,而学生的描述是“发现次数大于1则删除”,这实际上是在第二次及以后出现时才删除,与标准答案的思路一致(第一次出现时标记,第二次及以后删除)。然而,学生没有明确说明数组大小应为n+1(因为绝对值范围是0到n),且初始值应设为0,但思路核心正确,扣1分。

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

得分:1分

理由:学生定义了单链表结点的结构,但字段名使用了"val"和"next",而非标准答案的"data"和"link"。虽然字段名不同,但逻辑等价,因此不扣分。但标准答案中使用了typedef定义指针类型PNODE,而学生没有,这不影响算法实现,但严格来说不够完整,扣1分。

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

得分:4分

理由:学生的代码存在多处逻辑错误:
1. 数组hash的大小应为n+1(因为绝对值范围是0到n),但学生声明为hash[n],这会导致数组越界(例如,当绝对值为n时无法访问)。
2. 在删除节点时,没有释放被删除节点的内存,会导致内存泄漏。
3. 遍历逻辑有误:当删除节点时,t->next被更新为t->next->next,但t并没有移动,而是直接执行t = t->next,这可能会跳过节点或处理错误。标准答案中,只有在不删除时才移动p。
4. 函数返回head,但算法应修改链表而不需返回(因为参数是头指针)。
5. 没有检查头节点是否为空。
由于这些逻辑错误,扣4分。

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

得分:1分

理由:学生正确给出了时间复杂度和空间复杂度均为O(n),但忽略了实际链表长度m(时间复杂度应为O(m)),而空间复杂度是O(n)(数组大小)。因此扣1分。

题目总分:2+1+4+1=8分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发