13关于栈和队列的题目.ppt

关于栈和队列的习题;一、选择题 1.用单循环链表表示队列，正确的说法是：（B ） A. 可设一个头指针使入队、出队都方便 B. 可设一个尾指针使入队、出队都方便 C. 必须设头尾指针才能使入队、出队都方便 D. 无论如何,只可能使入队方便 2.输入序列为（A，B，C，D），不可能得到的输出序列有?（D ）。 A．（A，B，C，D）? B．（D，C，B，A）? C．（A，C，D，B） ? D．（C，A，B，D） 3.用顺序表实现栈结构时，顺序表地址的（ B ）作为栈顶操作比较方便。 A. 低端 B. 高端 4.用单链表实现栈结构构时，把链表的（ A ）作为栈顶操作比较方便。 A. 第一个元素 B.最后一个元素;二、判断题 1.栈和队列逻辑上都是线性表。 ( √ ) 2.消除递归不一定需要使用栈。（√ ） 三、填空题 1.用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是??O（1）??? 和?O（n）???? ；若只设尾指针，则出队和入队的时间复杂度分别是??O（1）?? 和??O（1）?? 。 2.栈的特点是（ 后进先出 ）。 3.队列的特点是（先进先出 ）。;四、问答题 内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 ;两个栈公用一片顺序空间;两个栈公用一片顺序空间;两个栈公用一片顺序空间;两个栈公用一片顺序空间;两个栈公用一片顺序空间;两个栈公用一片顺序空间;两个栈公用一片顺序空间;两个栈公用一片顺序空间;两个栈公用一片顺序空间;两个栈公用一片顺序空间;两个栈公用一片顺序空间;五、程序设计题 1.设A是一个栈，栈中共有N个元素，依次为A1，A2，…,AN，栈顶元素为AN，B是一个循环队列，队列中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[]) { queueint q; q.push(1); q.push(2); q.push(3); stackint s; s.push(4); s.push(5); s.push(6);; int len; while(s.empty()!=true) { q.push(s.top());//栈顶元素放入队列尾部 s.pop();//删除栈顶元素 len=q.size();//此时队列的长度为len while(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[]) { queueint q; q.push(1); q.push(2); q.push(3);; stackint s; while(q.empty()!=true) {//队列中元素入栈 s.push(q.front()); q.pop(); } while(s.empty()!=true) {//栈中元素入队列 couts.top() ; q.push(s.top()); s.pop(); } return 0; };接下来的时间，大家把本章内容复习一下，有不懂得地方问一下。;