关于栈和队列习题ppt课件

1、关于栈和队列的习题一、选择题1.用单循环链表表示队列，正确的说法是：B A. 可设一个头指针使入队、出队都方便B. 可设一个尾指针使入队、出队都方便C. 必需设头尾指针才干使入队、出队都方便D. 无论如何,只能够使入队方便2.输入序列为A，B，C，D，不能够得到的输出序列有 D 。AA，B，C，D BD，C，B，A CA，C，D，B DC，A，B，D3.用顺序表实现栈构造时，顺序表地址的 B 作为栈顶操作比较方便。A. 低端 B. 高端4.用单链表实现栈构造构时，把链表的 A 作为栈顶操作比较方便。A. 第一个元素 B.最后一个元素二、判别题1.栈和队列逻辑上都是线性表。 ( )2.消除递归不

2、一定需求运用栈。 三、填空题1.用循环链表表示的队列长度为n，假设只设头指针，那么出队和入队的时间复杂度分别是 O1 和 On ；假设只设尾指针，那么出队和入队的时间复杂度分别是 O1 和 O1 。2.栈的特点是 后进先出 。3.队列的特点是先进先出 。四、问答题内存中一片延续空间无妨假设地址从1到m，提供应两个栈S1和S2运用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 两个栈公用一片顺序空间s1s2p2p1两个栈公用一片顺序空间10s1s2p2p1两个栈公用一片顺序空间1011s1s2p2p1两个栈公用一片顺序空间101112s1s2p2p1两个栈公用一片顺序

3、空间10111220s1s2p2p1两个栈公用一片顺序空间1011122120s1s2p2p1两个栈公用一片顺序空间101112222120s1s2p2p1两个栈公用一片顺序空间10111223222120s1s2p2p1两个栈公用一片顺序空间1011122423222120s1s2p2p1两个栈公用一片顺序空间101112132423222120s1s2p2p1两个栈公用一片顺序空间10111213142423222120s1s2p2p1此时指针交错，空间曾经满了，不能再压入元素五、程序设计题1.设A是一个栈，栈中共有N个元素，依次为A1，A2，,AN，栈顶元素为AN，B是一个循环队列，队列

4、中N个元素依次为B1，B2，BN，队头元素为B1，A，B均采用顺序存储构造且存储空间足够大，现要将栈中元素全部移到队列中，使得队列中元素与栈中元素交替陈列，即B中元素为B1，A1，B2，A2，B3，A3，,BN，AN，问至少需求多少次根本操作才干完成上述任务，请写出详细步骤要求除A，B外所用的其他附加存储量为1，每次出栈、入栈、出队列可均看作一次根本操作。 int main(int argc, char* argv)queue q;q.push(1);q.push(2);q.push(3);stack s;s.push(4);s.push(5);s.push(6); int len;while

5、(s.empty()!=true)q.push(s();/栈顶元素放入队列尾部s.pop();/删除栈顶元素len=q.size();/此时队列的长度为lenwhile(len2)/队列的前len-2个元素放入队尾q.push(q.front();q.pop();len-;while(q.empty()!=true)coutq.front();q.pop();return 0;我无法证明这是不是最少次数。大家可以思索一下有没有更好的方法。2.知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量任务变量，运用C言语编写一个算法，将队列Q中的一切元素逆置。 int main(int argc, char* argv)queue q;q.push(1);q.push(2);q.push(3);stack s;while(q.empty()!=true)/队列中元素入栈s.push(q.front();q.pop();while(s.emp