首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某个任务的数据模型可以抽象为给定的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
42
问题
某个任务的数据模型可以抽象为给定的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
学硕统考专业
相关试题推荐
1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
汉建武二十四年(公元48年)匈奴()被南边八部拥立为南单于,他袭用其祖父呼韩邪单于的称号,请求内附,得到东汉的允许。从此以后,匈奴分裂为南北二部。
提出电磁感应定律的是物理学家()。
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:下列关于隋唐钱币的表述,不正确的是()
下列选择中,()不是操作系统关心的主要问题。
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1MB,按字节编址,缓存容量为32KB,采用组相联方式进行地址映射与变换,主存与缓存的每一块为64B,缓存共分8组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)
假脱机技术(SPOOLing)中,被利用来做虚拟设备的是()。
随机试题
一对齿轮啮合传动,只要其压力角相等,就可以正确啮合。()
结合自身的实际情况,谈谈影响人格形成的诸因素。
下列民事权利救济方式中,属于公力救济的是()。
在采用工程量清单计价的方式下,工程竣工结算的编制内容中有关费用的计算应遵循的原则包括()。
【背景资料】某工业设备安装有限公司承包了一工业锅炉房机电设备安装工程,锅炉为散装。由于设备到货拖延,施工工期非常紧张。项目部总工程师编制的试运转方案中,对于锅炉的水处理系统没有提出具体明确的要求;并且要求为了缩短试运转周期,附属设备和锅炉主体一起
个人化是指()。
交换机作为VLAN的核心,提供了哪些智能功能?_______
每年年终,太平洋公司都会给在职员工发放年终奖金,公司会计小任负责计算工资奖金的个人所得税并为每位员工制作工资条。按照下列要求完成工资奖金的计算以及工资条的制作:在工作表“员工基础档案”中,利用公式及函数依次输入每个学生的性别“男”或“女”,出生日期“X
AnIndiananthropologist,ChandraThapar,madeastudyofforeigncultures,whichhadcustomssimilarto【C1】______ofhisnative
A、Ithasafixedrhythm.B、Itissimilartothetraditionaljazz.C、Itisfreeandspontaneous.D、Itistypicallyanelectronic
最新回复
(
0
)