第三章 栈与队列  习题及答案
一、基础知识题
3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：
(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?
(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。
(3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。
3.2 链栈中为何不设置头结点?
答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
3.3 循环队列的优点是什么? 如何判别它的空和满?
答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。
3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?
答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查，到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。
3.5 指出下述程序段的功能是什么?
(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);
    }
    while ( ! StackEmpty (&tmp) )
    {
        x=Pop( &tmp);
        Push( &S1,x);
        Push( &S2, x);
    }
(3) void Demo2( SeqStack *S, int m)
    {    // 设DataType 为int 型
        SeqStack T; int i;
        InitStack (&T);
        while (! StackEmpty( S))
            if(( i=Pop(S)) !=m) Push( &T,i);
        while (! StackEmpty( &T))
        {
            i=Pop(&T); Push(S,i);
        }
    }
(4)void Demo3( CirQueue *Q)
    {    // 设DataType 为int 型
        int x; SeqStack S;
        InitStack( &S);
        while (! QueueEmpty( Q ))
            {x=DeQueue( Q); Push( &S,x);}
        while (! StackEmpty( &s))
            { x=Pop(&S); EnQueue( Q,x );}
    }// Demo3
(5) CirQueue Q1, Q2; // 设DataType 为int 型
    int x, i , m = 0;
    ...    // 设Q1已有内容， Q2已初始化过
    while ( ! QueueEmpty( &Q1) )
        { x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); m++;}
    for (i=0; i< n; i++)
        { x=DeQueue(&Q2) ;
          EnQueue( &Q1, x) ; EnQueue( &Q2, x);}
二、算法设计题
3.6 回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)
3.7 利用栈的基本操作，写一个将栈S中所有结点均删去的算法void ClearStack( SeqStack *S)，并说明S为何要作为指针参数?
3.8 利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数?
3.9 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。
3.10 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。
试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。
3.11 Ackerman 函数定义如下：请写出递归算法。
        [ n+1    当m=0时
AKM ( m , n ) = \{ AKM( m-1 ,1) 当m≠0 ，n=0时
        [ AKM( m-1, AKM( m,n-1)) 当m≠0, n ≠ 0时
3.12 用第二种方法 ，即少用一上元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。
3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。
3.14 对于循环向量中的循环队列，写出求队列长度的公式。
3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。
答案：
3.2 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
3.3 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。
3.4答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指
针开始查，到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。
3.5 答：    (1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。
(2)程序段的功能是利用tmp栈将一个非空栈的所有元素按原样复制到一个空栈当中去。
(3)程序段的功能是将一个非空栈中值等于m的元素全部删去。
(4)程序段的功能是将一个循环队列反向排列，原来的队头变成队尾，原来的队尾变成队头。
(5)首先指出程序可能有印刷错误，for语句中的n应为m才对。这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。
3.6 解：根据提示，算法可设计为：
/
/ishuiwen.h 存为头文件
int  IsHuiwen( char *S)
{
    SeqStack T;
    int i , l;
    char t;
    InitStack( &T);
    l=strlen(S);        //求向量长度
    for ( i=0; i<l/2; i++)    //将一半字符入栈
        Push( &T,  S[i]);
    while( !EmptyStack( &T))
    {   
        // 每弹出一个字符与相应字符比较
        t=Pop (&T);
        if( t!=S[l-i]) { return 0 ;}// 不等则返回0
        i--;
    }
    return  -1 ;    // 比较完毕均相等则返回 -1
}
// 以下程序用于验证上面的算法
//以下是栈定义( 存为stack.h)
//出错控制函数
#include <stdlib.h>
#include <stdio.h>
void Error(char * message)
{
    fprintf(stderr, "Error: %s\n",message);
    exit(1);
空字符串是什么}
// 定义栈类型
#define StackSize  100
typedef char Datatype;
typedef struct{
    Datatype data[StackSize];
    int Top;
} SeqStack;
void InitStack( SeqStack *S)
{   
    //初始化(置空栈)
    S->Top=-1;
}
int  EmptyStack(SeqStack *S)
{    //判栈空
    return  S->Top == -1;   
}
int FullStack (SeqStack *S)
{    // 判栈满
    return S->Top==StackSize-1;
}
void Push (SeqStack *S , Datatype x)
{    //进栈
    if(FullStack(S))   
        Error("Stack overflow");

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。