文章

77

粉丝

0

获赞

0

访问

7.1k

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


评分及理由

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

学生答案的基本设计思想正确:使用辅助数组记录每个绝对值是否首次出现,首次出现则保留,否则删除。这与标准答案的核心思想一致(空间换时间,使用辅助数组)。但学生答案中描述“出现次数若大于1则删除”不够准确(应为“大于0”或“非0”),但考虑到核心思路正确,且“大于1”可能是误写(实际应为“等于1”表示已出现过),因此不扣分。得3分。

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

学生给出的单链表结点数据类型定义正确,包括data和link字段,且link类型为指向结点的指针。但标准答案中使用了`typedef NODE *PNODE;`来定义指针类型,而学生答案未定义,但题目只要求“单链表结点的数据类型定义”,因此不强制要求定义指针类型。得2分。

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

学生算法描述基本正确,但存在以下逻辑错误:
1. 在删除结点时,学生代码直接执行`P->next = P->next->next;`,但未释放被删除结点的内存(缺少`free`操作),这会导致内存泄漏。标准答案中明确使用`free(r)`释放结点。
2. 学生代码中,参数使用`LNode *&L`(C++引用),但标准答案使用`PNODE h`(C语言指针),但题目允许使用C或C++,因此语法风格不扣分。但删除操作未释放内存是逻辑错误。
3. 学生代码中,循环条件为`while(P->next != NULL)`,但内部在删除结点后,P并未移动(只有在保留结点时P才后移),这可能导致逻辑正确,但未释放内存是严重错误。
扣分:未释放内存扣2分(因为内存管理是算法正确性的重要部分)。其他部分正确(包括辅助数组初始化、绝对值计算、条件判断等)。得6分(满分8分)。

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

学生正确说明空间复杂度为O(n)(辅助数组大小n+1),时间复杂度为O(n)(遍历链表)。但时间复杂度应为O(m)(m为链表长度),学生写为O(n)(n为数据绝对值的上限),这是错误。但根据上下文,可能是误写(因为n和m易混淆),且标准答案中时间复杂度为O(m),但学生答案中写O(n)可能意指线性复杂度,但表述不精确。扣1分。得1分。

题目总分:3+2+6+1=12分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发