首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某个任务的数据模型可以抽象为给定的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
59
问题
某个任务的数据模型可以抽象为给定的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
学硕统考专业
相关试题推荐
下列哪一个不是罗马王政时代的管理机构?()
论述欧洲一体化的进程及影响。
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
()是二战后一个调整各国贸易关系的法律框架,又是一个进行多边贸易谈判、争夺市场的场所,还是一个调解和解决争议的机构。
记载了用竿标日测影以求日高的方法,并认识了勾股定理的算书是()。
分析希腊大殖民运动发生的背景和影响。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
随机试题
A上市公司于2012年3月31日通过定向增发本公司普通股对B公司进行合并,取得B公司80%股权。假定不考虑所得税影响,该项业务的有关资料如下:(1)2012年3月31日,A公司通过定向增发本公司普通股,以2股换1股的比例自B公司原股东C公司处取得了B公司
患者男性,29岁,农民。以高热、周身疼痛起病,病后第6天死于顽固性休克,经尸体解剖发现垂体前叶明显充血、出血、坏死,肾脏肿大,间质极度水肿、充血,全身小血管内皮细胞肿胀,以后腹膜、纵隔水肿为主要损害。根据尸解所见诊断为( )
A、芹菜素B、柚皮素C、木犀草素D、大豆素E、山柰酚能与氯化锶反应生成黑色沉淀的是()
《医疗事故处理条例》将医疗事故分为
当投标单位在编制投标报价时,发现工程量清单上的工程量与施工图工程量不一致,而招标文件明确不允许对工程量进行调整的,应()。
试述起重机静载试验的目的、方法和合格标准。
关于“继发性妄想”,下列说法中不正确的是()。
发展文化产业,需要努力奏响高雅文化主旋律,以先进文化引领新风尚,以优秀文化作品教育大家,服务社会,不断为广大人民提供更好的精神食粮。奏响文化主旋律需要()
统计性歧视是指将一个群体的典型特征判断为群体中的个体具有的特征,并将此特征作为对个体特征的评价和描述。根据上述定义,下列选项中属于统计性歧视现象的是()。
创建一个显示“选项”的菜单项对象mi的正确语句是______。
最新回复
(
0
)