文章

179

粉丝

0

获赞

0

访问

9.0k

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


评分及理由

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

得分:1分

理由:学生的基本设计思想是使用双重循环遍历链表,外层循环遍历每个结点,内层循环检查后续结点是否有相同绝对值的结点并删除。这种方法虽然能实现功能,但时间复杂度为O(n²),不符合题目要求的"时间复杂度尽可能高效"的标准。标准答案采用空间换时间的策略,使用辅助数组达到O(m)时间复杂度。由于思路基本正确但效率不高,给1分。

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

得分:1分

理由:学生给出了单链表结点的基本数据类型定义,包含了data和next两个字段,这是正确的。但存在两个问题:一是使用了"LNode *LNode"这样的语法错误;二是没有使用typedef定义类型别名。考虑到核心结构定义正确,给1分。

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

得分:3分

理由:学生的算法实现存在较多问题:

  • 代码中有多处语法错误和逻辑错误
  • 在删除结点时,使用"q->next = q->next->next"会跳过当前q的下一个结点,而不是删除q本身
  • 没有正确处理删除操作时的指针链接
  • 缺少必要的头文件包含(如math.h)
  • 参数传递方式不合理

虽然算法的大致思路是正确的(双重循环检查绝对值重复),但由于实现存在严重缺陷,只能给3分。

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

得分:2分

理由:学生对时间复杂度和空间复杂度的分析是正确的。双重循环的时间复杂度确实是O(n²),只使用常数个指针变量的空间复杂度确实是O(1)。这部分分析准确,给满分2分。

题目总分:1+1+3+2=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发