首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某个任务的数据模型可以抽象为给定的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
48
问题
某个任务的数据模型可以抽象为给定的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
学硕统考专业
相关试题推荐
()时,为补充兵力,开拓财源,“料民于太原”(今山西西南部)。料民就是清查民数,以便于征兵,结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。
1890-1906,美南部各州纷纷制定法律或修改州宪法,对公民选举资格进行限定,部分州采用祖父条款,规定内战前有投票格的人,其后代不受新投票规则限制,但该条款被联邦最高法院否定,表明当时美国:
20世纪30年代,美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势,维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外的事务
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是()。
随机试题
断离肢体的保存方法正确的是
不寐实证的治法是
成人股骨颈的血液供应主要来源于
同温同压下,等质量的气体体积的大小决定于()。
《物权法》规定,除法律另有规定外,()代表国家行使国有财产的所有权。
中华人民共和国全国人民代表大会公告(第二号)第十届全国人民代表大会第一次会议于2003年3月15日选举:胡锦涛为中华人民共和国主席;曾庆红为中华人民共和国副主席。现予公告。
下列选项中,以登记作为物权取得的生效条件的是()。
设a1=4,an+1=,证明:存在,并求此极限.
I’minterestedinthecriminaljusticesystemofourcountry.Itseemstomethatsomethinghastobedone,ifwe’reto【B1】____
从四面八方
最新回复
(
0
)