首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
请设计一个队列,要求满足: 初始时队列为空; ②入队时,允许增加队列占用空间; ③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减; ④入队操作和出队操作的时间复杂度始终保持为O(1)。 请回答下列问题: 该队列是应选择链式存储结构
请设计一个队列,要求满足: 初始时队列为空; ②入队时,允许增加队列占用空间; ③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减; ④入队操作和出队操作的时间复杂度始终保持为O(1)。 请回答下列问题: 该队列是应选择链式存储结构
admin
2020-06-17
25
问题
请设计一个队列,要求满足:
初始时队列为空;
②入队时,允许增加队列占用空间;
③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减;
④入队操作和出队操作的时间复杂度始终保持为O(1)。
请回答下列问题:
该队列是应选择链式存储结构,还是应选择顺序存储结构?
选项
答案
顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析:要求①容易满足;链式存储方便开辟新空间,要求②容易满足:对于要求③,出队后的结点并不真正释放,用队头指针指向新的队头结点,新元素入队时,有空余结点则无须开辟新空间,赋值到队尾后的第一个空结点即可,然后用队尾指针指向新的队尾结点,这就需要设计成一个首尾相接的循环单链表,类似于循环队列的思想。设置队头、队尾指针后,链式队列的入队操作和出队操作的时间复杂度均为O(1),要求④可以满足。因此,采用链式存储结构(两段式单向循环链表),队头指针为front,队尾指针为rear。
解析
转载请注明原文地址:https://jikaoti.com/ti/LNDjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。要求:描述算
如下图所示的AOE网,求:哪些是关键活动?
测得一个以太网数据的波特率是40Mbps,那么其数据率是()。
如下图所示为一个TCP主机中的拥塞窗口的变化过程,这里最大数据段长度为1024字节,请回答如下问题:该TCP协议的初始阀值是多少?为什么?
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;};将两个升序单链表归并为一个升序单链表。
以下关于计算机存储器件的叙述,()是不正确的。
假定在一个处理机上执行的操作如下:这些作业假定按A、B、C、D、E次序先后几乎同时(时间差相对时间片大小忽略不计)到达。(1)给定相应的图示来说明分别用FcFS、RR(时间片=1)、SJF和非抢占优先调度算法(最小优先数有最高优先权)调度这些作业的情
下列关于RISC的叙述中,错误的是()。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:请说明系统并不一定死锁。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离1w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
随机试题
在某医院的科普活动中,小李准备使用演示文稿介绍关于水的知识。相关素材存放在考生文件夹下,参考“PPT参考效果.docx”中的示例,按下列要求帮助小李完成演示文稿的制作:将第5张和第10张幻灯片的版式修改为“两栏内容”,并分别在右侧栏中插入考生文件夹下的
粪便镜检白细胞>15个/高倍镜视野提示
非法转让土地,是指违反法律规定,将土地权利完全或部分地转移给他人的行为。()
【背景资料】施工单位承建了某大桥工程,该大桥桥址位于两山体之间谷地,跨越一小河流,河流枯水期水深0.5m左右,丰水期水深2m左右,地面以下地层依次为黏土、砂砾、强风化砂岩。该桥基础原设计为40根钻孔灌注桩,桩长12.0~13.8m不等。施工中发生如下事件
完善客户纠纷处理机制,及时化解相关矛盾纠纷的主体是()。
健全完善我国商业银行内部控制体系应当包括的内容是()。
物流中心能否发挥作用的关键是()。
某企业安排30名职工参加体检,其中男性职工的近视比例大于10%小于11%,女性职工的近视比例在20%~30%之间。问男性职工中不近视的人比女性职工中不近视的人多几人?
ShoppinghabitsintheUnitedStateshavechangedgreatlyinthelastquarterofthe20thcentury.【C1】______inthe1900smos
A、doctorswithmuchexperience.B、educatorswithspecialtraining.C、experiencedhousewiveswithnospecialtraining.D、womenwi
最新回复
(
0
)