首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某个任务的数据模型可以抽象为给定的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
46
问题
某个任务的数据模型可以抽象为给定的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
学硕统考专业
相关试题推荐
新中国成立初期,旨在完成民主革命遗留任务的运动是()。
“二战期间,美国研制了原子弹并用于实践;1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道;德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。
明清时期继续采取“重农抑商”的政策,结果导致了()。
标志着整风运动开始向反“右派”斗争转变的重要文件是()。
分析希腊大殖民运动发生的背景和影响。
1918年美国总统威尔逊提出“十四点原则”,内容有“海洋上的航行有绝对自由”、“取消一切经济障碍和确立贸易条件的平等”、“成立一个一般性的各国联合组织”。其最终目的是()。
1939年5、6月间,英国政府不顾德军的轰炸将33万联军撤到英国,这些部队成为日后反功的基于这就是著名的()。
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:随着商业的发展,唐朝在货币和金融方面有一些重要的进步,以下表述全面的是()
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
假脱机技术(SPOOLing)中,被利用来做虚拟设备的是()。
随机试题
三部门经济中,总需求的表达式为()
男性,36岁。高热12天,呼吸深快。血气分析:pH7.44,PaCO230mmHg,BE-5.8mmol/L。应考虑
A.胆总管结石继发胆管炎B.壶腹部肿瘤C.早期肝癌D.门脉高压症E.病毒性肝炎黄疸、胆囊增大和肝大
A.可吊销药品生产或经营企业的营业执照B.可吊销药品生产或经营企业的许可证C.可吊销医疗机构执业许可证D.可对构成犯罪的,依法追究刑事责任E.可吊销违法医师的执业医师证书对在药品购销活动中给予、收受贿赂,情节严重的,卫生行政管理部门
关于客户开户及交易编码的申请。当日分配的客户交易编码,期货交易所应当于()允许客户使用。
下列属于认知派学习理论的是()。
根据下面材料回答问题。2008年一季度企业家信心指数与上季度相比有下降的是()。
宏达公司的业绩比腾飞公司好。但是因为鹏程公司的业绩比天城公司的业绩好,所以宏达公司的业绩比天城公司好。以下除了哪项外,都可以成为题干成立的一个必要前提?
甲将乙的联系方式发到自己的微信朋友圈,声称乙欠钱不还,是个骗子,经查,甲所说与事实完全不符。甲的行为侵害了乙的()(2018年一专一第29题,2018年一法专一第19题)
A、Whenheiswiththeboyalone.B、Whenheteachestheboyalesson.C、Whenhesendstheboyhomeaspunishment.D、Whenheworks
最新回复
(
0
)