第三章：栈和队列【习题】

一、选择题

1．栈和队列都是( )。
    A.顺序存储的线性结构    B.限制存取点的线性结构
    C.链接存储的线性结构    D.限制存取点的非线性结构
2．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是( )。
    A. edcba    B. decba    C. dceab    D. abcde
3．若已知一个栈的入栈序列是l，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则Pi为 ( )。
    A.i    B. n-i    C. n-i+l    D.不确定
4．循环队列SQ采用数组空间SQ.data[0，n-l]存放其元素值，已知其头尾指标分别是front和rear，则当前队列中的元素个数是( )。
    A. (rear-front+n)%n     B. rear-front+l
    C. rear-front-l          D. rear-front
5．中缀表达式A-(B+C/D)E的后缀形式是( )。
    A. AB-C+D／E     B. ABC+D／E*
    C. ABCD／E*+-     D. ABCD／+E*-

6．一个队列的入列序列是1，2，3，4，则队列的输出序列是( )。
    A.4，3，2，1     B.1，2，3，4
    C.1，4，3，2     D.3，2，4，1
7．若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。
    A.1和5     B.2和4     C.4和2     D.5和l
8．用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指标指向队尾结点，则在进行出队运算时( )。
    A.仅修改队头指针             B.仅修改队尾指针
    C.对头、队尾指针都要修改   D.对头、对尾指针都可能要修改
    当队列中只有一个元素时，出队后需要清空对头和队尾指针。
9．若进栈序列为a，b，c，则通过入出栈运算可能得到的a，b，c的不同排列个数为( )。
    A.4     B.5     C.6     D.7
10.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队运算后其头指针front值为( )。
    A. front=front+l     B. front=(front+l) %(m-l)
    C.front=(front-1)%m     D. front=(front+l)%m
11.在一个链队中，假定front和rear分别为队首指标和队尾指标，则删除一个结点的运算应执行( )。
    A. front front->next;     B.rear=rear->next;
    C.rear=front->next;     D. front=rear->next;
12.向一个栈顶指针为hs的链栈中插入结点*s时，应执行( )。
    A.hs->next=s；     B. s->next=hs; hs=s;
    C.s->next=hs->next; hs->next=s;     D. s->next=hs; hs=hs->next:
13.在具有n个单元的顺序循环队列中，假定front和rear分别为队首指针和队尾指针，顺序表的下标下界从0开始，则判断队满的条件是( )。
    A.(l+rear)%n==front;     B.(l+rear)% (n-l)==front;
    C.l+rear%n==front;    D.(l+front)%n==rear;
14.若已知一个栈的入栈序列是l，2，3，…，30，其输出序列是p1, p2，p3，…，pn，若p1=30，则p10为( )。
    A. 11     B. 20     C. 30     D. 21
    n-i+1

二、填空题

1．设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队运算的时间复杂度分别为____和____；若只设尾指针，则入队和出队运算的时间复杂度分别为____和____。
O(n)，O(1) O(1)，O(n)
2．基本线性表，栈和队列都是____ 结构。可以在基本线性表的____插入和删除元素；对于栈只能在____ 插入和删除元素；对于队列只能在____插入元素和删除元素。
线性 任何 栈顶 队尾, 队首
3．一个栈的输入序列是235614，则栈的输出序列54321是____。
不可能的
4．对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F和R表示，出队时，队首指针循环加l可表示F=____。
F=(1+F)%M
5．因为顺序栈的空间是有限的。因此，在进行插入运算时，可能会发生____。
上溢
6．假设以s和x分别表示进栈和退栈运算，则对输入序列a，b，c，d，e进行一系列栈运算ssxsxssxxx之后，得到的输出序列为____。
bceda
7．栈顶的位置是随着____ 运算而变化的。
进栈或出栈
8．有如下递归函数，执行语句printf(”%d\n'’，dunno(3))；的结果是_________。

int dunno (int m)
{
    int value；
    if(m == 0)  value = 3;
    else  value = dunno (m - l) + 5;
    return (value)；
}

18
9．设a是含有N个分量的整数数组，写出求n个整数之和的递归定义________，写出求n个整数之积的递归定义____。

10.设栈S和队列Q的初始状态为空，元素a，b，c，d，e，f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b，d，c，f, e，a，则栈S的容量至少应该是________。
3

三、简答题

1．什么是队列的“假溢出”现象？一般有哪几种处理方法？

假设顺序队列的头指针为front，尾指针为rear，队列的容量为MaxSize，下标下界为0，则最后一个单元的下标为MaxSize-1。
(1)“假溢出”是指rear=MaxSize-l，而front≠0的现象。
(2)处理“假溢出”的方法通常有下列3种：
    1)每当从队首删除一个元素时，将队列中剩余的全部元素均向队首方向移动一个位置。
    2)当发生假溢出时，将队列中现有的全部元素均向低下标方向移动一个位置。
    3)上述两种方法都要进行大量元素的移动，效率低。最巧妙的方法是采用循环队列方式。
