一、单项选择题
————————————————————
————————————————————
解析:栈和队列的逻辑结构都是线性结构,都可以采用顺序存储或链式存储,C显然也错误。只有D才是栈和队列的本质区别,限定表中插入和删除操作位置的不同。
正确答案:D
————————————————————
————————————————————
解析:队列“先进先出”的特性表现在:先进队列的元素先出队列,后进队列的元素后出队列,进队列对应的是插入操作,出队列对应的是删除操作。Ⅰ和IⅣ均正确。
正确答案:B
————————————————————
————————————————————
解析:删除队头元素即出队,是队列的基本操作之一,所以选D。
正确答案:D
————————————————————
————————————————————
解析:队列的入队顺序和出队顺序是一致的,这是和栈不同的。
正确答案:B
————————————————————
————————————————————
解析:数组下标范围0~n,因此数组容量为n+1。循环队列中元素入队的操作是rear=(rear+1)mod maxsize,题中maxsize=n+1。因此入队操作应为rear=(rear+1) mod (n+1)。
正确答案:D
————————————————————
————————————————————
解析:队列的长度为(rear-front+maxsize) %maxsize=(rear-front+21)%21=16。这种情况和front指向当前元素,rear指向队尾元素的下一个元素的计算是相同的。
正确答案:B
————————————————————
————————————————————
解析:循环队列中,每删除一个元素,队首指针front=(front+1)%6,每插入一个元素,队尾指针rear= (rear+1)%6。上述操作后,front=0,rear=3。
正确答案:B
————————————————————
————————————————————
解析:当队列中只有一个元素时,front 指向该元素的前一个位置,rear指向该元素,因此当队列为空时,队首指针等于队尾指针,这样第一个元素进队后,才能符合题目要求。
正确答案:D
————————————————————
————————————————————
解析:既然不能附加任何其他数据成员,只能采用牺牲一个存储单元的方法来区分是队空还是队满,约定以“队列头指针在队尾指针的下一位置作为队满的标志”,因此选C。选项A是判断队列是否空的条件,选项B和D都是干扰项。
正确答案:C
————————————————————
————————————————————
解析:若用(rear+1)%(n+1)==front作为队满标志,则说明题目采用了牺牲一个存储单元的方法来区分队空和队满,因此可用front==rear作为队空标志。
正确答案:A
————————————————————
————————————————————
解析:虽然链式队列采用动态分配方式,但其长度也受内存空间的限制,不能无限制增长。顺序队列和链式队列的进队和出队时间均为O(1)。顺序队列和链式队列都可以进行顺序访问。对于顺序队列,可通过队头指针和队尾指针计算队列中的元素个数,而链式队列则不能。
正确答案:D
————————————————————
————————————————————
解析:因为队列需在双端进行操作,所以选项C和D的链表显然不太适合链队。对于A,链表在完成进队和出队后还要修改为循环的,对于队列来讲这是多余的(画蛇添足)。对于B,因为有首指针,所以适合删除首结点;因为有尾指针,所以适合在其后插入结点。
正确答案:B
————————————————————
————————————————————
解析:因为非循环双链表只带队首指针,所以在执行入队操作时需要修改队尾结点的指针域,而查找队尾结点需要O(n)的时间。B、C和D均可在O(1)的时间内找到队首和队尾。
正确答案:A
————————————————————
————————————————————
解析:因为在队头做出队操作,为便于删除队头元素,所以总是选择链头作为队头。
正确答案:A
————————————————————
————————————————————
解析:队列用链式存储时,删除元素从表头删除,通常仅需修改头指针,但若队列中仅有一个元素,则尾指针也需要被修改,当仅有一个元素时,删除后队列为空,需修改尾指针为rear=front。
正确答案:D
————————————————————
————————————————————
解析:插入操作时,先将结点x插入到链表尾部,再让rear指向这个结点x。C的做法不够严密,因为是队尾,所以队尾x->next必须置为空。
正确答案:D
————————————————————
————————————————————
解析:依题意,进队操作是在队尾进行,即链表表头。题中已明确说明链表只设头指针,也即没有头结点和尾指针,进队后,循环单链表必须保持循环的性质,在只带头指针的循环单链表中寻找表尾结点的时间复杂度为O(n),所以进队的时间复杂度为O(n)。
正确答案:A
————————————————————
————————————————————
解析:此类题可对各选项进行模拟,假设队列为Q1和Q2。对于A,元素依次入队Q1,然后依次出队。对于B,5最先出队,只可能是1,2,3,4入队Q1,,5入队Q2,然后5出队,只能得到5,1,2,3,4。对于C,1,2,5入队Q1,3,4入队Q2,然后按要求出队。D的分析同C。
正确答案:B
————————————————————
————————————————————
解析:使用排除法。先看可由输入受限的双端队列产生的序列:设右端输入受限,1,2,3,4依次左入,则依次左出可得4,3,2,1,排除A;左出、右出、左出、左出可得到4,1,3,2,排除B;再看可由输出受限的双端队列产生的序列:设右端输出受限,1,2,3,4依次左入、左入、右入、左入,依次左出可得到4,2,1,3,排除D。
正确答案:C
————————————————————
————————————————————
解析:本题的队列实际上是一个输出受限的双端队列,如图3.11所示。A操作:a左入(或右入)、b左入、c右入、d右入、e右入。B操作:a左入(或右入)、b左入、c右入、d左入、e右入。D操作: a左入(或右入)、b左入、c左入、d右入、e左入。C操作: a左入(或右入)、b右入、因d未出,此时只能进队,c怎么进都不可能在b和a之间。
正确答案:C
————————————————————
————————————————————
解析:根据题意,第一个元素进入队列后存储在A[0]处,此时front和rear值都为0。入队时因为要执行(rear+1)%n操作,所以若入队后指针指向0,则rear初值为n-1,而因为第一个元素在A[0]中,插入操作只改变rear指针,所以fronT为0不变。
正确答案:B
————————————————————
————————————————————
解析:end1指向队头元素,可知出队操作是先从A[end1]读数,然后end1再加1。end2指向队尾元素的后一个位置,可知入队操作是先存数到A[end2],然后end2再加1。若用A[0J存储第一个元素,队列初始时,入队操作是先把数据放到A[0]中,然后end2自增,即可知end2初值为0;而end1指向的是队头元素,队头元素在数组A中的下标为o,所以得知endl的初值也为0,可知队空条件为end1==end2;然后考虑队列满时,因为队列最多能容纳M-1个元素,假设队列存储在下标为О到M-2的M-1个区域,队头为A[0],队尾为A[M-2],此时队列满,考虑在这种情况下end1和end2的状态,end1指向队头元素,可知end1=0,end2指向队尾元素的后一个位置,可知 end2=M-2+1=M-1,所以队满的条件为end1==(end2+1)mod M。
正确答案:A
————————————————————
————————————————————
解析:选项A的操作顺序为①①②②①①③③。选项B的操作顺序为②①①①①①③。选项D的操作顺序为②②②②②①③③③③③。对于C:首先输出3,说明1和2必须先依次入栈,而此后2肯定比1先输出,因此无法得到1,2的输出顺序。
正确答案:C
————————————————————
————————————————————
解析:假设队列左端允许入队和出队,右端只能入队。对于A,依次从右端入队1,2,再从左端入队3,4,5。对于B,从右端入队1,2,然后从左端入队3,再从右端入队4,最后从左端入队5。对于C,从左端入队1,2,然后从右端入队3,再从左端入队4,最后从右端入队5。无法验证D的序列。
正确答案:D
标签:队列,元素,入队,课后,习题,解析,rear,指针 From: https://blog.csdn.net/2406_86301373/article/details/141089745