数据结构习题精解（C语言实现+微课视频）
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

3.3　栈的典型试题精选与解析

3.3.1　典型试题

一、单项选择题

1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（　　）。

A．a，b，c，d，e

B．d，e，c，b，a

C．d，c，e，a，b

D．e，d，c，b，a

2、设计一个判别表达式中括号是否配对的算法，采用（　　）数据结构最佳。

A．顺序表

B．链表

C．队列

D．栈

3、链栈执行出栈操作，并将出栈的元素存入x中，应执行下列（　　）。

A．x=top;top=top->next

B．x=top->data

C．top=top->next;x=top->data

D．x=top->data;top=top->next

4、经过对栈s进行以下操作后：

     InitStack(s);  Push(s,a);  Push(s,b);  Pop(s,&x);  top(s,&x);

变量x的值为（　　）。

A．a

B．B

C．NULL

D．FALSE

5、【2013年统考试题】一个栈的入栈序列为1、2、3、...、n，其出栈序列为p1、p2、p3、...、pn。若p2=3，则p3可能取值的个数是（　　）。

A．n-3

B．n-2

C．n-1

D．无法确定

6、设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是（　　）。

A．1

B．2

C．3

D．4

7、表达式a*（b+c）-d的后缀表达式是（　　）。

A．abcd+-

B．abc+*d-

C．abc*+d-

D．-+*abcd

8、一个递归算法必须包含（　　）。

A．递归调用

B．终止条件和迭代部分

C．迭代部分

D．终止条件和递归部分

9、将递归算法转换成对应的非递归算法时，通常需要使用（　　）来保存中间结果。

A．队列

B．栈

C．链表

D．树

10、执行完以下程序段后，b的值为（　　）。

A．2

B．4

C．8

D．无限递归

11、向一个栈顶指针为top的链栈中插入一个x结点（不设头结点），则执行语句（　　）。

A．top->next=x

B．x->next=top->next;top->next=x;

C．x->next=top;top=x;

D．x->next=top;top=top->next

12、判定一个顺序栈S（栈空间大小为n）为空的条件是（　　）。

A．S->top==0

B．S->top!=0

C．S->top==n

D．S->top!=n

13、【2017年统考试题】下列关于栈的叙述中，错误的是（　　）。

I．采用非递归方式重写递归程序时必须使用栈。

II．函数调用时，系统要用栈保存必要的信息。

III．只要确定了入栈次序，即可确定出栈次序。

IV．栈是一种受限的线性表，允许在其两端进行操作。

A．仅I

B．仅I、II、III

C．仅I、III、IV

D．仅II、III、IV

14、【2018年统考试题】若栈S1中保存整数，栈S2中保存运算符，函数F（）依次执行下述各步操作：

（1）从S1中依次弹出两个操作数a和b。

（2）从S2中弹出一个运算符op。

（3）执行相应的运算b op a。

（4）将运算结果压入栈S1中。

假定S1中的操作数依次是5、8、3、2，其中，2在栈顶。S2中的运算符依次是*、-、+，其中，+位于栈顶。调用3次F（）后，S1栈顶保存的值是（　　）。

A．-15

B．15

C．-20

D．20

15、【2015年统考试题】已知程序如下：

程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（　　）。

A．main（）->s（1）->s（0）

B．s（0）->s（1）->main（）

C．main（）->s（0）->s（1）

D．s（1）->s（0）->main（）

16、【华中科技大学考研试题】（多选）若已知一个栈的入栈序列是1、2、3、4，其出栈序列是p1、p2、p3、p4，则p2、p4可能是（　　）。

A．2、4

B．2、1

C．4、3

D．3、4

17、【北京理工大学考研试题】向一个栈顶指针为h的带头结点的链栈中插入指针s所指向的结点时，应执行（　　）。

A．h->next=s;

B．s->next=h;

C．s->next=h;h->next=s;

D．s->next=h->next;h->next=s;

18、【武汉大学考研试题】假设n个元素入栈序列是1、2、3、…、n，其出栈序列是p1、p2、p3、…、pn，若p1=3，则p2的值为（　　）。

A．一定是2

B．一定是1

C．不可能是1

D．以上都不对

二、综合分析题

1、已知栈的基本操作函数：

     int InitStack(SeqStack     *S);  //构造空栈
     int StackEmpty(SeqStack S);//判断栈空
     int Push(SeqStack    *S,ElemType e);//入栈
     int Pop(SeqStack    *S,ElemType   *e);//出栈

函数Conversion实现十进制数转换为八进制数，请将函数补充完整。

2、写出算法的功能。

3、【浙江大学考研试题】下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中，例如123存放为“321”。

4、利用栈的后进先出思想将（5*（12-3）+4）/2转换为后缀表达式，并根据后缀表达式求其算术表达式的值。要求按照表3-3给出中缀表达式转换为后缀表达式每一步入栈和出栈过程，并画出利用后缀表达式求解表达式的值时每一步操作栈中元素的变化。

三、算法设计题

1、建立一个顺序栈。从键盘上输入若干个字符，以回车键结束，实现元素的入栈操作。然后依次输出栈中的元素，实现出栈操作。要求顺序栈由栈顶指针、栈底指针和存放元素的数组构成。

2、建立一个链栈。从键盘上输入若干个字符，以回车键结束，实现元素的入栈操作。然后依次输出栈中的元素，实现出栈操作。

3、Fibonacci数列的序列为0、1、1、2、3、5、8、13、21、…，其中每个元素是前两个元素之和。其递归定义如下：

编写求该数列的第N个元素的递归与非递归的算法。

4、编写求n！的递归与非递归算法。

5、试利用栈的后进先出思想，编写非递归算法，求C（4，3）的值，并给出栈的变化过程。

6、【北京航空航天大学考研试题】已经Ackermann函数的定义如下：

（1）写出Ack（2，1）的计算过程。

（2）利用栈的算法思想实现Ack（m，n）的非递归算法。

7、有两个栈S1和S2都采用顺序结构存储，并且共享一个存储区。为了尽可能利用存储空间，减少溢出的可能，采用栈顶相向、迎面增长的方式，试设计S1和S2有关入栈和出栈算法。

上一章目录下一章