2018 年 408 真题2018 年 408 数据结构 · 第 1 题选中文字高亮 · 下划线若栈 S1 中保存整数,栈 S2 中保存运算符,函数 F() 依次执行下述各步操作: 从 S1 中依次弹出两个操作数 a 和 b;从 S2 中弹出一个运算符 op;执行相应的运算 b op a;将运算结果压入 S1 。 假定 S1 中的操作数依次是 5,8,3,2(2 在栈顶),S2 中的运算符依次是 ×,−,+ ( + 在栈顶)。调用 3 次 F() 后,S1 栈顶保存的值是( )。A-15B15C-20D20←上一题请设计一个队列,要求满足: ① 初始时队列为空; ② 入队时,允许增加队列占用空间; ③ 出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减; ④ 入队操作和出队操作的时间复杂度始终保持为 O(1) 。 请回答下列问题: (1) 该队列是应选择链式存储结构,还是应选择顺序存储结构? (2) 画出队列的初始状态,并给出判断队空和队满的条件。 (3) 画出第一个元素入队后的队列状态。 (4) 给出入队操作和出队操作的基本过程。下一题现有队列 Q 与栈 S,初始时 Q 中的元素依次是 1,2,3,4,5,6(1 在队头),S 为空。若仅允许下列 3 种操作: ① 出队并输出出队元素 ② 出队并将出队元素入栈 ③ 出栈并输出出栈元素 则不可能得到的输出序列是( )。→