文章

78

粉丝

0

获赞

0

访问

8.0k

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

(1)第一次遍历出2个链表的长度,长的链表移动到和短链表长度相同,再同时向后遍历,比较是否相同,查找起始位置,直到结束
(2)

node* find(node* str1,node* str2){
	int m=0,n=0;
	node* p1=str1,p2=str2;
	while(p1->next!=null){
		p1=p1->next;
		m++;
	}
	while(p2->next!=null){
		p2=p2->next;
		n++;
	}
	if(m>n){
		for(int i=0;i<m-n;i++){
			str1=str1->next;
		}
	}else{
		for(int i=0;i<n-m;i++){
			str2=str2->next;
		}
	}
	node* ans;
	while(str1->next!=null&&str2->next!=null){
		if(str1->data==str2->data){
			ans=str1;
		}
		str1=str1->next;
		str2=str2->next;
	}
	return ans;
}

(3)时间复杂度是O(n)


评分及理由

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

得分:4分

理由:学生的基本设计思想描述清晰准确,与标准答案一致。具体包括:①计算两个链表长度;②长链表先移动差值步数;③同步遍历比较。思路正确完整,因此得满分。

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

得分:5分

理由:算法整体框架正确,但存在以下逻辑错误:
1. 变量声明错误:node* p1=str1,p2=str2; 应该为 node *p1=str1, *p2=str2;(p2前缺少*),属于语法错误,扣1分。
2. 指针移动逻辑错误:在调整长链表位置时,直接移动str1和str2头指针(str1=str1->next),这会破坏原始链表头,应使用临时指针。扣2分。
3. 公共结点判断逻辑错误:在同步遍历时,仅比较结点数据(str1->data==str2->data)而非结点地址,且ans赋值逻...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发