1. 判断题

（l）栈是运算受限制的线性表。 

（2）在栈空的情况下，不能作出栈操作，否则产生溢出。 

（3）栈一定是顺序存储的线性结构。

参考答案： (1） √     (2）√    (3）×   

2. 选择题

(l）设入栈序列是 1 、 2 、 … 、 n ，入栈过程中不允许中途出栈，则第 i 个输出的元素是 (   ）。

A．不确定             B.i                  C. n - i              D. n - i + 1

(2）铁路调度用“栈”，假设进栈车厢编队序列为“ ABC " （进栈过程中可以出栈），出栈则有许多编队序列，以下不可能出现的序列是（  ）。

A. " ABC "             B. " CBA "            C. " BAC "          D. " CAB "

(3）当栈中当前元素为 n 个，此时进行进栈运算时发生上溢，则该栈的最大、容量为（  ）。

A. n/2                 B. n - 1               C. n                D. n + 1

(4）在栈中存取数据的原则是（  ）。

A．先进先出           B．后进先出         C．后进后出        D．随意进出

 (5）插入和删除只能在一端进行的线性表，称为（  ）。

A．队列               B．循环队列         C．栈              D. 循环栈

 (6）栈结构通常采用的两种存储结构是(   ）。

A．线性存储结构和链式存储结构       B．散列方式和索引方式    

C．链式存储结构和数组               D.线性存储结构和非线性存储结构

 参考答案：D     D     C      B     C     C    

3. 简述利用两个栈模拟一个队列的入队、出对、判断队空等运算。

答：利用两个栈模拟一个队列的运算的基本思想是：

用一个栈S1作为输入栈，而另一个栈S2作为输出栈。

当入队时，总是将数据加入到作为输入的栈（即S1）中；

在输出时，如果输出栈S2已空，则从输入栈S1将以输入到输入栈中的数据输入到输出栈S2中，然后由输出栈S2输出数据，如果输出栈S2不为空，则就应由输出栈S2直接输出数据元素。

显然，当S1、S2均为空时，表示队列为空。

4. 若已知一个栈的入栈序列是1，2，3，4，…，n ，其输出序列是P1，P2，P3，…，Pn，若P1=n，则Pi为多少？

当P1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的，那么输入顺序必定是1，2，3，4，…，n，则出栈的序列是n ，…，4，3，2，1，所以Pi = n-i+1。

5. 对于一个栈，给出输入项A，B，C。如果输入项序列由A，B，C组成，试给出全部可能的输出序列。

本题利用栈的“后进先出”的特点，有如下几种情况：

A进A出B进B出C进C出产生输出序列ABC

A进A出B进C进C出B出产生输出序列ACB

A进B进B出A出C进C出产生输出序列BAC

A进B进B出C进C出A出产生输出序列BCA

A进B进C进C出B出A出产生输出序列CBA

不可能产生输出序列CBA。

6. 利用栈的基本操作，写一个将栈S中所有结点均删除的算法void ClearStack (SeqStack*S)，并说明S为何要作为指针参数？

要将栈S中所有结点均删除，可以利用栈的基本操作Pop（出栈）运算来实现，从栈顶元素开始，不断执行出栈运算，直到栈为空为止。实现本题功能的算法如下：

    voidClearStack (SeqStack*S)    
    {
        while (!StackEmpty (*S) )Pop (*S );
    }

说明：根据C语言的特征，函数形参为指针变量，可以将该形参在函数体内所修改的值返回给实参。根据题意，栈S在执行完该函数后，其结点已全部删除，内容已发生修改，故，S要作为指针参数。 

7. 利用栈的基本操作，写一个返回栈中结点个数的算法int  StackSize (SeqStackS)，并说明S为何不用作为指针参数？

根据题意，设一变量count来统计栈中结点的个数，从栈顶元素出发，循环执行出栈运算，直到栈空。实现本题功能的函数如下：

    intStackSize (SeqStackS)    
    {
    intcount=0;
    while (!StackEmpty (S)) 
    {
    conut++;
    Pop (s);
    }
    }

说明：依据题意，该算法只需统计栈中结点个数，执行完函数后不能修改实参栈的内容。所以，在该函数中，S不能用作指针参数。

8. 如果用一个循环数组qu[0，m0-1]表示队列时，该队列只有一个头指针front，不设队尾指针rear，而改置计数器count用以记录队列中结点的个数。

（1）编写实现队列的五个基本运算；

（2）队列中能容纳元素的最多个数还是m0-1吗？

解：

（1）依题意，有如下条件：

队列为空：count==0，front==1

队列为满：count==m0

队列尾的第一个元素位置==（front+count）% m0

队列首的第一个元素位置==（front+1）% m0

队列类型定义如下：

typedef int qu[m0]；

由此得到如下对应上述基本运算的5个函数如下：

    /* m0定义为全局变量 */    
    void makenull（front，count） /*使队列q为空*/
    int front，count；
    {   front=1；
    count=0；
    }
    int empty（count） /*判定队列q是否为空*/
    int count；
    {   if（count==0）return（1）；
    else return（0）；
    }
    void pop（q，front，count，x） /*取队列头元素给x*/
    qu q；
    int front，count；
    ElemType *x；
    {   if（count==0）printf（”队列下溢出\n”）；
    else
    {   front=（front+1）% m0；
    *x=q[front]；
    }
    }
    void enqueue（q，x，front，count）/*将元素x入队列*/
    qu q；
    int front，count；
    ElemType x；
    {   int place；
    if（count==0）printf（”队列上溢出\n”）；
    else
    {   count++；
    place=（front+count）% m0；
    }
    }
    void dequeue（q，front，count）/*删除队列头元素*/
    qu q；
    int front，count；
    {  if（count==0）printf（”队列下溢出\n”）；
    else
    {  front=（front+1）% m0；
    count--；
    }
    }

（2）队列中可容纳的最多元素个数为m0个。

来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=352

• 数据结构-排序-练习题2018-09-10 21:49
• 数据结构-线性表练习题2018-09-10 21:37
• 数据结构-绪论-练习题2018-09-10 21:51
• 题目：广义表的存储结构2018-09-10 21:46