🏷️ 知识点：队列
若循环队列以数组 Q[0..m-1] 为其存储结构，变量 rear 表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1) MOD m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是（ ）。
A. rear-length
B. (rear-length+m) MOD m
C. (1+rear-m-length) MOD m
D. (rear-length-1) MOD m
[tag_link]
正确答案：C
循环队列中，队尾元素的位置由 `rear` 给出，队列当前元素个数为 `length`。 设��首元素的位置为 `front`，由于队列元素从 `front` 连续存储到 `rear`（考虑循环），因此 `rear` 与 `front` 满足关系：
解出 front，得：
选项 C 的表达式为 (1 + rear - m - length) MOD m，可化简为：
在模 运算下，减去 不改变余数，因此该表达式等价于：
与推导结果一致。
通过实例验证：设
， ， ，则队首应为位置 9。
计算选项 C：
结果正确； 而其他选项均不满足。 因此，循环队列的队首元素实际位置为选项 C。
循环队列用数组 A[0...m-1] 存放其元素值，头尾指针分别为 front 和 rear，front 指向队头元素，rear 指向队尾元素的下一个元素，其移动按数组下标增大的方向进行（rear != m-1 时），则当前队列中的元素个数是（ ）。
A. (rear - front + m) % m
B. (rear - front + 1) % m
C. rear - front - 1
D. rear - front
[tag_link]
正确答案：A
【解析】在循环队列中，`front` 指针指向队头元素，`rear` 指针指向队尾元素的下一个位置。 队列中的元素从 `front` 开始，到 `rear` 的前一个位置结束。 由于数组是循环的：
- 当 `rear ≥ front` 时，元素个数为 `rear − front`； >
- 当 `rear < front` 时，表示 `rear` 已从数组末尾绕回到开头，此时元素个数为 `(rear + m) − front`，即 `rear − front + m`。 >
综合这两种情况，元素个数可统一表示为 `(rear − front + m) % m`， 该公式通过取模运算确保结果始终为非负整数且正确反映队列长度。 >
其他选项中：
- B 项 `(rear − front + 1) % m` 在队列为空（`front == rear`）时会得到 1，而非 0； >
- C 项 `rear − front − 1` 在空队列时得到 −1，且不适用于循环情况； >
- D 项 `rear − front` 在 `rear < front` 时会产生负数，未考虑循环特性。 >
因此，只有 A 项适用于所有情况。 >
若以 1234 作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是（ ）。
A. 1234 B. 4132 C. 4231 D. 4213
[tag_link]
正确答案：C
输入序列为 1234，需找出既不能由输入受限双端队列（插入仅在一端，删除可在两端）也不能由输出受限双端队列（删除仅在一端，插入可在两端）得到的输出序列。
- 选项 A（1234）：两种受限队列均可通过顺序插入和删除得到。
- 选项 B（4132）：输入受限队列可通过插入 1,2,3,4 后依次删除后端 4、前端 1、后端 3、前端 2 得到； 输出受限队列无法得到，因为需要插入 4 前队列前端为 1 且后续顺序为 3,2，但无法通过插入 1,2,3 得到所需队列[1,3,2]。
- 选项 C（4231）：输入受限队列中，插入 1,2,3,4 后删除后端 4，队列变为[1,2,3]，2 不在端部，无法直接输出 2 而不先输出 1 或 3； 输出受限队列中，需要插入 4 前队列为[2,3,1]，但无法通过插入 1,2,3 得到该队列。 因此两种队列均无法得到 4231。
- 选项 D（4213）：输入受限队列无法得到（类似 4231 的原因），但输出受限队列可通过插入 1,2,3 得到队列[2,1,3]，再插入 4 前端后依次删除得到 4213。 综上，4231 既不能由输入受限也不能由输出受限双端队列得到。
用链表方式存储的队列（有头尾指针非循环），在进行删除运算时（ ）。
A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
[tag_link]
正确答案：D
在链表方式存储的队列中，头指针指向队头节点，尾指针指向队尾节点，且为非循环链表。 进行删除运算时，通常从队头删除节点。
如果队列中有多个节点，删除队头节点后，只需修改头指针指向下一个节点，尾指针保持不变，因为队尾节点未变。 如果队列中只有一个节点，删除后队列为空，此时需要将头指针和尾指针都修改为 NULL，表示队列为空。
因此，删除操作中头指针总是需要修改，而尾指针仅在队列变空时需要修改，否则不变。 这意味着头、尾指针可能都要修改，也可能只修改头指针，故选项 D 正确。
某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，若元素 a,b,c,d,e 依次入此队列后 再进行出队操作，则不可能得到的出队序列是()。
A.b,a,c,d,e B.d,b,a,c,e C.d,b,c,a,e D.e,c,b,a,d
[tag_link]
正确答案：C
本题的队列实质是 输出受限的双端队列 （两端入队、一端出队）。
依次入队的元素为 a、b、c、d、e，各选项的可行性及对应入队方案如下： A 可行 a 左入（或右入） → b 左入 → c 右入 → d 右入 → e 右入 队列状态（队首→队尾）：b, a, c, d, e 出队序列：b, a, c, d, e ✅ B 可行 a 左入（或右入） → b 左入 → c 右入 → d 左入 → e 右入 队列状态：d, b, a, c, e 出队序列：d, b, a, c, e ✅ D 可行 a 左入（或右入） → b 左入 → c 左入 → d 右入 → e 左入 队列状态：e, c, b, a, d 出队序列：e, c, b, a, d ✅ C 不可能 不管 a 从左还是右入队，b 紧接着入队后一定与 a 相邻。
要得到 d, b, c, a, e，d 必须第一个出队，所以 d 只能从队首方向插入，处于 a、b 的外侧。
当 d 出队、接着 b 出队后，队列中只剩 a（及其后可能入队的元素）。
此时无论 c 是在 b 出队前还是之后入队，从两端插入都无法使 c 出现在 b 和 a 之间，也就无法形成 b, c, a 的出队顺序。
因此该序列不可能。
❌
已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1, 2, 3, 4, 5 , 则不能得到的出队序列是（ ）。
A. 5,4,3,1,2 B. 5,3,1,2,4 C. 4,2,1,3,5 D. 4,1,3,2,5
[tag_link]
正确答案：D
每次入队有两个选择，但是出队只有能一个选择，所以 2 在出队时必然和 1 相邻，3 在出队时必然与 2 相邻，以此类推，可以判断 D 选项是不可能的，因为 1 和 2 没有相邻。
设栈 S 和队列Q的初始状态均为空，元素 a,b,c,d,e,f,g 依次进入栈 S 。若每个元素出栈后立即进入 队列 Q, 且7个元素出队的顺序是 b,d,c,f,e,a,g, 则栈 S 的容量至少是()。
A.1
B.2
C.3
D.4
[tag_link]
正确答案：C
由于队列的特点是先进先出，即栈 S 的出栈顺序就是队 Q 的出队顺序。故本题只需注意栈的特点是先进后出。出入栈的详细过程见下表。序号 说明 栈内 栈外 序号 说明 栈内 栈外 1 a 入栈 A 8 e 入栈 ae bdc 2 b 入栈 Ab 9 f 入栈 aef bdc 3 b 出栈 A b 10 f 出栈 ae bdcf 4 c 入栈 Ac b 11 e 出栈 a bdcfe 5 d 入栈 Acd b 12 a 出栈 bdcfea 6 d 出栈 Ac bd 13 g 入栈 g bdcfea 7 c 出栈 A bdc 14 g 出栈 bdcfeag 栈内的最大深度为 3，故栈 S 的容量至少是 3。【另解】元素的出栈顺序是 b,d,c,f,e,a,g，可推出进栈出栈顺序为 Push(S,a), Push(S,b), Pop(S,b), Push(S,c), Push(S,d), Pop(S,d), Pop(S,c), Push(S,e), Push(S,f), Pop(S,f), Pop(S,e), Pop(S,a), Push(S,g), Pop(S,g)。假设初始所需容量为 0，每做一次 Push 进行一次“+1”操作，每做一次 Pop 进行一次“-1”操作，记录容量的最大值为 3，所以选 C。
若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3，其移动按数组下标增大的方向进行（当下标不等于 m-1 时）。当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为（ ）。
A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1
[tag_link]
正确答案：B
首先，循环队列使用大小为 6 的数组，下标从 0 到 5。 初始时 front=3，rear=0，表示队列中有元素。 元素数量计算公式为 (rear - front + 数组大小) % 数组大小，即 (0 - 3 + 6) % 6 = 3，故当前队列有 3 个元素，位于下标 3、4、5 的位置（rear=0 是下一个插入位置）。
接下来执行操作：先删除一个元素，再加入两个元素。 删除元素时，front 向数组下标增大方向移动。 当前 front=3，不是数组末尾下标 5，因此删除后 front 增加 1，变为 4。 此时 rear 不变，仍为 0。 然后加入第一个元素：rear 向数组下标增大方向移动，从 0 增加 1 到 1。 加入第二个元素：rear 从 1 增加 1 到 2。
最终，rear=2，front=4。 对应选项 B（2 和 4）。
已知循环队列存储在一维数组 A[0..n-1]中，且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在 A[0]处，则初始时 front 和 rear 的值分别是（ ）。
A. 0，0
B. 0，n-1
C. n-1，0
D. n-1，n-1
[tag_link]
正确答案：B
根据题意，第一个元素进入队列后存储在A[0]处，此时front和rear值都为0。入队时由于要执行(rear+1) % n操作，所以如果入队后指针指向 0， 则rear初值为n-1，而由于第一个元素在A[0]中，插入操作只改变rear指针，所以front为 0 不变。
循环队列放在一维数组 A[0..M-1] 中，end1 指向队头元素，end2 指向队尾元素的后一个位置。假设队 列两端均可进行入队和出队操作，队列中最多能容纳 M-1 个元素。初始时为空。下列判断队空和队满的 条件中，正确的是()。
A. 队空：end1=end2; 队满：end1=(end2+1)mod M
B. 队空：end1=end2; 队满：end2=(end1+1)mod(M-1)
C. 队空：end1=(end1+1)mod M; 队满：end1=(end2+1)mod M
D. 队空：end1=(end2+1)mod M; 队满：end2=(end1+1)mod(M-1)
[tag_link]
正确答案：A
本题考查 循环队列 ： end1 指向队头元素，那么可知出队的操作是先从 A[end1] 读数，然后 end1 再加 1 。end2 指向队尾元素的后一个位置，那么可知入队操作是先存数到 A[end2] ，然后 end2 再加 1 。若把 A[0] 储存第一个元素，当队列初始时，入队操作是先把数据放到 A[0] ，然后 end2 自增，即可知 end2 初值为 0;end1 指向的是队头元素，队头元素的在数组 A 中的下标为 0 ，所以得知 end1 初值也为 0 ，可知队空条件为 end1-end2 。然后考虑队列满时，因为队列最多能容纳 M-1 个元素，假设队列存储在下标为 0 到下标为 M-2 的 M-1 个区域，队头为 A[0] ，队尾为 A[M-2] ，此时队列满，考虑在这种情况下 end1 和 end2 的状态， end1 指向队头元素，可知 end1-0 ， end2 指向队尾元素的后一个位置，可知 end2=M-2+1=M-1 ，所以可知队满的条件为 end1-(end2+1)modM ，选 A 。
设有下图所示的火车车轨，入口到出口之间有 n 条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为 1-9 的 9 列列车，驶入的次序依次是 8, 4, 2, 5, 3, 9, 1, 6, 7。若期望驶出的次序依次为 1~9，则 n 至少是（ ）。
A. 2 B. 3 C. 4 D. 5
[tag_link]
正确答案：C
在确保队列先进先出原则的前提下。根据题意具体分析：入队顺序为 8, 4, 2, 5, 3, 9, 1, 6, 7，出队顺序为 1~9。入口和出口之间有多个队列（n 条轨道），且每个队列（轨道）可容纳多个元素（多列列车）。如此分析：显然先入队的元素必须小千后入队的元素（如果 8 和 4 入同一队列，8 在前 4 在后，那么出队时只能是 8 在前 4 在后），这样 8 入队列 1，4 入队列 2, 2 入队列 3，5 入队列 2（按照前面的原则“大的元素在小的元素后面”也可以将 5 入队列 3，但这时剩下的元素 3 就必须放到一个新的队列里面，无法确保”至少“，本应该是将 5 入队列 2，再将 3 入队列 3，不增加新队列的情况下，可以满足题意“至少”的要求），3 入队列 3，9 入队列 1，这时共占了 3 个队列，后面还有元素 1，直接再占用一个新的队列 4，1 从队列 4 出队后，剩下的元素 6 和 7 或者入队到队列 2 或者入队到队列 3（为简单起见我们不妨设 n 个队列的序号分别为 1, 2, …, n），这样就可以满足题目的要求。综上，共占用了 4 个队列。当然还有其他的入队出队的情况，请考生们自己推演。但要确保满足：O 队列中后面的元素大千前面的元素；确保占用最少（即 满足题目中的“至少") 的队列。
栈和队列的主要区别在于()。
A. 它们的逻辑结构不一样 B. 它们的存储结构不一样 C. 所包含的元素不一样 D. 插入、删除操作的限定不一样
[tag_link]
正确答案：D
队列的“先进先出”特性是指()。 I. 最后插入队列中的元素总是最后被删除 II. 当同时进行插入、删除操作时，总是插入操作优先 Ⅲ.每当有删除操作时，总要先做一次插入操作 IV. 每次从队列中删除的总是最早插入的元素
A. I B. I 和 IV C. Ⅱ 和 Ⅲ D. IV
[tag_link]
正确答案：B
允许对队列进行的操作有()。
A. 对队列中的元素排序 B. 取出最近入队的元素 C. 在队列元素之间插入元素 D. 删除队首元素
[tag_link]
正确答案：D
一个队列的入队顺序是1,2,3,4,则出队的输出顺序是()。
A. 4,3,2,1 B.1,2,3,4 C.1, 4,3, 2 D.3,2,4,1
[tag_link]
正确答案：B
循环队列存储在数组A[0…n] 中，入队时的操作为()。
A. rear=rear+1 B.rear=(rear+1)mod(n-1) C. rear=(rear+1)mod n D.rear=(rear+1)mod (n+1)
[tag_link]
正确答案：D
已知循环队列的存储空间为数组 A[21],front 指向队首元素的前一个位置，rear 指 向队尾元素，假设当前 front 和 rear 的值分别为8和3,则该队列的长度为()。 A.5 B.6 C.16 D.17
[tag_link]
正确答案：C
若用数组A[0…5] 实现循环队列，且当前 rear 和 front 的值分别为1和5,当从队列 中删除一个元素，再加入两个元素后，rear 和 front 的 值 分 别 为 ( ) 。
A. 3和 4 B. 3 和0 C. 5和0 D.5 和 1
[tag_link]
正确答案：B
假设用数组 Q[MaxSize] 实现循环队列，队首指针 front 指向队首元素的前一位置， 队尾指针 rear 指向队尾元素，则判断该队列为空的条件是()。
A. Q.rear==(Q.front+1)8MaxSize B. ( Q.rear+1)号MaxSize==Q.front+1 C. (Q. rear+1) 号MaxSize== Q.front D. Q.rear==Q.front
[tag_link]
正确答案：D
假设循环队列Q[MaxSize] 的队首指针为 front, 队尾指针为rear, 队列的最大容量 为 MaxSize, 此外，该队列再没有其他数据成员，则判断该队列已满的条件是()。
A. Q. front==Q. rear B.Q.front+Q .rear>=MaxSize C. Q .front==(Q.rear+1)MaxSiz e D.Q.rear==(Q.front+1) 号MaxSize
[tag_link]
正确答案：C
假设用 A[0….n]实现循环队列，front 、rear 分别指向队首元素的前一个位置和队尾 元素。若用(rear+1) 号(n+1)==front 作为队满标志，则()。
A. 可用 front==rear 作为队空标志 B. 队列中最多可有n+1 个元素 C. 可 用 front>rear 作为队空标志 D. 可用( front+1) 吕(n+1)==rear 作为队空标志
[tag_link]
正确答案：A
与顺序队列相比，链式队列的()。
A. 优点是队列的长度不受限制 B. 优点是入队和出队时间效率更高 C. 缺点是不能进行顺序访问 D. 缺点是不能根据队首指针和队尾指针计算队列的长度
[tag_link]
正确答案：D
下列描述的几种链表中，最适合用作队列的是()。
A. 带队首指针和队尾指针的循环单链表 B. 带队首指针和队尾指针的非循环单链表 C. 只带队首指针的非循环单链表 D. 只带队首指针的循环单链表
[tag_link]
正确答案：B
请设计一个队列，要求满足：
① 初始时队列为空；
② 入队时，允许增加队列占用空间；
③ 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；
④ 入队操作和出队操作的时间复杂度始终保持为 O(1) 。
请回答下列问题：
(1) 该队列是应选择链式存储结构，还是应选择顺序存储结构？
(2) 画出队列的初始状态，并给出判断队空和队满的条件。
(3) 画出第一个元素入队后的队列状态。
(4) 给出入队操作和出队操作的基本过程。
[tag_link]
1）顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析：要求①容易满足；链式存储方便开辟新空间，要求②容易满足；对于要求③，出队后的结点并不真正释放，用队头指针指向新的队头结点，新元素入队时，有空余结点则无须开辟新空间，赋值到队尾后的第一个空结点即可，然后用队尾指针指向新的队尾结点，这就需要设计成一个首尾相接的循环单链表，类似于循环队列的思想。设置队头、队尾指针后，链式队列的入队操作和出队操作的时间复杂度均为 O(1)，要求④可以满足。因此，采用链式存储结构（两段式单向循环链表），队头指针为 front，队尾指针为 rear。
2）该循环链式队列的实现，可以参考循环队列，不同之处在于循环链式队列可以方便增加空间，出队的结点可以循环利用，入队时空间不够也可以动态增加。同样，循环链式队列也要区分队满和队空的情况，这里参考循环队列牺牲一个单元来判断。初始时，创建只有一个空闲结点的循环单链表，头指针 front 和尾指针 rear 均指向空闲结点，如下图所示。
队空的判定条件：front == rear。队满的判定条件：front == rear->next。
3）插入第一个元素后的状态如下图所示。4)操作的基本过程：入队操作
if (front == rear->next)
则在 rear 后面插入一个新的空闲结点；
入队元素保存到 rear 所指结点中；rear=rear->next；返回。
出队操作
if（front==rear） // 队空
则出队失败，返回；
取 front 所指结点中的元素 e；front=front->next；返回 e。
下列描述的几种链表中，最不适合用作链式队列的是()。
A. 只带队首指针的非循环双链表 B. 只带队首指针的循环双链表 C. 只带队尾指针的循环双链表 D. 只带队尾指针的循环单链表
[tag_link]
正确答案：A
在用单链表实现队列时，队头设在链表的()位置。
A. 链头 B. 链尾 C. 链中 D. 以上都可以
[tag_link]
正确答案：A
用链式存储方式的队列进行删除操作时需要()。
A. 仅修改头指针 B. 仅修改尾指针 C. 头尾指针都要修改 D. 头尾指针可能都要修改
[tag_link]
正确答案：D
在一个链式队列中，假设队首指针为 front, 队尾指针为 rear,x 所指向的元素需要 入队，则需要执行的操作为()。
A. front=x,front=front->next B. x->next=front->next,front=x C. rear->next=x, rear=x D. rear->next=x,x->next=NULL,rear=x
[tag_link]
正确答案：D
假设循环单链表表示的队列长度为 n, 队头固定在链表尾，若只设头指针，则入队操作 的时间复杂度为()。
A. O(n) B.O(1) C.O(n²) D.O(nlog₂n)
[tag_link]
正确答案：A
假设输入序列为1,2,3,4,5,利用两个队列进行出入队操作，不可能输出的序列是()。 A.1,2,3,4,5 B.5,2,3,4,1 C.1,3,2,4,5 D.4,1,5,2,3
[tag_link]
正确答案：B
若以1,2,3,4作为双端队列的输入序列，则既不能由输入受限的双端队列得到，又不能 由输出受限的双端队列得到的输出序列是()。
A. 1,2,3,4 B.4, 1,3, 2 C.4,2,3,1 D.4,2,1,3
[tag_link]
正确答案：C
若希望循环队列中的元素都能得到利用，则需设置一个标志域 tag, 并以tag 的值为0 或1来区分队首指针front 和队尾指针rear 相同时的队列状态是“空”还是“满”。 试编写与此结构相应的入队和出队算法。
[tag_link]
D
Q是一个队列，S 是一个空栈，实现将队列中的元素逆置的算法。
[tag_link]
B
利用两个栈 S1 和 S2 来模拟一个队列，已知栈的4个运算定义如下：Push(S,x ); I1元素x 入 栈SPop(S,x); //s 出栈并将出栈的值赋给xStackEmpty (S ); / 判断栈是否为空StackOverflow(S); /判断栈是否为满
[tag_link]
D
利用两个栈 S1 和 S2 来模拟一个队列，已知栈的4个运算定义如下： Push(S,x ); I1元素x 入 栈S Pop(S,x); //s 出栈并将出栈的值赋给x StackEmpty (S ); / 判断栈是否为空 StackOverflow(S); /判断栈是否为满 如何利用栈的运算来实现该队列的3个运算(形参由读者根据要求自己设计)?//将元素x 入队//出队，并将出队元素存储在x 中 /判断队列是否为空Enqueue ;Dequeue;QueueEmpty; 如何利用栈的运算来实现该队列的3个运算(形参由读者根据要求自己设计)? //将元素x 入队 //出队，并将出队元素存储在x 中 /判断队列是否为空 Enqueue ; Dequeue; QueueEmpty;
[tag_link]
D