首页 26考研 在职考研 直播好课 大纲冲刺

新东方在线 > 考研 > 计算机 > 考研计算机真题 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

41.(15分)用单链表保存m个整数，结点的结构为

2021-07-25 07:57:00来源：

　　【题目】

　　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个整数

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
双12 MBA 优惠券 0元学 院校库

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

真题解析

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10