首页 > 其他分享 >25版王道数据结构课后习题详细分析 第三章栈、队列和数组 3.2 队列 选择题部分

25版王道数据结构课后习题详细分析 第三章栈、队列和数组 3.2 队列 选择题部分

时间:2024-08-10 23:23:37浏览次数:14  
标签:队列 元素 入队 课后 习题 解析 rear 指针

一、单项选择题

————————————————————

————————————————————

解析:栈和队列的逻辑结构都是线性结构,都可以采用顺序存储或链式存储,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

相关文章

  • 06.磁盘管理课后习题
    06.磁盘管理课后习题1.如何查看/etc/目录大小2.如何查看磁盘使用分区情况3.如何查看innode使用情况4.如何查看磁盘block使用情况1.使用“lsblk”命令查看块设备信息,包括磁盘分区情况和磁盘使用情况。2.使用“df”命令查看文件系统的磁盘空间使用情况。3.使用“du”......
  • c++习题18-计算鞍点
    目录一,题目二,思路三,代码一,题目给定一个5×5的矩阵,每行只有一个最大值,每列只有一个最小值,寻找这个矩阵的鞍点。鞍点指的是矩阵中的一个元素,它是所在行的最大值,并且是所在列的最小值。例如:在下面的例子中(第4行第1列的元素就是鞍点,值为8)。11356912478101056......
  • c++习题20-百钱百鸡
    目录一,题目二,思路三,代码 一,题目农夫约翰今天来到了畜牧市场,想给自己的农场里买点鸡回去。已知公鸡一只5块钱,母鸡3块钱,小鸡崽子一块钱三只。农夫手里有N元,他想买N只鸡,但是他跟ljc一样数学不好,想让你帮他算一算有几种买法,以方便他挑选。输入描述一个整数N,约翰手里的钱......
  • 单体应用提高性能及处理高并发-异步处理与消息队列
            在单体应用中,应对高并发和提升性能是开发者常面对的挑战。异步处理与消息队列是两个有效的手段,可以帮助开发者将耗时操作与主线程分离,减少阻塞,提高系统的响应速度和吞吐量。1.异步处理异步处理允许应用程序在执行耗时操作时不阻塞主线程。这对于提高系统性......
  • 【IO】IPC通信机制函数(消息队列,共享内存,信号量集函数整理汇总)
            整理了一下IPC通信的函数,包括消息队列,共享内存,信号量集;信号量集的使用是在共享内存的基础上使用,函数太多啦,慢慢学吧cc,争取全部记住        其中在使用有关信号量集的函数的时候,进行简单的封装函数功能之后,再进行使用,会更加方便,在文章最后对信号量集的......
  • 25版王道数据结构课后习题详细分析 第三章栈、队列和数组 3.1 栈 选择题部分
    一、单项选择题————————————————————————————————————————解析:栈和队列的逻辑结构都是相同的,都属于线性结构,只是它们对数据的运算不同。正确答案:B————————————————————————————————————......
  • 浙大数据结构慕课课后题(03-树2 List Leaves)
    题目要求:给定一棵树,您应该按照从上到下、从左到右的顺序列出所有叶子。输入规格: 每个输入文件都包含一个测试用例。对于每种情况,第一行都给出一个正整数N(<=10),这是树中节点的总数--因此节点的编号从0到N-1.然后N行紧随其后,每行对应一个节点,并给出节点的左右子节点......
  • 11.面试题——消息队列RabbitMQ
    1.RabbitMQ是什么?特点是什么?RabbitMQ是一种开源的消息队列中间件,用于在应用程序之间进行可靠的消息传递。它实现了AMQP(AdvancedMessageQueuingProtocol)协议,提供了强大的消息处理能力。RabbitMQ的主要特点包括:可靠性:RabbitMQ使用可靠的消息传递机制,确保消息能够安全地传......
  • 探索ThinkPHP6中的消息队列机制:提升应用性能与扩展性的关键
    在现代Web开发中,随着业务规模的扩大和用户量的激增,系统面临的并发请求和数据处理压力也随之增加。为了应对这些挑战,提升应用的性能和可扩展性,消息队列(MessageQueue)作为一种高效的数据处理模式,逐渐被广泛采用。ThinkPHP6,作为PHP语言下的一个高性能、易扩展的轻量级框架,也提供了......
  • 如何使用ThinkPHP6进行消息队列集成
    在ThinkPHP6中进行消息队列的集成,主要涉及到选择合适的消息队列系统(如RabbitMQ、Kafka、Redis等),并通过相应的PHP客户端库或扩展来实现与ThinkPHP6的集成。以下是一个基于RabbitMQ和Redis的集成示例,展示如何在ThinkPHP6项目中设置和使用消息队列。1.选择消息队列系统首先,你需......