首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
请设计一个队列,要求满足: 初始时队列为空; ②入队时,允许增加队列占用空间; ③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减; ④入队操作和出队操作的时间复杂度始终保持为O(1)。 请回答下列问题: 该队列是应选择链式存储结构
请设计一个队列,要求满足: 初始时队列为空; ②入队时,允许增加队列占用空间; ③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减; ④入队操作和出队操作的时间复杂度始终保持为O(1)。 请回答下列问题: 该队列是应选择链式存储结构
admin
2020-06-17
32
问题
请设计一个队列,要求满足:
初始时队列为空;
②入队时,允许增加队列占用空间;
③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减;
④入队操作和出队操作的时间复杂度始终保持为O(1)。
请回答下列问题:
该队列是应选择链式存储结构,还是应选择顺序存储结构?
选项
答案
顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析:要求①容易满足;链式存储方便开辟新空间,要求②容易满足:对于要求③,出队后的结点并不真正释放,用队头指针指向新的队头结点,新元素入队时,有空余结点则无须开辟新空间,赋值到队尾后的第一个空结点即可,然后用队尾指针指向新的队尾结点,这就需要设计成一个首尾相接的循环单链表,类似于循环队列的思想。设置队头、队尾指针后,链式队列的入队操作和出队操作的时间复杂度均为O(1),要求④可以满足。因此,采用链式存储结构(两段式单向循环链表),队头指针为front,队尾指针为rear。
解析
转载请注明原文地址:https://kaotiyun.com/show/VU3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
用P—V操作实现写优先读者一写者问题。
已知二叉树采用二叉链表方式存放,要求返回二叉树T的后序遍历访问的第一个结点,是否可不用递归且不用栈来完成?请简述原因。
如下图所示的AOE网,求:哪些是关键活动?
某计算机的(2ache共有16块,采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节,按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
栈S最多只能容纳4个元素,现在6个元素按A,B,C,D,E,F的顺序进栈,下列哪一个序列是可能的出栈序列()?
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:请说明系统并不一定死锁。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:请说明系统处于不安全状态;
设森林F中有三棵树,第一、第二、第三棵树的结点个数分别为N1,N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是()。
随机试题
在Access中,查询是数据库设计目的的体现,也就是说,数据库建立完成后,只有被使用者查询,才能真正体现数据的价值。()
白色念珠菌感染治疗中,错误的是
票据上的签章,为签名、盖章或者签名加盖章。法人和其他使用票据的单位在票据上的签章为:
若已知进入某除尘器的粉尘量为0.5g/s,除尘器除下的粉尘量为0.48g/s。则除尘器的全效率η为()。
【背景资料】某市政府投资工程,建设单位与施工单位按照《建设工程施工合同(示范文本)》签订了施工合同,采用可调价合同形式。工期20个月,项目监理机构批准的施工总进度计划如图3—1所示,各项工作在其持续时间内均按匀速进展,每月计划完成的投资(部分)见
产品策略中所研究的产品包括核心层、形式层、期望层、延伸层和()五个层次。
博闻强记的背功从哪里来?靠过目成诵的___________,这种人少之又少,如同凤毛麟角;再就是靠苦读苦背,“三更灯火五更鸡”,舍此没别的___________可走。填入划横线部分最恰当的一项是()。
Atwhichgatewilltheplanearrive?
Whatisthenearestvalueof:(0.16667×0.83333×0.33333)/(0.22222×0.66667×0.12500)?
PassageFourWhydidDr.Wranghamconducttheexperimentonratswhichdidnotrelyoncooking?
最新回复
(
0
)