数据结构习题汇编03第三章栈和队列试题

1、如果您需要使用本文档，请点击下载按钮下载!第三章 栈和队列 试题一、单项选择题l 栈的插入和删除操作在（ ）进行。a. 栈顶b. 栈底c. 任意位置d. 指定位置l 当利用大小为n的数组顺序存储一个栈时，假定用top=n表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。a. top+;b. top-;c. top = 0;d. top;l 若让元素1,2,3依次进栈，则出栈次序不可能出现（ ）种情况。a. 3, 2, 1b. 2, 1, 3c. 3, 1, 2d. 1, 3, 2l 在一个顺序存储的循环队列中，队头指针指向队头元素的（ ）位置。a. 前一个b. 后一个c.

2、 当前 d. 后面l 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。a. n-2 b. n-1c. n d. n+1l 从一个顺序存储的循环队列中删除一个元素时，需要（ ）。a. 队头指针加一b. 队头指针减一c. 取出队头指针所指的元素d. 取出队尾指针所指的元素l 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ）。a. front+1 = rearb. rear+1 = frontc. front = 0d. front = rearl 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ）。a

3、. front = rearb. front != nullc. rear != nulld. front = nulll 设链式栈中结点的结构为（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;l 设链式栈中结点的结构为（data, link），且top

4、是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到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;l 设循环队列的结构是 #define maxsize 100 typedef int elemtype;1 / 71如果您需要使用本文档，请点击下载按钮下载! typedef struct elemtype basemaxsize; int

5、 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;l 设循环队列的结构是 #define maxsize 100 typedef int elemtype; typedef struct elemtype basemaxsize; int front, rear; queue;若有一个queue类型的队列q

6、，则应用语句（ ）计算队列元素个数。a. (q.rear - q.front + maxsize ) % maxsize;b. q.rear - q.front +1;c. q.rear - q.front -1;d. q.rear - qfront;l 在做进栈运算时,应先判断栈是否（ ）a. 空 b. 满c. 上溢d. 下溢l 为增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时, 应将两栈的（ ）分别设在这片内存空间的两端。 a. 长度b. 深度c. 栈顶d. 栈底l 使用两个栈共享一片内存空间时，当（ ）时，才产生上溢。a. 两个栈的栈顶同时到达这片内存空间的中心

7、点b. 其中一个栈的栈顶到达这片内存空间的中心点c. 两个栈的栈顶在这片内存空间的某一位置相遇d. 两个栈均不空, 且一个栈的栈顶到达另一个栈的栈底二、填空题l 栈是一种限定在表的一端插入和删除的线性表，它的特点是_。l 队列是一种限定在表的一端插入，在另一端删除的线性表，它的特点是_。l 队列的插入操作在_进行，删除操作在_进行。l 向一个顺序栈插入一个元素时，首先使_后移一个位置，然后把待插入元素写入到这个位置上。l 从一个顺序栈中删除元素时，需要将_前移一位位置。2 / 72如果您需要使用本文档，请点击下载按钮下载!l 若设顺序栈的最大容量为maxsize，则判断栈满的条件是_。l 当用

8、长度为maxsize的数组顺序存储一个栈时，若用top = maxsize表示栈空，则表示栈满的条件为_。l 在一个链式栈中，若栈顶指针等于null则为_。l 在向一个链式栈插入一个新结点时，首先把栈顶指针中存放的结点地址赋给新结点的指针域，然后把新结点的存储位置赋给_。l 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行_和_操作。l 从一个栈顶指针为top的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行_操作。l 设循环队列q的队头和队尾指针分别为front和rear，则判断队空的条件为_。l 设循环队列q的队头和队尾指针分别为front和rear，队列的最大

9、容量为maxsize，且规定判断队空的条件为q.front = q.rear，则判断队满的条件为_。l 向一个循环队列中插入元素时，需要首先移动_，然后再向所指位置写入新插入的元素。l 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为_或该队列_。l 假定front和rear分别为链式队列的队头和队尾指针，则该队列中只有一个结点的条件为_。l 双端队列是限定插入和删除操作在表的_进行的线性表。l 中缀表达式3*(x+2)-5所对应的后缀表达式为_。l 后缀表达式“4 5 * 3 2 + -”的值为_。l 设有一个顺序栈s，元素s1, s2, s3, s4, s5, s6依次进栈，

10、如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为_。三、判断题l 每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列。l 链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。l 在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。l 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。l 在使用后缀表示实现计算器类时使用了一个栈的实例，它起的作用是暂存运算对象和计算结果。3 / 73如果您需要使用本文档，请点击下载按钮下载!l 在向顺序栈压入新元素时，要先按栈顶指针指示的位置存入新元素再移动栈顶指针。l 在用单

11、链表表示的链式队列中，队头在链表的链尾位置。l 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。l 在一个循环队列q中，判断队满的条件为q.rear % maxsize+1 = q.front。l 在一个循环队列q中，判断队空的条件为q.rear+1 = q.front。l 若让元素1, 2, 3依次进栈，则出栈次序1, 3, 2是不可能出现的情况。l 若让元素1, 2, 3依次进栈，则出栈次序3, 1, 2是不可能出现的情况。l 在循环队列中，进队时队尾指针进一，出队时队头指针减一。l 在循环队列中，进队时队尾指针进一，出队时队头指针进一。l 在用单链表表示的链式队列

12、q中，队空条件为q->front = q->rear。l 如果进栈序列是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的变化。运算符优先数如下表所示：运算符#(*, /,

13、%+, -)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);

14、 q.enqueue (1); int i, j, t, s = 0;4 / 74如果您需要使用本文档，请点击下载按钮下载!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 = 

15、9;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 = &

16、#39;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

17、&q ) stack s; int d; while (!q.isempty ( ) ) q.dequeue ( d ); s.push ( d ); while (!s.isempty ( ) ) 5 / 75如果您需要使用本文档，请点击下载按钮下载! s.pop ( d ); q.enqueue ( d ); 功能是：_五、算法分析题l 下面的算法中使用了一个栈st，阅读该算法，回答下列问题：l 算法的功能是：_l 若字符数组a = m, a, d, a, m, i, m, a, d, a, m ，执行这个算法，跟踪栈的变化。#include “stack.h”int unknow

18、n ( 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;l 下面的算法中使用了一个栈st，阅读该算法，回答下列问题：l 算法的功能是：_(2) 若单链表中各结点中数据的逻辑顺序为 u, n, i, v, e, r, s, i, t, y

19、 ，执行这个算法，跟踪栈的变化。#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 ( !