循环队列是通过头、尾指针的循环来实现的。入队时，修改尾指针：rear=(l+rear)%MaxSize;出队时，修改队首指针：front=(l+front)%MaxSize。

2．试证明：若借助栈由输入序列1，2，3，…，n，得到输出序列P1，P2，P3，…，Pn（它是输入序列 的一个排列），则输出序列中不可能出现这样的情况：若i<j<k，存在输出序列Pk Pi Pj。

要想得到PkPiPj，则必须先按i，j．k顺序全部进栈以后，再进行出栈操作。
显然，第1个出栈的是最后进栈的Pk，而Pk出栈之后，栈顶元素是Pj，因此第2个出栈的应该是Pj。
最后出栈的才是Pi，即出栈序列应该为PkPjPi，而不是PkPiPj。

3．顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为listarray[O...n-l]，队列头指针为front，队列尾指针为rear，则listarray[rear]表示下一个可以插入队列的位置。请解释其原因。

一般环状队列头或尾其中之一要进行特殊处理，否则，当队列“空”或“满”时，只凭q.rear= =q.front无法判断。
一般的处理方法是将q.rear指向下一个要插入的位置。
这样，虽牺牲了一个单元的存储空间，但可以很容易地区分队列“空”或“满”。
当q.rear==q.front时，表示队列“满”，当q.rear==(q.front+l)%n时，表示队列“空”。

4．试推导求解n阶Hanoi塔问题至少需执行的move运算的次数。

求解此方程，得M(n)=2n一l。也可以递推得到，并由“数学归纳法”证明。

四、算法设计题
1．利用两个栈S1和S2模拟一个队列时，要求实现该队列的进队、出队、判队空3种运算。

/*
 * 用一个栈S1作为输入栈，另一个栈S2作为输出栈。
 * 进行入队操作时，总是将数据加入到S1中;进行出队操作时，如果S2不空，则输出S2的元素;
 * 如果S2为空，则读取S1的全部元素加入到S2中，然后由S2输出。
 * 当S1和S2均为空时，表示队列为空。
 * 假设栈的类型为STACK
 */

//(1)进队
void EnQueue(STACK *S, ElemType x)
{
    if (SI->top == MaxSize - l)
        printf(¨overflow”);
    else
        Push(Sl，x); //以进栈代替进队
}
//(2)出队
ElemType DeIQueue(STACK *SI, STACK kS2)
{
    ElemType x;
    if (S2->top ! = -1)
        Pop(S2, &x);
    else
    {
        while (1Empty(S1))
        {
            Pop(S1, &x);
            Push(S2, x);
        }
        Pop(S2, &x);
    }
    return X;
}
//(3)判断队空
int EmptyQueue(STACK *S1, STACK *S2)
{
    if (S1->top == -1 ＆＆S2->top == -l)
        return 1; //两个栈同时为空，则表示队空
    return O;     //队不空，返回O
}

2．假设如题图3-1所示，火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度。试编写算法，输出对这n节车厢进行调度的运算（入栈或出栈运算）序列，以使所有的软席车厢都被调整到硬席车厢之前。

//注意两侧的铁道均为单向行驶道，且两侧不相通。故车辆都必须通过“栈道”进行调度。
typedef char ElemType;
int attemper(STACK *p, STACK *q)
{ //将p栈道的车厢，经调度之后入q栈道，使软席车厢调整到硬席车厢之前
    STACK *temp;
    ElemType e;
    InitStack(temp);
    while (!Empty(p))
    {
        P0p(p，＆e);
        if (e == 'S')
            Push(q，e);
        else
            Push(temp, e);
    }
    while (!Empty(temp))
    {
        Pop(temp; &e);
        Push(q, e);
    }
}

