扫码获取更多资源

●栈和队列习题

填空题

1.线性表、栈和队列都属于( )结构。可在线性表( ）位置插入和删除元素；对插 于栈只能在( )插入和删除元素；对于队列只能在( ）入元素和在( )删除元素。

2.在操作序列 push(l) ,push(2) ,pop( ) ,push(5) ,push(7) ,pop()和 push(6)之后，栈 顶元素是( )，栈底元素是( )o

4.实现递归函数调用的一种数据结构是( )。

5.在具有n个单元的循环队列中，队满时共有( )个元素。

选择题

如果一个栈的入栈序列是1、2、3、4、5,则栈不可能的输出序列是（）

（A）54321 (B) 45321 (C) 43512 (D) 12345

2.如果一个队列的入队顺序是1、2、3、4,则队列的输出顺序是（）

(A) 4321 (B) 1234 (C) 1432 (D) 3241

3. 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓 冲区应该是一个( )结构。

(A)栈 (B)队列 (C)数组 (D)线性表

5.设栈S和队列Q的初始状态为空，元素at ,a2,-,a6依次通过栈S, 一个元素出栈后 即进入队列Q。如果6个元素出队的顺序是也、叫“3頒6湿5、。1，则栈S的容量至少应该 是( )。

(A) 6 (B) 4 (C) 3 (D) 2

问答题

1.循环队列的引入是为了克服什么问题？

2.设有一个栈，元素进栈的次序为a、b、c、d、e,能否得到出栈序列c、e、a、b、d和c、b、a、 d、e?如果能，则写出操作序列；如果不能，则说明原因。

3.如果用Q[n]表示一个循环队列，用front表示队头元素的前一个位置，用rear表示 队尾元素的位置，那么队列中元素个数是多少？

4.已知一个栈的入栈序列是l,2,・・・，n,其输出序列为Pi，P2,…，Pn，如果Pi=n,则ps 是多少？

5.如果利用两个栈S1和S2模拟一个队列，那么应该如何利用栈的运算实现队列的插 入和删除操作？

算法设计题

1.试设计一个算法：判定给定的字符向量是否为回文。回文即正读和反读均相同的 字符序列，例如字符序列“abba”和字符序列“abdba”均是回文，但字符序列“good”不是回 文。提示：将一半字符入栈。

2.试设计一个算法：判断一个算术表达式的圆括号是否正确配对。提示：采用栈的结 构，对表达式进行扫描时，凡遇到字符“(”就进栈，遇到字符“)”就退栈，表达式扫描完毕后栈 应该为空。

3.假设以带头结点的循环链表表示队列，且只设一个指针指向队尾元素。试设计一个 算法：对该循环队列进行置空队、判队空、入队和出队操作。

4 .假设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2i，・・・，a/试设计 一个算法：通过一个循环队列Q重新排列该栈中的元素，使得从栈顶到栈底的元素依次为 a2n »a2n_2 »,,, »a2 »a2n_! ,a2n_3, ••・恂。要求空间复杂度和时间复杂度均为O(n)。

5.假设编号为1、2、3、4的四列火车通过如图3-2所示的铁路调度站，可能得到的调度 结果有哪些？如果有n列火车通过调度站，试设计一个算法：输出所有可能的调度结果。

联系我们：