数据结构第三章栈和队列3习题

1、 第三章 栈和队列试题一、单项选择题栈的插入和删除操作在（）进行。C. 任意位置D. 指定位置栈顶B. 栈底当利用大小为n 的数组顺序存储一个栈时，假定用首先应执行（）语句修改top 指针。A. top+ ;B. top - ;top = n 表示栈空，则向这个栈插入一个元素时，C. top = 0D. top ;3. 若让元素1,2,3 依次进栈，则出栈次序不可能出现（）种情况。A. 3, 2, 1B. 2, 1, 3C. 3, 1, 2D. 1, 3, 2在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。A. 前一个B. 后一个C. 当前D. 后面当利用大小为n 的数组顺序存储一

2、个队列时，该队列的最大长度为（） 。A. n-2B. n-1C. nD. n+1从一个顺序存储的循环队列中删除一个元素时，需要（） 。A. 队头指针加一B. 队头指针减一C. 取出队头指针所指的元素D. 取出队尾指针所指的元素假定一个顺序存储的循环队列的队头和队尾指针分别为front 和 rear ， 则判断队空的条件为（） 。A. front+1 = rearB. rear+1 = frontC. front = 0D. front = rear假定一个链式队列的队头和队尾指针分别为A. front = rearC. rear != NULLfront 和 rear ，则判断队空的条件为（

3、B. front != NULL D. front = NULL9. 设链式栈中结点的结构为（data, link个由指针s 所指的结点，则应执行操作（） ，且 top 是指向栈顶的指针。若想在链式栈的栈顶插入一）。A. top-link = s;C. s-link = top ; top = sB. s-link = top-link; top-link = sD. s-link = top ; top = top-link10. 设 链式栈中结点的结构为（并将被摘除结点的值保存到data, link ） ，且 top 是指向栈顶的指针。若想摘除链式栈的栈顶结点，x 中，则应执行操作（） 。

4、A. x = top-data; top = top-linkC. x = top ; top = top-linktop = top-link ; x = top-data D. x = top-data ;设 循环队列的结构是#define MaxSize 100typedef intElemType ;typedef struct ElemType baseMaxSize int front, rear ; Queue ;若有一个Queue类型的队列Q,则判断队列满的条件应是语句（）。A. Q.front = Q.rear ;B. Q.front - Q.rear = MaxSize;C

5、. Q.front + Q.rear = MaxSize;D. Q.front = （Q.rear+1） % MaxSize设 循环队列的结构是#define MaxSize 100typedef intElemType ;typedef struct TOC o 1-5 h z ElemType baseMaxSize;int front, rear ; Queue ;若有一个Queue类型的队列Q,则应用语句（）计算队列元素个数。（Q.rear - Q.front + MaxSize ） % MaxSize;Q.rear - Q.front +1;Q.rear - Q.front -1;Q

6、.rear - Qfront;在 做进栈运算时, 应先判断栈是否（）A. 空B. 满C. 上溢D. 下溢为 增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时, 应将两栈的（）分别设在这片内存空间的两端。A. 长度B. 深度C. 栈顶D. 栈底使 用两个栈共享一片内存空间时，当（）时，才产生上溢。两个栈的栈顶同时到达这片内存空间的中心点其中一个栈的栈顶到达这片内存空间的中心点两个栈的栈顶在这片内存空间的某一位置相遇两个栈均不空, 且一个栈的栈顶到达另一个栈的栈底二、填空 TOC o 1-5 h z 栈是一种限定在表的一端插入和删除的线性表，它的特点是 。队列是一种限定在表

7、的一端插入，在另一端删除的线性表，它的特点是 。队列的插入操作在 进行，删除操作在 进行。向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把待插入元素写入到这个位置上。从一个顺序栈中删除元素时，需要将 前移一位位置。若设顺序栈的最大容量为MaxSize ，则判断栈满的条件是 。当用长度为MaxSize 的数组顺序存储一个栈时，若用top = MaxSize 表示栈空，则表示栈满的 TOC o 1-5 h z 条件为 。在一个链式栈中，若栈顶指针等于NULL 则为 。在向一个链式栈插入一个新结点时，首先把栈顶指针中存放的结点地址赋给新结点的指针域，然后把新结点的存储位置赋给 。向一个栈顶指

