Python二级--循环队列专题

Python二级--循环队列专题,第1张

Python二级--循环队列专题 知识点

        循环队列是线性结构、顺序存储结构的队列。故其一开始创建,空间大小就已经确定,无论是入队还是退队,都是在确定空间中执行,当循环队列满时,再执行插入会产生“上溢”错误,当循环队列为空时,再执行删除会产生“下溢”错误。空循环队列的初始状态为front=rear=0,当入队一个元素时,rear=rear+1,表现在循环队列中,rear=m到了rear=1的位置,如上图的第二个,再入队一个元素,rear=rear+1=2。退队一个元素,即让front=front+1,表现在循环队列中就是从front=m到front=1,此时原来位置1的元素被删除。

        通过以上论述,可知,入队 *** 作指针rear,退队 *** 作front。而且front和rear的大小不能确定,可能出现以下3种情况,分别为

①front=rear,此时循环队列可能为空,也可能为满。

②front

③front>rear,如上图第2个所示,此时循环队列中的元素为(rear+m-front)个(rear代表左边的元素个数,m-front代表右边的元素个数)

1.循环队列的存储空间为 Q(1:50) ,初始状态为 front=rear=50 。经过一系列正常的入队与退队 *** 作后, front=rear=25 ,此后又插入一个元素,则循环队列中的元素个数为( A)

A.1,或50且产生上溢错误

B.51

C.26

D.2

解析:front=rear说明此时循环队列可能为空也可能满。当循环队列为空时,再插入一个元素此时循环队列有1个元素;当循环队列为满时,再插入一个元素会导致上溢错误。故选A。

2.设循环队列的存储空间为Q(1:m),初始状态为空。现经过一系列正常的入队与退队 *** 作后,front=m,rear=m-1,此后从该循环队列中删除一个元素,则队列中的元素个数为(B)

A.m-1

B.m-2

C.0

D.1

解析:front>rear,此时循环队列中元素有(rear+m-front)=(m-1+m-m)=(m-1)个元素,再删除一个元素,此时有(m-2)个元素。故选B。

3.设循环队列的存储空间为Q(1:m),初始状态为front=rear=m。现经过一系列正常的入队与退队 *** 作后,front=30,rear=10。现在要在该循环队列中作顺序查找,最坏情况需要比较的次数为(D)

A.19

B.20

C.m-19

D.m-20

解析:循环队列最终元素个数取决于最后front和rear的位置。由于front=30>20=rear,故此时循环队列中元素个数为(rear+m-front)=(10+m-30)=(m-20)个元素。又考虑最坏情况查找元素,故考虑每个元素都比较完才找到的情况,即要进行(m-20)次。故选D。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://www.outofmemory.cn/zaji/5580309.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-14
下一篇 2022-12-14

发表评论

登录后才能评论

评论列表(0条)

保存