文章

179

粉丝

0

获赞

0

访问

7.9k

头像
2009年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年9月23日 21:46
阅读数 56


评分及理由

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

得分:4分

理由:学生的基本设计思想与标准答案一致,都采用了双指针(快慢指针)的方法,通过一趟遍历找到倒数第k个结点。但学生在描述中提到“若第二个指针等于头指针+list,则返回0”,这里的“头指针+list”表述不清晰,可能是指头结点(即list指向的结点),但标准答案中是通过计数count是否小于k来判断k值是否超过链表长度,而学生的方法在代码中实际是通过fast指针是否提前为NULL来判断,思路正确但描述存在歧义,因此扣1分。

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

得分:4分

理由:学生的实现步骤基本正确,但步骤③中“判断slow与头指针是否相等”是不必要的,因为如果k值合法,slow最终指向的结点不可能是头结点(list指向的结点),而代码中实际是通过fast指针遍历k个结点时是否遇到NULL来判断k值是否合法,步骤描述与代码逻辑不完全一致,存在瑕疵,因此扣1分。

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

得分:4分

理由:学生的代码逻辑正确,能够通过一趟扫描找到倒数第k个结点,并正确处理k值超过链表长度的情况。但代码中存在两处问题:一是结构体类型名定义为Lode,但在link字段中使用了Lode *link,应该使用struct Lode *link或先typedef;二是fast和slow初始指向list(头结点),而标准答案中指针初始指向第一个数据结点,但学生的代码在逻辑上仍然正确,因为最终slow指向的是倒数第k个结点(从头结点开始算第k个,但题目中头结点是表头结点,不存储数据,而学生的代码中list是头指针,可能指向头结点,但代码中直接输出slow->data,如果slow指向头结点,则可能输出头结点的数据,这与题目要求不符)。不过,根据题目“带有表头结点的单链表”,list是头指针,指向头结点,头结点的data域可能无意义,但学生的代码在k值合法时slow指向的是倒数第k个数据结点(因为fast先移动k步,然后同步移动,直到fast为NULL,slow正好指向倒数第k个结点),逻辑正确。但结构体定义有误,扣1分。

题目总分:4+4+4=12分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发