8、针为top 的链式栈中插入一个新结点*p 时，应执行 和 操作。从一个栈顶指针为top 的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 操作。设循环队列Q 的队头和队尾指针分别为front 和 rear ，则判断队空的条件为 。设循环队列Q 的队头和队尾指针分别为front 和 rear ，队列的最大容量为MaxSize ，且规定判断队空的条件为Q.front = Q.rear ，则判断队满的条件为 。向一个循环队列中插入元素时，需要首先移动 ，然后再向所指位置写入新插入的元素。在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为 或该队列 。假定 front 和

9、 rear 分别为链式队列的队头和队尾指针，则该队列中只有一个结点的条件为 。双端队列是限定插入和删除操作在表的 进行的线性表。中缀表达式3*(x+2)-5 所对应的后缀表达式为 。后缀表达式“4 5 * 3 2 + - ”的值为 。设有一个顺序栈 S,元素S1,S 2, s 3,s 4,s 5,s 6依次进栈，如果 6个元素的出栈顺序为S2,S 3,s4, s 6, s 5, s 1，则顺序栈的容量至少应为 。三、判断. 每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列。. 链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。. 在一个顺序存储的循环队列中，队头指针

10、指向队头元素的后一个位置。. 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。. 在使用后缀表示实现计算器类时使用了一个栈的实例，它起的作用是暂存运算对象和计算结果。. 在向顺序栈压入新元素时，要先按栈顶指针指示的位置存入新元素再移动栈顶指针。.在用单链表表示的链式队列中，队头在链表的链尾位置。.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。.在一个循环队列 Q中，判断队满的条件为 Q.rear % MaxSize+1 = Q.front.在一个循环队列Q中，判断队空的条件为 Q.rear+1 = Q.front 。.若让元素1,2,3依次进栈，则出栈次序1

11、,3,2是不可能出现的情况。.若让元素1,2,3依次进栈，则出栈次序3,1,2是不可能出现的情况。.在循环队列中，进队时队尾指针进一，出队时队头指针减一。.在循环队列中，进队时队尾指针进一，出队时队头指针进.在用单链表表示的链式队列Q中，队空条件为 Q-front=Q-rear 。.如果进栈序列是1,2,3,4, 5,6, 7,8。则可能的出栈序列有8!种。四、运算题.试利用运算符优先数法，画出对中缀算术表达式a + b*c-d/e求值时运算符栈 OPTR和运算对象栈OPND的变化。运算符优先数如下表所示：运算符#(*, /, %+, -)isp (栈顶运算符优先级)01537icp (栈外运

12、算符优先级)07421.试利用运算符优先数法，画出将中缀算术表达式a + b*c-d/e改为后缀表达式时运算符栈OPTR的变化。运算符优先数如下表所示：运算符#(*, /, %+, -)isp (栈顶运算符优先级)01537icp (栈外运算符优先级)07421.试画出对后缀算术表达式abc* + de/-求值时运算对象栈 OPND的变化。.将二项式(a + b) i展开，其系数构成杨辉三角形。若想按行将展开式系数的前n行打印出来，需要用到一个队列，存放各行展开式的系数。试画出当 n = 3 的情况下，在打印过程中队列的变化。#include 03b.h /在03b.h 里定义了链栈的抽象数据

13、类型void YANGVI( int n) SqQueue q ; InitQueue(&q); TOC o 1-5 h z q.EnQueue (1); q.EnQueue (1);int i,j,t,s = 0;for (i = 1; i=n ; i+)cout endl; TOC o 1-5 h z 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 ;

14、x = c; y = kS.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 ; charx = e, y = cQ.EnQueue ( h ); Q.EnQueue ( r ); Q.EnQueue ( y )Q.DeQueue(Q,x); Q.EnQueue

15、 ( 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 ); 功能是：五、算法分析题下面的算法中使用了一个栈st ，阅读该算法，

16、回答下列问题：算法的功能是：若字符数组A = m, a, d, a, m, i, m, a, d, a, m变化。#include “ stack.h ”int unknown ( char A , int n ) TOC o 1-5 h z stack st (n+1);int yes = 1, i = 0;char ch ;while( Ai !=“0”)st.Push ( Ai ); i+= 0;while( Ai !=“0”)st.Pop ( ch );if ( Ai = ch ) i+;else yes = 0; break; return yes ;下面的算法中使用了一个栈st ，阅读该算法，回答下列问题：算法的功能是：若单链表中各结点中数据的逻辑顺序为 u, n, i, v, e, r, s, i, t, y算法，跟踪栈的变化。# includestack.h# includeLinkList.htemplatevoid LinkList : unknown ( )/