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

），且 top 是指向栈顶的指针。若想摘除链式栈的栈顶结点，并 x 中，则应执行操作（ ; top = top->link ; 11. 设循环队列的结构是

#define MaxSize 100 typedef int ElemType; typedef struct {

1. 2. 3. 4. 5. 6. 7. 8. 9. 第三章 栈和队列 试

题

、单项选择题

栈的插入和删除操作在（ ）进行。

A. 栈顶

B. 栈底 当利用大小为 n 的数组顺序存储一个栈时， 先应执行（ A. top++ ; ）语句修改 top 指针。 B.

top -- ; C. 任意位置 假定用 top ==n 表示栈空， C. top = 0 ; D. 指定位置 则向这个栈插入一个元素时， 首 D. top ; 若让元素 1,2,3 A. 3, 2, 1

依次进栈，则出栈次序不可能出现（ B. 2, 1, 3 C. 3, 1, 2 在一个顺序存储的循环队列中，队头指针指向队头元素的（ A. 前一个 B. 后一个 当利用大小为 n 的数组顺序存储一个队列时， A. n-2 B. n-1 从一个顺序存储的循环队列中删除一个元素时， A. 队头指针加一 C. 取出队头指针所指的元素 C. 当前 ）种情况。 D. 1, 3, 2 ）位置。 D. 后面 该队列的最大长度为（ C. n ）。 D. n+1 （ ）。 B. 队头指针减一 D. 取出队尾指针所指的元素 假定一个顺序存储的循环队列的队头和队尾指针分别为 front 和 rear ，则判断队空的条件为（ A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear ）。 假定一个链式队列的队头和队尾指针分别为 A. front == rear C. rear != NULL front 和 rear ，则判断队空的条件为（ B. front != NULL D. front == NULL ）。 设链式栈中结点的结构为（ data, link 指针 s

所指的结点，则应执行操作（ A. top->link = s ; C. s->link = top ; top = s ; ），且 top 是指向栈顶的指针。若想在链式栈的栈顶插入一个由 ）。 B. s->link = top->link ; top->link = s

D. s->link = top ; top = top->link

10. 设链式栈中结点的结构为（ data, link 将被摘除结点的值保存到 A. x = top->data C. x = top ; top = top->link ）。

B. top = top->link ; x = top->data

D. x = top->data ;

若设顺序栈的最大容量为 MaxSize ，则判断栈满的条件是ElemType base[MaxSize] ; int front, rear

} Queue;

若有一个 Queue 类型的队列 A. == ; C. + == MaxSize ; Q ， 则判断队列满的条件应是语句（ B. - == MaxSize ; D. == +1） % MaxSize ; ）。 12. 设循环队列的结构是

#define MaxSize 100 typedef int ElemType; typedef struct { ElemType base[MaxSize] int

front, rear ; } Queue; 若有一个 Queue 类型的队列 Q ，

A. - + MaxSize ) % MaxSize

B. - +1 ;

C. - -1 ; 则应用语句（ ）计算队列元素个数。

D. - Qfront 13. 在做进栈运算时 , 应先判断栈是否（ A. 空 B. 满 C. 上溢 D. 下溢 14. 为增加内存空间的利用率和减少溢出的可能性， （ ）分别设在这片内存空间的两端。 A. 长度 B. 深度 由两个栈共享一片连续的内存空间时 , 应将两栈的 C. 栈顶 D. 栈底

15. 使用两个栈共享一片内存空间时，当（ A. 两个栈的栈顶同时到达这片内存空间的中心点 B. 其中一个栈的栈顶到达这片内存空间的中心点 C. 两个栈的栈顶在这片内存空间的某一位置相遇 D. 两个栈均不空 , 且一个栈的栈顶到达另一个栈的栈底 ）时，才产生上溢。 1. 、填空题 栈是一种限定在表的一端插入和删除的线性表，它的特点是 2. 队列是一种限定在表的一端插入，在另一端删除的线性表，它的特点是 3. 队列的插入操作在 进行，删除操作在 进行。 4.

向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把待插入元素写入到这个位置上。 5. 从一个顺序栈中删除元素时，需要将

前移一位位置。 6.

7.

当用长度为 MaxSize 的数组顺序存储一个栈时，若用 top ==MaxSize 表示栈空，则表示栈满的条件为

19. 后缀表达式“ 4 5 * 3 2 + - ”的值为

20.设有一个顺序栈 S,元素S i , s 2, s 3, s 4, s 5, s 6依次进栈，如果 6个元素的出栈顺序为 S 2, s 3, s 4, s 6,

s 5, s 1，则顺序栈的容量至少应为

三、判断题

每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列。

1. 2. 链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。

3. 在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。

4. 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。

5. 在使用后缀表示实现计算器类时使用了一个栈的实例，它起的作用是暂存运算对象和计算结果。

6. 在向顺序栈压入新元素时，要先按栈顶指针指示的位置存入新元素再移动栈顶指针。

在向一个链式栈插入一个新结点时，首先把栈顶指针中存放的结点地址赋给新结点的指针域，然后把 新结点的存储位置赋给

10. 向一个栈顶指针为 top 的链式栈中插入一个新结点 *p 时，应执行

