最新《数据结构》习题汇编03 第三章 栈和队列 试题.doc

精品资料数据结构习题汇编03 第三章 栈和队列 试题.第三章 栈和队列 试题一、单项选择题1. 栈的插入和删除操作在（ ）进行。A. 栈顶B. 栈底C. 任意位置D. 指定位置2. 当利用大小为n的数组顺序存储一个栈时，假定用top=n表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。A. top+;B. top-;C. top = 0;D. top;3. 若让元素1,2,3依次进栈，则出栈次序不可能出现（ ）种情况。A. 3, 2, 1B. 2, 1, 3C. 3, 1, 2D. 1, 3, 24. 在一个顺序存储的循环队列中，队头指针指向队头元素的（ ）位置。A. 前一个B. 后一个C. 当前 D. 后面5. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。A. n-2 B. n-1C. n D. n+16. 从一个顺序存储的循环队列中删除一个元素时，需要（ ）。A. 队头指针加一B. 队头指针减一C. 取出队头指针所指的元素D. 取出队尾指针所指的元素7. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ）。A. front+1 = rearB. rear+1 = frontC. front = 0D. front = rear8. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ）。A. front = rearB. front != NULLC. rear != NULLD. front = NULL9. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行操作（ ）。A. top->link = s; B. s->link = top->link; top->link = s;C. s->link = top; top = s; D. s->link = top; top = top->link;10. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行操作（ ）。A. x = top->data; top = top->link; B. top = top->link; x = top->data;C. x = top; top = top->link;D. x = top->data;11. 设循环队列的结构是 #define MaxSize 100 typedef int ElemType; typedef struct ElemType baseMaxSize; int front, rear; Queue; 若有一个Queue类型的队列Q，则判断队列满的条件应是语句（ ）。 A. Q.front = Q.rear; B. Q.front - Q.rear = MaxSize;C. Q.front + Q.rear = MaxSize; D. Q.front = (Q.rear+1) % MaxSize;12. 设循环队列的结构是 #define MaxSize 100 typedef int ElemType; typedef struct ElemType baseMaxSize; int front, rear; Queue;若有一个Queue类型的队列Q，则应用语句（ ）计算队列元素个数。A. (Q.rear - Q.front + MaxSize ) % MaxSize;B. Q.rear - Q.front +1;C. Q.rear - Q.front -1;D. Q.rear - Qfront;13. 在做进栈运算时,应先判断栈是否（ ）A. 空 B. 满C. 上溢D. 下溢14. 为增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时, 应将两栈的（ ）分别设在这片内存空间的两端。 A. 长度B. 深度C. 栈顶D. 栈底15. 使用两个栈共享一片内存空间时，当（ ）时，才产生上溢。A. 两个栈的栈顶同时到达这片内存空间的中心点B. 其中一个栈的栈顶到达这片内存空间的中心点C. 两个栈的栈顶在这片内存空间的某一位置相遇D. 两个栈均不空, 且一个栈的栈顶到达另一个栈的栈底二、填空题1. 栈是一种限定在表的一端插入和删除的线性表，它的特点是_。2. 队列是一种限定在表的一端插入，在另一端删除的线性表，它的特点是_。3. 队列的插入操作在_进行，删除操作在_进行。4. 向一个顺序栈插入一个元素时，首先使_后移一个位置，然后把待插入元素写入到这个位置上。5. 从一个顺序栈中删除元素时，需要将_前移一位位置。6. 若设顺序栈的最大容量为MaxSize，则判断栈满的条件是_。7. 当用长度为MaxSize的数组顺序存储一个栈时，若用top = MaxSize表示栈空，则表示栈满的条件为_。8. 在一个链式栈中，若栈顶指针等于NULL则为_。9. 在向一个链式栈插入一个新结点时，首先把栈顶指针中存放的结点地址赋给新结点的指针域，然后把新结点的存储位置赋给_。10. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行_和_操作。11. 从一个栈顶指针为top的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行_操作。12. 设循环队列Q的队头和队尾指针分别为front和rear，则判断队空的条件为_。13. 设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队空的条件为Q.front = Q.rear，则判断队满的条件为_。14. 向一个循环队列中插入元素时，需要首先移动_，然后再向所指位置写入新插入的元素。15. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为_或该队列_。16. 假定front和rear分别为链式队列的队头和队尾指针，则该队列中只有一个结点的条件为_。17. 双端队列是限定插入和删除操作在表的_进行的线性表。18. 中缀表达式3*(x+2)-5所对应的后缀表达式为_。19. 后缀表达式“4 5 * 3 2 + -”的值为_。20. 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为_。三、判断题1. 每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列。2. 链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。3. 在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。4. 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。5. 在使用后缀表示实现计算器类时使用了一个栈的实例，它起的作用是暂存运算对象和计算结果。6. 在向顺序栈压入新元素时，要先按栈顶指针指示的位置存入新元素再移动栈顶指针。7. 在用单链表表示的链式队列中，队头在链表的链尾位置。8. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。9. 在一个循环队列Q中，判断队满的条件为Q.rear % MaxSize+1 = Q.front。10. 在一个循环队列Q中，判断队空的条件为Q.rear+1 = Q.front。11. 若让元素1, 2, 3依次进栈，则出栈次序1, 3, 2是不可能出现的情况。12. 若让元素1, 2, 3依次进栈，则出栈次序3, 1, 2是不可能出现的情况。13. 在循环队列中，进队时队尾指针进一，出队时队头指针减一。14. 在循环队列中，进队时队尾指针进一，出队时队头指针进一。15. 在用单链表表示的链式队列Q中，队空条件为Q->front = Q->rear。16. 如果进栈序列是1, 2, 3, 4, 5, 6, 7, 8。则可能的出栈序列有8！种。四、运算题1. 试利用运算符优先数法，画出对中缀算术表达式a + b * c - d / e 求值时运算符栈OPTR和运算对象栈OPND的变化。运算符优先数如下表所示：运算符#(*, /, %+, -)isp（栈顶运算符优先级）01537icp（栈外运算符优先级）074212. 试利用运算符优先数法，画出将中缀算术表达式a + b * c - d / e 改为后缀表达式时运算符栈OPTR的变化。运算符优先数如下表所示：运算符#(*, /, %+, -)isp（栈顶运算符优先级）01537icp（栈外运算符优先级）074213. 试画出对后缀算术表达式a b c * + d e / - 求值时运算对象栈OPND的变化。4. 将二项式 (a + b) i 展开, 其系数构成杨辉三角形。若想按行将展开式系数的前n行打印出来，需要用到一个队列，存放各行展开式的系数。试画出当n = 3的情况下，在打印过程中队列的变化。#include "03b.h" /在03b.h里定义了链栈的抽象数据类型void YANGVI ( int n ) SqQueue q; InitQueue(&q);q.EnQueue (1); q.EnQueue (1); int i, j, t, s = 0;for ( i = 1; i <= n; i+ ) cout << endl;q.EnQueue (0);for ( j = 1; j <= i+2; j+ ) q.DeQueue (t); q.EnQueue (s+t); s = t;if ( j != i+2 ) cout << s << ' '5. 写出下列程序段的输出结果:void main( ) stack S; char x, y;x = 'c' y = 'k'S.Push ( x ); S.Push ( 'a' ); S.Push ( y );S.Pop ( x ); S.Push ( 't' ); S.Push ( x );S.Pop ( x ); S.Push ( 's' );while (!S.IsEmpty ( ) ) S.Pop ( y ); cout << y; cout << y << endl; 输出结果：_6. 写出下列程序段的输出结果:void main( ) queue Q; char x = 'e', y = 'c'Q.EnQueue ( 'h' ); Q.EnQueue ( 'r' ); Q.EnQueue ( y );Q.DeQueue(Q,x); Q.EnQueue ( x ); Q.DeQueue ( x );Q.EnQueue ( 'a' );while (!Q.IsEmpty ( ) ) Q.DeQueue ( y ); cout << y; cout << y << endl; 输出结果：_7. 简述下述算法功能 void unknown ( Queue &Q ) Stack S; int d; while (!Q.IsEmpty ( ) ) Q.DeQueue ( d ); S.Push ( d ); while (!S.IsEmpty ( ) ) S.Pop ( d ); Q.EnQueue ( d ); 功能是：_五、算法分析题1. 下面的算法中使用了一个栈st，阅读该算法，回答下列问题：(1) 算法的功能是：_(2) 若字符数组A = m, a, d, a, m, i, m, a, d, a, m ，执行这个算法，跟踪栈的变化。#include “stack.h”int unknown ( char A , int n ) stack<char> st (n+1); int yes = 1, i = 0; char ch; while ( Ai != “0” ) st.Push ( Ai ); i+; i = 0; while ( Ai != “0” ) st.Pop ( ch );if ( Ai = ch ) i+; else yes = 0; break; return yes;2. 下面的算法中使用了一个栈st，阅读该算法，回答下列问题：(1) 算法的功能是：_(2) 若单链表中各结点中数据的逻辑顺序为 u, n, i, v, e, r, s, i, t, y ，执行这个算法，跟踪栈的变化。#include "stack.h"#include "LinkList.h"template<class T> void LinkList<T> : unknown ( ) /此单链表带有表头结点，它的表头指针为first。Stack<ListNode<T>*> S; ListNode<T> *p = first->link, *q; while ( p != NULL ) S.Push (p); p = p->link; p = first; p->link = NULL; while ( !S.IsEmpty( ) ) /将栈中保存的结点依次出栈S.Pop (q ); q->link = p->link; p->link = q; p = q; 六、算法设计题1. 假设以数组Qm存放循环队列中的元素, 同时设置一个标志tag，以tag = 0和tag = 1来区别在队头指针（front）和队尾指针（rear）相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入（enqueue）和删除（dlqueue）算法。2. 若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入（enqueue）和删除（dequeue）算法，并给出p为何值时队列空。3. 假设以数组Qm存放循环队列中的元素, 同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入（enqueue）和删除（dequeue）元素的操作。4. 双端队列（deque）是两端都可以插入与删除的顺序表。若将一个双端队列存放于一维数组Qm中，两个端点设为end1和end2，并让该数组首尾相接。试写出双端队列所用指针end1和end2的初始化条件及队空与队满条件，并编写基于此结构的相应的插入（enqueue）新元素和删除（dequeue）算法。