首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
请设计一个队列,要求满足: 初始时队列为空; ②入队时,允许增加队列占用空间; ③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减; ④入队操作和出队操作的时间复杂度始终保持为O(1)。 请回答下列问题: 该队列是应选择链式存储结构
请设计一个队列,要求满足: 初始时队列为空; ②入队时,允许增加队列占用空间; ③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减; ④入队操作和出队操作的时间复杂度始终保持为O(1)。 请回答下列问题: 该队列是应选择链式存储结构
admin
2020-06-17
31
问题
请设计一个队列,要求满足:
初始时队列为空;
②入队时,允许增加队列占用空间;
③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减;
④入队操作和出队操作的时间复杂度始终保持为O(1)。
请回答下列问题:
该队列是应选择链式存储结构,还是应选择顺序存储结构?
选项
答案
顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析:要求①容易满足;链式存储方便开辟新空间,要求②容易满足:对于要求③,出队后的结点并不真正释放,用队头指针指向新的队头结点,新元素入队时,有空余结点则无须开辟新空间,赋值到队尾后的第一个空结点即可,然后用队尾指针指向新的队尾结点,这就需要设计成一个首尾相接的循环单链表,类似于循环队列的思想。设置队头、队尾指针后,链式队列的入队操作和出队操作的时间复杂度均为O(1),要求④可以满足。因此,采用链式存储结构(两段式单向循环链表),队头指针为front,队尾指针为rear。
解析
转载请注明原文地址:https://jikaoti.com/ti/LNDjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
把程序地址空间中使用的逻辑地址变成内存中物理地址称为()。
关于分页系统,回答下列问题:设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIFO)和最近未使用页面置换算法(LRU)下,产生缺页的次数各是多少?(画
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,一1,4,一4,…,j2,一j2(j0时,Hi=(H(key)+di)%m当di
在集中式总线仲裁中,()方式响应时间最快。
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。当指令寻址方式由操作码指出时,直接和间接寻址可寻址的主存空
已知AOE网中顶点v1,v2,v3,…v7分别表示7个时间,有向线段a1,a2,a3,…a10。分别表示10个活动,线段旁的数值表示每个活动花费的天数,如图10-1所示。请填写表10-1、表10-2两个表格,并用顶点序列表示出关键路径,给出关键活动。
利用栈求表达式的值时,设立运算数栈OPND。假设OPND只有两个存储单元,在下列表达式中,不发生溢出的是()。
某银行的营业厅有多个柜员窗口,可以同时办理业务。银行的营业厅中安排有n张座椅供储户休息等候。每个储户在进入营业厅时会在排队机上取得一个号码,若此前没有客户,则排队机就会唤醒一个柜员为储户服务,当没有储户时柜员便可以休息。若储户较多,则所有柜员均会参与服务,
假定站点A和B在同一个10Mbit/s以太网的网段上,这两个站点之间的传播时延为225bit时间。现假定A开始发送一帧,并且在A发送结束之前B也发送一帧。如果A发送的是以太网所允许的最短的帧,试问:在(1)中的站点A和B在t=0时同时发送了数据帧。当t
随机试题
林明德是某在线销售摄影器材企业的管理人员,于2017年初随机抽取了100名网站注册会员,准备使用Excel分析他们上一年度的消费情况。根据下列要求,帮助他运用已有的数据完成这项工作。隐藏“2016年消费”工作表,将“各年龄段人数”工作表置于所有工作表最
病历:女性,17岁,高中生。三个月前无明显原因出现失眠、上课时注意力不集中,主动要家长给介绍男朋友,两个月发展到不去读书,在街上闲游,住院前一个月常半夜高歌、自言自语、扮鬼脸、做怪动作、照镜子、痴笑,有时头插鲜花,甚至赤身裸体、将家中玻璃窗打碎、喝痰盂中
试分析路透社经久不衰的原因。
加密算法和解密算法是在一组仅有合法用户知道的密码信息的控制下进行的,该密码信息称为________。
A.3%过氧化氢液B.0.12%氯己定C.25%甲硝唑凝胶D.2%碳酸氢钠液E.碘甘油目前公认最成熟的控制菌斑的含漱药物为
融资性售后回租服务,按照“融资租赁服务”征收增值税。()
汇总记账凭证账务处理程序的适用范围是()。
甲公司系2016年12月在深圳证券交易所挂牌的上市公司,主要从事手机、彩色电视机的生产和销售,按单项存货计提存货跌价准备。XYZ会计师事务所接受委托对该公司2017年年度财务会计报告进行审计。在审计过程中,该事务所对以下交易或事项及其处理提出了异议:(1
下列关于t分布的表述,错误的是()
Theeconomicsituation(willimprove)giventhatthereis(forecasttobe)less(unemployment)andclosuresthan(inpreviousye
最新回复
(
0
)