【特惠】26考研
红包
【考研】专业课HOT
26考研
【MBA】在职考研
【申硕】同等学力
【报录比】查询
计划
【分数】录取线
计划
【高分】抢跑课
预备
【词汇】5500大纲
免费
【AI】智能择校
免费
【资料】考研大纲
精
扫码加入训练营
牢记核心词
学习得礼盒
【题目】
41.(15分)用单链表保存m个整数,结点的结构为:,且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表head如下:
则删除结点后的head为:
要习之:
(1)给出算法的基本设计思想。
(2)使用C或C++语言,给出单链表结点的数据类型定义。
(3)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
(4)说明你所设计算法的时间复杂度和空间复杂度。
【答案要点】:
(1)算法的基本设计思想
算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值,从而只需对链表进行一趟扫描。
因为|data|≤n,故辅助数组q的大小为n+1,各元素的初值均为0。依次扫描链表中的各结点,同时检查q[|data|]的值,如果为0,则保留该结点,并令q[|data|]=1;否则,将该结点从链表中删除。
(2)使用C语言描述的单链表结点的数据类型定义
typedef struct node {
int data:
struct node *link:
} NODE;
typedef NODE*PNODE;
(3)算法实现
void func(PNODE h,int n)
{ PNODE p:h,r;
int*q,m;
q=(int*) malloc(sizeof(int)*(n+1));//申请n+1
//个位置的
//辅助空间
for(int i=0;i
*(q+i)= 0;
while(p->link!=NULL)
{ m=p->link->data>0 ? p->link->data:-p->link一>data;
if(*(q+m)==0) //判断该结点的data是否已
//出现过
{ *(q+m)=1; //首次出现
p=p->link; //保留
}
else //重复出现
{ r=p->link; //删除
p->link=r->link;
free(r);
}
}
free(q);
}
【(1)、(2)、(3)的评分说明】
①若考生设计的算法满足题目的功能要求且正确,则(1)、(3)根据所实现算法的时间复杂度给分,细则见下表:
②若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路,但在算法实现中能够表达出算法思想且正确的,可参照①的标准给分。
③若算法的基本设计思想描述或算法实现中部分正确,可参照①中各种情况的相应给分标准酌情给分。
④若考生给出的单链表结点的数据类型定义与题目中所给的结点形式不完全相同,酌情给分。
⑤参考答案中只给出了使用C语言的版本,使用C++语言的答案视同使用C语言。
(4)参考答案所给算法的时间复杂度为O(m),空间复杂度为O(n)。
【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致,可给分。
本文关键字: 用单链表保存m个整数
添加班主任领资料
添加考研班主任
免费领取考研历年真题等复习干货资料
推荐阅读
2024年考研初试考试结束后,相信同学们都比较关心考后的真题以及答案了。新东方在线第一时间为大家整理了本次考试对应的真题以及答案解
2024年考研初试考试结束后,相信同学们都比较关心考后的真题以及答案了。新东方在线第一时间为大家整理了本次考试对应的真题以及答案解
2024年考研初试考试结束后,相信同学们都比较关心考后的真题以及答案了。新东方在线第一时间为大家整理了本次考试对应的真题以及答案解
2024年考研初试考试结束后,相信同学们都比较关心考后的真题以及答案了。新东方在线第一时间为大家整理了本次考试对应的真题以及答案解
2024年考研初试考试结束后,相信同学们都比较关心考后的真题以及答案了。新东方在线第一时间为大家整理了本次考试对应的真题以及答案解
资料下载
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
新东方在线考研资料合集
下载方式:微信扫码,获取网盘链接
目录:
1.2013-2023年近10年政数英真题及解析PDF版(新东方)
2.2013-2023年专业课考试历年真题及解析PDF版
3.24考研复习备考资料大合集:大纲+备考资料+词汇书+考前押题+自命题
资料介绍:
1.2013-2023年近10年政数英真题及解析PDF版(新东方)
、
2.2013-2023年专业课考试历年真题及解析PDF版
3.24考研复习备考资料大合集
3.24考研复习备考资料:考研大纲
3.24考研复习备考资料:政数英备考资料+自命题真题
------------------
考研备考过程中,尤其是专业课部分,参考往年的考试真题,对于我们的复习有更好的帮助。北京大学考研真题资料都有哪些?小编为大家进行了汇总。
北京大学考研真题资料-公共课
北京大学考研真题资料-专业课
以上就是关于“北京大学考研真题资料下载(历年汇总)”的整理,更多考研资料下载,请关注微信获取下载地址。
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
阅读排行榜
相关内容