首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某个任务的数据模型可以抽象为给定的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-01
51
问题
某个任务的数据模型可以抽象为给定的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: inI SetSearch_Insert(rectype R[],index id,datatype X,int i){ //数据表R,查找第i个集合的元素X,若查找成功,返回其位置; //否则将其插入第i个集合 if(i<1 || 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
id.A[i];j--)t //查找失败,将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/iNCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1945年,联合国成立之时,创始会员国共有()个国家。
1962年2月,中共中央发出《关于改变农村人民公社基本核算单位问题的指示》,规定人民公社的基本核算单位是()。
1947年英国通过《蒙巴顿方案》,随后印度和巴基斯坦独立,形成印巴分治局面,在克里米尔地区冲突埋下隐患,《蒙巴顿方案》中印巴分治的依据
近现代以来,国际关系中先后出现了维也纳体系、凡尔赛一华盛顿体系和雅尔塔体系。关于这三个体系共同点的表述不正确的是()。
1947年,刘邓大军千里跃进大别山,揭开了战略反攻的序幕。 据此回答问题:之所以把中原地区作为反攻的方向,主要是由于该地区()
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题:哪位皇帝的即位首次应用了秘密立储制?()
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
文件系统的主要目的是()。
CSMA/CA是如何实现“冲突避免”的?
假脱机技术(SPOOLing)中,被利用来做虚拟设备的是()。
随机试题
拉线应采用
A国某公司年度所得为200万元,其中150万元来自本国,50万元为B国分公司汇来的股息,A国实行超额累进税率,年所得100万元以下者税率为20%,所得超过100万元部分按25%计征。用全额免税法和累进免税法分别计算A国公司应缴纳的所得税额。
11个月男婴,弛张高热,咳嗽6天,精萎纳差,时有呕吐,周围血象白细胞26乘以十的九次方/L,查体:烦躁不安,气促,面色苍白,皮肤可见猩红热样皮疹,两肺可闻中小湿啰音。
A、15~18B、13~16C、8~16D、7~9E、3~8O/w型乳化剂的HLB值
经纪活动中的代理,是一种()代理活动。
在无水流冲刷和无冻胀的情况下,基础的埋置深度应在地面以下0.5m。( )
国际直接投资,是指一个国家的企业或个人对另一国企业部门进行的投资。方式有()。
生活生态位是指()。
关于设计建议奖时的注意事项,下列说法错误的是()。
关于法与正义的关系,说法正确的有()。
最新回复
(
0
)