文章

41

粉丝

0

获赞

2

访问

2.9k

头像
2015年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年11月29日 20:43
阅读数 10


评分及理由

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

得分:2分

理由:学生的基本设计思想是采用三指针法进行双重循环遍历,这种方法确实能够实现题目要求的功能,但时间复杂度为O(m²),不是最优解。标准答案采用的是空间换时间的思路,使用辅助数组达到O(m)的时间复杂度。由于题目要求"时间复杂度尽可能高效的算法",学生的方案虽然正确但效率不高,扣1分。

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

得分:2分

理由:学生给出的单链表结点数据类型定义完全正确,与标准答案一致,使用typedef定义了结构体和指针类型,符合要求。

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

得分:5分

理由:算法实现存在以下问题:

  • 代码逻辑错误:在每轮外层循环开始时,q和k的初始化位置不正确。当P移动到下一个结点时,q应该初始化为P->next,k应该初始化为P,但代码中只在开始时初始化了一次,导致后续循环中q和k的指向错误。扣2分。
  • 边界条件处理:没有考虑链表为空或只有一个结点的情况。扣1分。
  • 绝对值比较逻辑:虽然使用了q->data == P->data || q->data == -P->data,但应该使用abs函数或更规范的绝对值比较方式。考虑到这是实现细节,不扣分。
  • 算法功能:基本思路正确,能够实现删除绝对值相同结点的功能,给基础分。

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

得分:2分

理由:学生对时间复杂度和空间复杂度的分析正确。算法确实是O(m²)的时间复杂度和O(1)的空间复杂度,与实现一致。

题目总分:2+2+5+2=11分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发