3．求两个正整数m和n的最大公约数可以用如下gcd (m，n)公式表示：
(1)编写一个计算gcd(m，n)的递归过程。

int gcd（int m，int n）
{
    int k;
    if (n == O)
        return (m);
    else
        return (gcd(n, m % n));
}

(2)将上述过程转化成非递归过程。

int gcd2(int m，int n)
{
    int r;
    do
    {
        r = m % n.m = n;
        n = r;
    } while (r);
    return m;
}

(3)画出计算gcd (20，6)的过程及栈的状态变化，给出计算结果。

在top=3时，n的值为0，退栈，并返回2作为最后结果。

4．如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或l来区分尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。

//标志位tag的初值置为“0”。一旦元素入队，使rear==front时，需置tag为“1”;
//反之，一旦元素出队列使front=rear时，需置tag为“0”，以便使下一次进行入队列或出队列操作时(此时front= =rear)
//可由标志位tag的值来区别队列当时的状态是“满”，还是“空”。
#define MaxSize 100
typedef struct
{
    ElemType data[MaxSize];
    int front，rear;
    int tag;
} SqQueue;

int EnQueue(SqQueue *q, ElemType e)
{
    // 插入元素e为q的新队尾元素，如队列满，则置tag = l
    if (q->rear == q->front && tag == l)
        return 0;
    q->data[q->rear] = e;
      q->rear=(q->rear+l))%MaxSize;
      if (q->rear == q->front)
          tag = l;
      return 1;
}

int DeQueue(SqQueue *q, ElemType *e)
{ //若队列不空，则删除q的队头元素，用e返回;如队列空，则置tag=0
    if (q->rear == q->front＆＆tag == 0)
        return O;
    *e = q->data[q->front];
    q->front = (q->front + l) % MaxSize;
    if (q->rear == q->front)
        tag = 0;
    return 1;
}

5．用单链表实现队列，如题图3-2所示，并令front rear FNULL表示队列为空，编写实现队列的如下5种运算的函数：

SetNull:将队列置成空队列。
GetFirst:返回队列的第一个元素。
EnQueue：把元素插入队列的后端。
DeQueue：删除队列的第一个元素。
Empty：判定队列是否为空。

typedef struct Lnode(
ElemType data;
struct Lnode *next;
}
LinkNode;
//根据单链表的特点，实现队列的5种运算的函数如下：
void SetNull(LinkNode **front, LinkNode **rear)
{
    *f ront = NULL;
    *rear = NULL;
}
int GetFirst(LinkNode *front, ElemType *x)
{
    if (front == NULL)
        return O;
    else
    {
        x = front->data;
        return 1;
    }
}
int EnQueue(LinkNode **front, LinkNode **rear, ElemType x)
{
    LinkNode *p;
    if (*rear == NULL)
    { //若队列为空，则直接建立一个链表
        *rear = (LinkNode *)malloc(sizeof(LinkNode));
        (*rear)->d.ata = x;
        *front = *rear;
    }
    else
    { //若不为空，则建立一个结点将其链表链接到末尾
        p = (LinkNode *)malloc(sizeof(LinkNode));
        p->data = x;
        p->next = NULL;
        (*rear)->next = p;
        *rear = p;
    }
    return 1;
}
int DeQueue(LinkNode **front, LinkNode **rear, ElemType *x)
{
    LinkNode *p;
    if (*front == NULL)
        return O;
    else
    {
        p = *front;
        x = p->data;
        *front = (*front)->next;
        free(p);
        if (*front == NULL)
            *rear = NULL;
        return l;
    }
}
int QueueEmpty(LinkNode **front)
{
    if (*front == NULL)
        return l;
    else
        return O;
}

6．若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入( EnQueue)和删除(DeQueue)算法，并给出p为何值时队列空。

//这里使用的循环链表不带头结点，规定p始终指向队尾结点，p->next即为队头结点。
//当p= =NULL时队列为空。队列插入和删除算法如下：
typedef  struct  node(
ElemType data;
struct node *next;
}
QNode;

