2. 从业资格
  3. 设栈S和队列Q的初始状态为空，元素a b c d e f g依次进入栈S。要求每

设栈S和队列Q的初始状态为空，元素a b c d e f g依次进入栈S。要求每

免费题库2022-08-02  73
问题 设栈S和队列Q的初始状态为空，元素a b c d e f g依次进入栈S。要求每个元素出栈后立即进入队列Q，若7个元素出队列的顺序为b d f e c a g，则栈S的容量最小应该是（）。A.5B.4C.3D.2
选项 A.5
B.4
C.3
D.2
答案 B
解析 本题考查数据结构基础知识。栈的特点是数据在栈顶后进先出，而队列的特点是数据先进先出，队头出，队尾进。根据题目意思，元素 abcdefg 必须依次进入栈S，出栈后立即进入队列Q。1. 根据7个元素出队列的顺序为bdfecag，可知元素b是第一个出栈的，b出栈之前，栈中肯定有两个元素a与b（b要进栈，a必须先进栈），到此可推出栈的容量至少为2；2. 元素b出栈后栈中还有a，根据7元素出队列顺序，接下来是d出栈，d出栈之前，栈中肯定有三个元素a、c、d（d要进栈，c必须先进栈，而a之前就在栈底），到此可推出栈的容量至少为3；3. 元素d出栈后栈中还有a、c(从栈底至栈顶方向)，根据7元素出队列顺序，接下来是f出栈，f出栈之前，栈中肯定有三个元素a、c、e、f（f要进栈，e必须先进栈，而a、c之前就在栈中），到此可推出栈的容量至少为4；4. 元素f出栈后栈中还有a、c、e(从栈底至栈顶方向)，根据7元素出队列顺序，接下来是e出栈；5. 元素e出栈后栈中还有a、c(从栈底至栈顶方向)，根据7元素出队列顺序，接下来是c出栈；6. 元素c出栈后栈中还有a，根据7元素出队列顺序，接下来是a出栈；7. 元素a出栈后栈为空，根据7元素出队列顺序，接下来是g入栈，然后出栈。根据以上分析，栈的容量最小应为4。
转载请注明原文地址:https://tihaiku.com/congyezige/2408362.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)