文章

119

粉丝

0

获赞

1

访问

10.0k

头像
2015年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年8月21日 21:01
阅读数 78


评分及理由

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

得3分。学生的基本设计思想与标准答案一致,都是使用辅助数组记录已出现的绝对值,然后遍历链表进行删除操作。思路正确,描述清晰。

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

得1分。学生给出了单链表结点的数据类型定义,但存在错误:在C语言中,结构体定义中应使用"struct node *link"而不是"node *link",因为"node"类型名尚未定义(除非使用typedef)。此外,标准答案中通常使用typedef来定义节点类型,但学生没有完整使用typedef(第一次识别中使用了typedef,但第二次识别中未使用,且结构体标签缺失)。扣1分。

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

得5分。学生实现了算法,但存在以下逻辑错误:
- 函数参数设计不合理:算法需要传入链表头结点(如标准答案中的h),但学生使用了当前结点now和前一结点pre作为参数,这不符合单链表操作的常规设计(通常从头结点开始遍历),且调用该函数时需要额外处理头结点,容易出错。
- 数组初始化缺失:学生没有对visited数组进行初始化(全部置0),这会导致未定义行为(数组内容随机),从而可能错误删除或保留结点。
- 绝对值函数冗余:标准答案直接使用条件表达式处理绝对值,学生额外定义了my_abs函数,虽不影响正确性,但增加了复杂度(但根据规则不扣分)。
- 删除操作时未更新pre:在删除结点后,now被更新为pre->link,但pre未更新(应保持不变),这部分逻辑正确。但整体参数设计错误导致算法无法直接应用。
扣3分(主要因参数设计和初始化缺失)。

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

得1分。学生正确给出了时间复杂度和空间复杂度均为O(n),但空间复杂度应为O(n)(辅助数组大小n+1),时间复杂度应为O(m)(链表长度m,而非n)。学生误写为O(n),可能是识别错误或笔误(根据规则,若为误写则不扣分,但这里n和m含义不同,且上下文未体现误写,故扣1分)。

题目总分:3+1+5+1=10分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发