首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某个任务的数据模型可以抽象为给定的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
2018-08-12
71
问题
某个任务的数据模型可以抽象为给定的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(reetype 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一一){ //查找失败,将x插入数据表 R[j+1]=R[j]; //元素后移 R[j+1]=x; //将x插入到原第i个集合最后一个元素之后 for(j=i;j≤k;j++)id.a[j]++; //修改索引表中各集合最后一个元素的下标 } 由于各集合元素个数不等,各块长度不等且块间无序,索引表中用数组表示,数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入(2,1 1.2)和(1,5.3),数据表前后状态如下: [*] 插入前,索引表中a数组的内容是3,6,12,插入后修改为4,8,14。
解析
转载请注明原文地址:https://kaotiyun.com/show/CMRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
对《魏玛宪法》的内容和影响叙述不正确的是()。
下列对近代社会思潮产生的先后顺序排列正确的是()。①人文主义②自由主义③理性主义④重商主义
编写判定给定的二叉树是否是二叉排序树的函数。
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
设一段正文由字符集{A,B,C,D,E,F)中的字母组成,这6个字母在正文中出现的次数分别为{12,18,26,6,4,34)。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成,试计算按哈夫曼编码压缩存储这段正文共需多少个字
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
下列叙述正确的个数是()。1)向二排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B一树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右子树的高度差的绝对值
m阶B一树是一棵()。
以下有关m阶B一树的说法中正确的有()。Ⅰ.每个结点至少有两棵非空子树Ⅱ.树中每个结点至多有m-1个关键字Ⅲ.所有叶子在同一层上Ⅳ.当插入一个数据项引起B-树结点分裂后,树长高一层
随机试题
女,75岁,右大腿卵圆窝部反复出现圆形包块10年。此次因便秘包块突出,用力还纳后右下腹持续疼痛伴呕吐就诊。查体:下腹压痛,肌紧张,叩诊肝浊音界缩小,肠鸣音消失。对诊断最有帮助的首选检查是
法洛四联症的4种病理变化中最重要的是
等直杆的受力情况如图5-1所示,则杆内最大轴力FNmax和最小轴力FNmin分别为()。
图4一1—13所示平面构架,不计各杆自重。已知:物块M重Fp,悬挂如图所示,不计小滑轮D的尺寸与重量,A、E、C均为光滑铰链,L1=1.5m,L2=2m。则支座B的约束力为()。[2013年真题]
某化工企业,液氨罐区发生了泄漏事故,已经造成了人员死亡,下列不属于该企业在事故应急救援阶段的基本任务的是()。
郑老师在教学过程中习惯根据教学要求提出相应问题,然后要求学生回答,并通过问答的形式来引导学生获取或巩固知识,郑老师所用的教学方法属于()。
全球粮食价格上涨,我国作为拥有众多人口的发展中大国,也在一定程度上受到影响。国家采取一系列措施确保粮食安全,包括()。
①据此,洪堡提出了青藏高原“热岛效应”理论 ②这不符合常理 ③早在18世纪末,德国科学家洪堡就发现,赤道附近的高山雪线,比中纬度的青藏高原许多高山的雪线低200米左右 ④故其热量较同纬度、同海拔高度的其他地区高得多,甚至比赤道附近的同海拔地区也
第一个表达文艺复兴教育思想的人是
以下程序的输出结果是_________。#include<stdio.h#defineFUDGE(y)2.84+y#definePR(A)printf("%d",(int)(A))#definePRINT1
最新回复
(
0
)