第三章栈和队列习题

第三章 栈和队列

一，选择

1. 对于栈操作数据的原则是（ ）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 3. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。

A. (rear+1) MOD n=front B. rear=front

C．rear+1=front D. (rear-l) MOD n=front

4当利用大小为n的数组顺序存储一个栈时，假定用top= =n表示栈空，则向这个栈插入一

个元素时首先应执行 语句修改top指针。 A．top++ B．top-- C．top=0 D．top

5. 若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为p1,p2,p3，?，pN,若pN是n，则pi是( )。

A. i B. n-i C. n-i+1 D. 不确定 6. 一个递归算法必须包括（ ）。

A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 7. 执行完下列语句段后，i值为：（ ）

int f(int x)

{ return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));

A．2 B. 4 C. 8 D. 无限递归

8. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。

A． 6 B. 4 C. 3 D. 2 9. 栈和队列的共同点是（ ）。

A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点

10. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。

A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 11. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。

A．仅修改队头指针 B. 仅修改队尾指针

C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改

12. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。

A．队列 B．多维数组 C．栈 D. 线性表 13. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 14. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。

A. rear=rear+1 B. rear=(rear+1) mod (m-1)

C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)

15. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )

A. 1和 5 B. 2和4 C. 4和2 D. 5和1 一，选择 1.B 9.C 二，填空

1．_______是限定仅在表尾进行插入或删除操作的线性表。

3．中缀表达式3*（x+2）-5所对应的后缀表达式为 ；后缀表达式“45*32+-”的值为 。

4. 顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。

5．向一个循环队列中插入一元素时，需首先移动 ，然后再向所指位置 新插入的元素。

6．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是： M= _______

7．用长度为n的数组顺序存储一个栈时，若用top= =n表示栈空，则表示栈满的条件为 。 二，填空

1．栈

3．3 x 2 + * 5 - 15 4．data[++top]=x； 5 ．队尾指针 写入

6．(M+1) MOD N (M+1)% N； 7．top=0

三，应用题

1．指出下列程序段的功能 (1) void Demo1(SeqStack *S){

int i; arr[64] ; n=0 ;

while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1

(2) SeqStack S1, S2, tmp;

DataType x;

...//假设栈tmp和S2已做过初始化

while ( ! StackEmpty (&S1)) {

x=Pop(&S1) ; Push(&tmp,x);

10.D 3.B 11.D 4 B 5.D 6.B 7.B 8.C 12.C 13.A 14.D 15.B }

while ( ! StackEmpty (&tmp) ) {

x=Pop( &tmp); Push( &S1,x); Push( &S2, x); }

(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。

(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。

四，算法设计题

1． 回文是指正读反读均相同的字符序列，如\和\均是回文，但\不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 1 ．

根据提示，算法可设计为： //以下为顺序栈的存储结构定义

#define StackSize 100 //假定预分配的栈空间最多为100个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct{

DataType data[StackSize]; int top; }SeqStack;

int IsHuiwen( char *t)

{//判断t字符向量是否为回文，若是，返回1，否则返回0

SeqStack s; int i , len; char temp;

InitStack( &s);

len=strlen(t); //求向量长度

for ( i=0; i

Push( &s, t[i]); while( !EmptyStack( &s))

{// 每弹出一个字符与相应字符比较 temp=Pop (&s);

if( temp!=S[i]) return 0 ;// 不等则返回0 else i++; }

return 1 ; // 比较完毕均相等则返回 1 }

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