文章
179
粉丝
0
获赞
0
访问
41.9k
2019年计算机学科专业基础综合试题 - 第41题回答
1）题目要求的是从链表的第p个结点之后的元素从后到前相隔着插入在前一半的元素之间。因此我先可以把第p个结点之后的链表先求逆序，然后通过标记他的起始点，依次往前插入。这样可以保证空间复杂度O(1)。因此，我们需要多个指针分别记录下当前要插入和被插入的位置。
2）
void func(NODE *L, int key){
if(L==NULL)return;
int *p,*q, *r;
p=L->next;
q=L->next;
while(key-- > 0){
q=q->next;
p=p->next;
}
p->next = NULL;
while(q->next){
r = q->next;
q->next=p->next;
p->next=q;
q=r;
}
}
3)O(1), O(1)
评分及理由
（1）得分及理由（满分3分）
得分：1分
理由：学生基本理解了需要将链表后半部分反转并插入前半部分，但设计思想描述不够清晰准确。没有明确说明如何找到链表的中点（下中位数点），也没有完整描述三步流程（找中点、反转后半段、合并）。此外，学生错误地引入了参数"key"和"p"的概念，与题目要求不符。
（2）得分及理由（满分8分）
得分：2分
理由：代码存在多处严重逻辑错误：
- 函数参数错误地引入了key参数，题目要求只处理整个链表
- 指针p和q的移动逻辑错误，无法正确找到链表中点
- 反转部分的逻辑不完整且错误
- 合并部分的逻辑完全缺失
- 代码语法错误（int *p,*q, *r应为NODE *）
- 缺少关键注释
虽然代码体现了反转链表的部分思路，但整体实现与题目要求相去甚远。
（3）得分及理由（满分2分）
得分：0分
理由：学生回答"O(1), O(1)"，这显然是错误的。正确的算法时间复杂度应该是O(n)，而空间复杂度是O(1)。学生没有正确分析时间复杂度。
题目总分：1+2+0=3分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发