首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
请设计一个队列,要求满足: 初始时队列为空; ②入队时,允许增加队列占用空间; ③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减; ④入队操作和出队操作的时间复杂度始终保持为O(1)。 请回答下列问题: 该队列是应选择链式存储结构
请设计一个队列,要求满足: 初始时队列为空; ②入队时,允许增加队列占用空间; ③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减; ④入队操作和出队操作的时间复杂度始终保持为O(1)。 请回答下列问题: 该队列是应选择链式存储结构
admin
2020-06-17
30
问题
请设计一个队列,要求满足:
初始时队列为空;
②入队时,允许增加队列占用空间;
③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减;
④入队操作和出队操作的时间复杂度始终保持为O(1)。
请回答下列问题:
该队列是应选择链式存储结构,还是应选择顺序存储结构?
选项
答案
顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析:要求①容易满足;链式存储方便开辟新空间,要求②容易满足:对于要求③,出队后的结点并不真正释放,用队头指针指向新的队头结点,新元素入队时,有空余结点则无须开辟新空间,赋值到队尾后的第一个空结点即可,然后用队尾指针指向新的队尾结点,这就需要设计成一个首尾相接的循环单链表,类似于循环队列的思想。设置队头、队尾指针后,链式队列的入队操作和出队操作的时间复杂度均为O(1),要求④可以满足。因此,采用链式存储结构(两段式单向循环链表),队头指针为front,队尾指针为rear。
解析
转载请注明原文地址:https://kaotiyun.com/show/VU3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。设计该机微指令的格式,要求给出
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
(某系统有三个进程P1,P2,P3并发工作,其中P1执行过程中需要使用资源S3,S1;P2需要使用资源S1,S2;P3需要使用资源S2,S3。如果进程推进过程中对资源分配不加以限制,会导致什么结果,为什么?
某计算机系统的内存储器由(2ache和主存构成,Cache的存取周期为45纳秒,主存的存取周期为200纳秒。已知在一段给定的时间内,CPU共访问内存4500次,其中340次访问主存。问:Cache的命中率是多少?
关于分页系统,回答下列问题:在页表中,哪些数据项是为实现换页而设置的?
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:设该Cache的命中率为98%,如果Cache的速度是主存的5倍,则该机采用Cache时存储系统的速度是不采用
已知4位有效信息为1010,试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码,要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码,生成多项式G(x)=1011。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
某银行的营业厅有多个柜员窗口,可以同时办理业务。银行的营业厅中安排有n张座椅供储户休息等候。每个储户在进入营业厅时会在排队机上取得一个号码,若此前没有客户,则排队机就会唤醒一个柜员为储户服务,当没有储户时柜员便可以休息。若储户较多,则所有柜员均会参与服务,
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
随机试题
认为游戏是儿童从行动中获得机体愉快的手段的是()
使用烤灯照射创面时,灯距和照射时间为()。
在市场经济中,由于企业的理财主体更加细化和多元化,因此股东、债权人、企业经营者在企业中承担着最大的权力、义务、风险和报酬。()
脑的最古老部位是()
下列具有意动用法的句子是()。
你是铁路公安处的工作人员,有人在铁路两旁摆放烟花爆竹,故单位要你组织一次有关安全教育知识的宣传活动,你怎么组织?
关于《务限法》说法不正确的是()。
下面关于网络信息安全的一些叙述中,不正确的是
在SQL语言中,一个基本表的定义一旦被删除,则与此表相关的下列内容中哪一个(些)也自动被删除或失效?I.此表中的数据Ⅱ.此表上建立的索引Ⅲ.此表上建立的视图
A、Thesteamertookhimtotheharbor.B、Hewasleftalonethere.C、Hewassaved.D、Noneoftheabove.C
最新回复
(
0
)