首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某个任务的数据模型可以抽象为给定的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
63
问题
某个任务的数据模型可以抽象为给定的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
学硕统考专业
相关试题推荐
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是:仅当需要访问某页面时,如果它不在内存,把它调入内存。按照这个思路,将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理,也可以产生类似的算法,不妨
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
已知某CPU有16根地址线、8根数据线,并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
以下说法中错误的是()。
大部分文件系统以硬盘作为文件存储器。某一个文件系统中,其磁盘物理块的大小为512B,有一个文件,包含了590个逻辑记录,每个记录占255B;其中,为检索方便,采用成组法存储,在每个物理块上只存放2个记录。,文件A在该文件目录中的位置如下图所示。
设有3阶B一树,如图1-4所示。在该B一树上依次插入关键字33和97。试画出两次插入后的B-树。
随机试题
跨国公司制定企业项目规划时考虑全球经济发展态势,这体现了国际企业战略的()
男,40岁,烧伤后3小时入院。疼痛剧烈,感口渴。面色苍白,心率150次/分,BP85/65mmHg,头颈部、躯干部布满大小不等水疱,可见潮红创面,两上肢呈焦黄色,无水疤。该病人的烧伤总面积估计为
周期、频率、角频率三者之间的关系正确的是()。
《会计法》在规定单位负责人为本单位会计行为责任主体的同时,也规定了会计机构、会计人员和其他人员的职责、法律责任。()
天然橡胶期货交易主要集中在( )。
下列各项中,会影响在建工程项目成本的有()。
揭示事物发展具有前进性和曲折性相统一的规律是()。
WriteinyourANSWERSHEETONEanoteofabout50-60wordstoafriendofyoursbasedonthefollowinggivensituation:Beforey
Nextweek,accordingtoUnitedNationsprojections(预测),theworldwillpasssevenbillioninpopulation,andbytheendofthis
A、Hewelcomeshertelephoninganytime.B、Hewilltelephoneherasoftenashecan.C、Heisnotthatfarawayifshewantstovi
最新回复
(
0
)