11. 从一个栈顶指针为 top 的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 操作。

12. 设循环队列Q 的队头和队尾指针分别为 front 和rear ，则判断队空的条件为 13.

设循环队列Q 的队头和队尾指针分别为 front 和rear ，队列的最大容量为

MaxSize ，且规定判断队空 的条件为 == ，则判断队满的条件为

15. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为 16. 假定 front 和 rear 分别为链式队列的队头和队尾指针，则该队列中只有一个结点的条件为

18. 中缀表达式 3*(x+2)-5 所对应的后缀表达式为

8. 在一个链式栈中，若栈顶指针等于 NULL 则为

9. 操作。

14. 向一个循环队列中插入元素时，需要首先移动

，然后再向所指位置写入新插入的元素。

或该队列

17. 双端队列是限定插入和删除操作在表的

进行的线性表。

7. 在用单链表表示的链式队列中，队头在链表的链尾位置。

4.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

将二项式（a + b）i展开，其系数构成杨辉三角形。若想按行将展开式系数的前n行打印出来，需要用到一个队列，存放各行展开式的系数。试画出当n = 3的情况下，在打印过程中队列的变化。

#include "” //在里定义了链栈的抽象数据类型

void YANGVI （ int n ） {

SqQueue q; In itQueue（&q）;

（1）

int

8.

9. 在一个循环队列Q中，判断队满的条件为% MaxSize+1

10.在一个循环队列Q中，判断队空的条件为+1 ==。

11.若让元素1,2, 3 依次进栈，则出栈次序1,3, 2 是不可能出现的情况。

12.若让元素1,2, 3 依次进栈，则出栈次序3, 1,2 是不可能出现的情况。

13.在循环队列中，进队时队尾指针进一，出队时队头指针减一。

14.在循环队列中，进队时队尾指针进一，出队时队头指针进一。

15.在用单链表表示的链式队列Q 中，队空条件为 Q->fro nt == Q->rear 。

16.如果进栈序列是1,2, 3, 4, 5, 6, 7, 8 。则可能的出栈序列有 8 ！种。

四、运算题

试利用运算符优先数法，画出对中缀算术表达式象栈

OPND勺变化。运算符优先数如下表所示：

1. 求值时运算符栈 OPTR和运算对

2. 试利用运算符优先数法，画出将中缀算术表达式的变化。

运算符优先数如下表所示：

改为后缀表达式时运算符栈 OPTR

3. 试画出对后缀算术表达式ab c * + de / - 求值时运算对象栈 OPND的变化。

7. 在用单链表表示的链式队列中，队头在链表的链尾位置。

for

4.

；(1)；

i, j, t, s = 0 ;

(i = 1 ; i <= n ; i++ ) {

cout << endl;

}

(0) ;

for ( j = 1 ; j <= i+2 ; j++ ) { (t) ;

(s+t) ;

s = t ;

if ( j != i+2 ) }

输出结果：

void main( ) {

queue Q; char x = 'e', y = 'c'

(Q,x) ; ( x )

( 'a' )

输出结果：

简述下述算法功能

void unknown ( Queue &Q ) { Stack S ; int d;

while (! ( ) )

{ ( d ) ; ( d ) ; } while (! ( ) )

{ ( d ) ; ( d ) ; }

5. main( ) {

stack S ; char x, y ; x = 'c' ; y = 'k' J ( x ) ; ( 'a' ) ; ( y ) ( x ) ; ( 't' ) ; ( x ) ( x ) ; ( 's'

) J while (! ( ) ) { ( y ) cout << y << endl;

写出下列程序段的输出结果

; cout

void << y; } << s <<

cout 6. 写出下列程序段的输出结果

( 'h' ) ( 'r' ) ; ( y )

while (! ( ) ) { ( y ) ; cout

<< y; } cout << y << endl;

7.

功能是： 五、

1.

算法分析题 下面的算法中使用了一个栈 st ，阅读该算法，回答下列问题： (1) 算法的功能是： _____________________________________________ (2) 若字符数组 A[ ] = { m, a, d, a, m, i, m, a, d, a, m } ，执行这个算法，跟踪栈的变化。 #include int

unknown ( stack< char A[ ], char > st (n+1) int yes

= 1, i = 0 char ch ;

while ( A[i] != “

i = 0 ; while ( A[i] != “

( ch ) ; int 0” ) 0” ) { ( A[i] ) ; i++ ; } if ( A[i] == ch ) i++

else { yes = 0 ; break; } }

return

yes ;

面的算法中使用了一个栈 (1) 算法的功能是： ________

(2) 若单链表中各结点中数据的逻辑顺序为 踪栈的变化。

2. st ，阅读该算法，回答下列问题： { u, n, i, v, e, r, s, i, t, y } ，执行这个算法，跟 #include ""

#include "" template void LinkList :: unknown ( ) { // 此单链表带有表头结点，它的表头指针为

Stack*> S ; ListNode while p = first while first 。 *p = first->link , *q ; ( p != NULL ) { (p) ; p = p->link ; } ; p->link = NULL ( !( ) ) { (q ) ; q->link = p->link p->link = q ;

// 将栈中保存的结点依次出栈 六、算法设计题

本文来源：https://www.bwwdw.com/article/i5tl.html