首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某个任务的数据模型可以抽象为给定的k个集合:S1,S2,…,Sk。其中Si(1≤i≤k)中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作,查找和插入时用一个二元组(i,x)来规定一个元素,i是集合的序号,x是元素值。设计一种恰当的
某个任务的数据模型可以抽象为给定的k个集合:S1,S2,…,Sk。其中Si(1≤i≤k)中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作,查找和插入时用一个二元组(i,x)来规定一个元素,i是集合的序号,x是元素值。设计一种恰当的
admin
2019-08-15
81
问题
某个任务的数据模型可以抽象为给定的k个集合:S
1
,S
2
,…,S
k
。其中S
i
(1≤i≤k)中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作,查找和插入时用一个二元组(i,x)来规定一个元素,i是集合的序号,x是元素值。设计一种恰当的数据结构来存储这k个集合的元素,并能高效地实现所要求的查找和插入操作。
(1)构造数据结构,并且说明选择的理由。
(2)若一组数据模型为S
1
={10.2,1.7,4.8,16.2},S
2
={1.7,8.4,0.5},S
3
={4.8,4.2,3.6,2.7,5.1,3.9},待插入的元素二元组为(2,11.2)和(1,5.3),按你的设计思想画出插入元素前后的数据结构状态。
选项
答案
借助于分块查找思想,在建立数据顺序表的同时,建立一索引表。数据表中按k个集合分块(元素个数不一定相等),索引表中有两个域,一是各集合最后一个元素在数据表中的位置(一维数组中的下标),二是集合的个数(k)。实现数据运算时,根据给定的二元组(i,x),首先在索引表中找到集合i的位置,然后在数据表中查找x。查到x,则查找成功,返回x在数据表中的位置,否则查找失败。若要插入,则将数据表中的数据后移,插入x,同时修改索引表。 typedef struct{datatype data;}rectype; typedef struct{ int a[]; //a数组容量够大,存储各集合最后一个数 据在数据表中的下标 int k; //集合个数 }index ; int SetSearch_Insert(rectype R[],index id,datatype x,int i){ //数据表R,查找第i个集合的元素x,若查找成功,返回其位置, //否则将其插入第i个集合 if(i<l∣∣i>id.k){printf(”无第%d个集合\n”,i);exit(0); } if(i==1)first=0; //first指向第i个集合在数据表的首址 else first=id.a[i一1]+1; last=id.a[i]; //last是第i个集合在数据表中的末址 for(j=first;j<last;j++)if(R[j]==x)return(j); //查找成功 for(J=id.a[id.k];j>id.A[i];j一一){ //查找失败,将x插入数据表 R[j+1]=R[j]; //元素后移 R[j+1]=x; //将x插入到原第i个集合最后一个元素之后 for(j=i;j≤k;j++)id.a[j]++; //修改索引表中各集合最后一个元素的下标 } 由于各集合元素个数不等,各块长度不等且块间无序,索引表中用数组表示,数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入(2,11.2)和(1,5.3),数据表前后状态如下: [*] 插入前,索引表中a数组的内容是3,6,12,插入后修改为4,8,14。
解析
转载请注明原文地址:https://kaotiyun.com/show/h0Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
到1869年为止,人类已发现了多少种化学元素()。
1962年2月,中共中央发出《关于改变农村人民公社基本核算单位问题的指示》,规定人民公社的基本核算单位是()。
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
庆历新政失败后,积贫积弱的局面一延其旧,改革议论不绝于朝野,神宗时任用王安石变法。回答问题:王安石变法中,对科举制度进行了改革,规定进士科专考()
宗教问题已成为某些国家和地区之间冲突的主要原因。信仰“真主”安拉,以《古兰经》为经典的宗教是()
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
若线性表最常用的运算是查找第i个元素及其前驱的值,则采用()存储方式节省时间。
关于DMA方式和通道方式,下列说法中错误的是()。
随机试题
马克思主义者认为,教育是一种()。
升麻、柴胡在补中益气汤中是
下列哪一种脂肪酸是合成前列腺素的前体
70号A级沥青的RTFOT试验结果如下表,请依表回答下列问题:关于沥青老化正确的解释是()。
政府对施工质量实施监督管理的主要手段是()。
乙企业应交的增值税为()元。甲企业收回委托加工材料的入账成本为()元。
甲公司2010年年末的流动资产总额为1200万元,流动负债总额为800万元,股东权益20000万元,负债总额30800万元;2010年的销售收入为5000万元。预计2011年销售收入增长率为25%。为此需要增加净经营长期资产300万元,根据有关情况分析,企
每股收益
为适应改革开放和社会主义现代化建设的需要,1985年中共中央颁发《关于教育体制改革的决定》,下放教育管理权,其中高等教育实行三级办学体制,这三级是指
______是C++语言程序的人口。
最新回复
(
0
)