void EnQueue(QNode **p, ElemType x) //队列插入
{
    QNode *s;
    s = (QNode *)malloc(sizeof(QNode));
    s->data = x;
    if (*p == NULL)
    {
        *p = s;
        (*p) 一 > next = *p;
    }
    else
    {
        s->next = (*p)->next; //将s作为*p之后的结点
        (*p)->next = s;
        *p = s; //*p指向*s
    }
}
int DeQueue(QNode **p, ElemType *x) //队列删除
{
    QNode *s;
    if (*p == NULL)
        return 0;
    if ((*p)->next == NULL)
    { //只有一个结点的情况
        x = (*p)->data;
        free(*p);
        *p = NUIL;
    }
    else
    { //将*p之后结点的data域值赋给x，然后删除之
        s = (*p)->next;
        *x = s->data;
        (*p)->next = s->next;
        free(s);
    }
    return 1;
}

7．编写程序将一个循环队列的内容倒置，该循环队列存储在一个数组A[1...N-1]中，例如，题图3-3 (a)中为倒置前的队列，题图3-3 (b)中为倒置后的队列。

//使用一个栈起到过渡的作用。先将sq队列中元素出队并将其入栈ss，直到队列空为止;然后初始化队列
//即sq->front=sq->rear=n;再出栈并将其入队列，直到栈空为止。对应的算法如下：
#define n 100
void reverse(squeue *sq)
{
    ElemType x;
    STACK *ss;
    ss - (STACK *)malloc(sizeof(STACK)); //栈初始化
    ss->top = -l;
    while (sq->front ! = sq->rear)
    { //队不空时，出队并入栈
        sq->front = (sq->front + l) % n;
        if (sq->front == 0)
            sq->front = n; //队列元素下标从1到n
        x = sq->data[sq->front];
        ss->top++;
        ss->data[ss->top] = x; //将x入栈
    }
    sq->front = sq->rear = n;
    while (ss->top >= 0)
    {
        x = ss->data[ss->top];
        ss->top--;
        sq->rear = (sq->rear + l) % n;
        sq->data[sq->rear] = x;
    }
}

8．已知Ackermann函数的定义如下：写出计算Ack(m, n)的非递归算法

/*
** 计算Ack(m,n)的非递归算法为fun函数。在fun中采用一个二维数组作为栈，其内容如下：
** st (top, O)存储标记，该标记为l(m = 0)、2(m≠O，n = 0)或3 (m + 0, n + 0)。
** st (top, 1)存储Ack (m, n)之值，初值为0。
** st (top, 2)存储m。
** st (top, 3)存储n。
*/
#define MaxSize 5000
int no(int m，int n) //根据m，n之值返回相应的标志
{
    if (m == 0)
        return 1;
    else if (n == O)
        return 2;
    else
        return 3：
}

int fun(int m，int n)
{
    int st[MaxSize][4], top = 0, ml, nl; //top初值为O
    st[top][0] = no(m, n);
    top++;          //先移动栈指针
    st[top][1] = 0; //初值O入栈
    st[top][2] = m; //初值m入栈
    st[top][3] = n; //初值n入栈
    do
    {
        if (st[top][1] == O)
            f if (st[top][O] == 3)
            {
                top++; //入栈
                st[top][1] = 0;
                st[top][2] = st[top - l][2];
                st[top][3] = st[top - l][3] - 1;
                st[top][0] = no(st[top][2], st[top][3]);
            }
        else if (st[top][0] == 2)
        {
            top++; //入栈
            st[top][1] = 0;
            st[top][2] = st[top - l][2] - 1;
            st[top][3] = 1;
            st[top][0] = no(st[top][2], st[top][3]);
        }
        if (st[top][0] == 1)
            st[top][1] = st[top][3] + 1; //求值
    }
    if (top >= l & ＆st[top][1] != 0＆＆st [top - l][0] == 2)
    {
        st[top - l][1] = st[top][1];
        top--; //出栈
    }
    else if (top >= l＆＆st[top][1] 1 = 0＆ & st[top一1][O] == 3)
    {
        nl = st[top][1];
        ml = st[top - l][2] - 1;
        top--; //出栈
        st[top][1] = 0;
        st[top][2] = ml;
        st[top][3] = nl;
        st[top][0] = no(st[top][2], st[top][3]);
    }
    if (top == l＆ & st[top][1] != 0)
        break; //栈中只有1个元素，且已计算出值，则退出循环
    while (top >= l)
        ;
    return (st[1][1]); //st [1][1]就是所求的函数值
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,456评论 5赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,370评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,337评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,583评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,596评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,572评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,936评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,595评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,850评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,601评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,685评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,371评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,951评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,934评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,167评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 43,636评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,411评论 2赞 342