logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

【原】数据结构——栈PTA习题

 流楚丶格念 2022-01-14

文章目录

单选题

题号题目答案
1假设有5个整数以1、2、3、4、5的顺序被压入堆栈，且出栈顺序为3、5、4、2、1，那么为了获得这样的输出，堆栈大小至少为： 4
2设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？ 3 2 1 5 4
3设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是： 1或者5
4从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，则执行： X= ST->data; ST = ST->next;
5若top为指向栈顶元素的指针，判定栈S（最多容纳m个元素）为空的条件是： S->top == -1
6若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？ 将链表头设为top
7若栈采用顺序存储方式存储，现两栈共享空间V[m]：top[i]代表第i（i=1或2）个栈的栈顶；栈1的底在V[0]，栈2的底在V[m-1]，则栈满的条件是： top[1]+1==top[2]
8给定一个堆栈的入栈序列为{ 1, 2, ⋯, n }，出栈序列为{ p​1​​ , p​2​​ , ⋯, p​n​​ }。如果p​2​​ =n，则存在多少种不同的出栈序列？ n−1
9在这里插入图片描述 仅 1、3、4
10在这里插入图片描述 15

函数题

6-1 在一个数组中实现两个堆栈 (29分)

本题要求在一个数组中实现两个堆栈。

函数接口定义：

Stack CreateStack( int MaxSize );
bool Push( Stack S, ElementType X, int Tag );
ElementType Pop( Stack S, int Tag );

其中Tag是堆栈编号，取1或2；MaxSize堆栈数组的规模；Stack结构定义如下：

typedef int Position;
struct SNode {
    ElementType *Data;
    Position Top1, Top2;
    int MaxSize;
};
typedef struct SNode *Stack;

注意：如果堆栈已满，Push函数必须输出“Stack Full”并且返回false；如果某堆栈是空的，则Pop函数必须输出“Stack Tag Empty”（其中Tag是该堆栈的编号），并且返回ERROR。

输入样例：

5
Push 1 1
Pop 2
Push 2 11
Push 1 2
Push 2 12
Pop 1
Push 2 13
Push 2 14
Push 1 3
Pop 2
End

输出样例：

Stack 2 Empty
Stack 2 is Empty!
Stack Full
Stack 1 is Full!
Pop from Stack 1: 1
Pop from Stack 2: 13 12 11

代码

#include <stdio.h>
#include <stdlib.h>

#define ERROR 1e8
typedef int ElementType;
typedef enum { push, pop, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
struct SNode {
    ElementType *Data;
    Position Top1, Top2;
    int MaxSize;
};
typedef struct SNode *Stack;

Stack CreateStack( int MaxSize );
bool Push( Stack S, ElementType X, int Tag );
ElementType Pop( Stack S, int Tag );

Operation GetOp();  /* details omitted */
void PrintStack( Stack S, int Tag ); /* details omitted */

int main()
{
    int N, Tag, X;
    Stack S;
    int done = 0;

    scanf("%d", &N);
    S = CreateStack(N);
    while ( !done ) {
        switch( GetOp() ) {
        case push: 
            scanf("%d %d", &Tag, &X);
            if (!Push(S, X, Tag)) printf("Stack %d is Full!\n", Tag);
            break;
        case pop:
            scanf("%d", &Tag);
            X = Pop(S, Tag);
            if ( X==ERROR ) printf("Stack %d is Empty!\n", Tag);
            break;
        case end:
            PrintStack(S, 1);
            PrintStack(S, 2);
            done = 1;
            break;
        }
    }
    return 0;
}

/* 你的代码将被嵌在这里 */

Stack CreateStack(int MaxSize)
{
    struct SNode *S = NULL;
    S = (struct SNode*)malloc(sizeof(struct SNode));

    S->Data =(int *)malloc(MaxSize * sizeof(int));
    S->Top1 = -1;       
    S->Top2 = MaxSize;  // 两个栈是   首尾

    S->MaxSize = MaxSize;
    return S;

}
bool Push(Stack S, ElementType X, int Tag)
{
    // 判断是否满了   这俩栈如果相对差1就是满了
    if (S->Top2 - S->Top1 == 1)
    {
        printf("Stack Full\n");
        return false;
    }
    else
    {
        // 栈编号
        if (Tag == 1)
        {
            S->Data[++(S->Top1)] = X;
        }
        else if (Tag == 2)
        {
            S->Data[--(S->Top2)] = X;
        }
        return true;
    }
}
ElementType Pop(Stack S, int Tag)
{
    if (Tag == 1)
    {
        if (S->Top1 == -1)
        {
            printf("Stack %d Empty\n", Tag);
            return ERROR;
        }
        else 
            return S->Data[(S->Top1)--];
    }
    else if (Tag == 2)
    {
        if (S->Top2 == S->MaxSize)
        {
            printf("Stack %d Empty\n", Tag);
            return ERROR;
        }
        else
        {
            return S->Data[(S->Top2)++];
        }
    }

}

6-2 另类堆栈 (21分)

在栈的顺序存储实现中，另有一种方法是将Top定义为栈顶的上一个位置。请编写程序实现这种定义下堆栈的入栈、出栈操作。如何判断堆栈为空或者满？

函数接口定义：

bool Push( Stack S, ElementType X );
ElementType Pop( Stack S );

其中Stack结构定义如下：

typedef int Position;
typedef struct SNode *PtrToSNode;
struct SNode {
    ElementType *Data;  /* 存储元素的数组 */
    Position Top;       /* 栈顶指针       */
    int MaxSize;        /* 堆栈最大容量   */
};
typedef PtrToSNode Stack;

注意：如果堆栈已满，Push函数必须输出“Stack Full”并且返回false；如果队列是空的，则Pop函数必须输出“Stack Empty”，并且返回ERROR。

输入样例：

4
Pop
Push 5
Push 4
Push 3
Pop
Pop
Push 2
Push 1
Push 0
Push 10
End

输出样例：

Stack Empty
3 is out
4 is out
Stack Full
0 1 2 5

代码


#include <stdio.h>
#include <stdlib.h>

#define ERROR -1
typedef int ElementType;
typedef enum { push, pop, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct SNode *PtrToSNode;
struct SNode {
    ElementType *Data;  /* 存储元素的数组 */
    Position Top;       /* 栈顶指针       */
    int MaxSize;        /* 堆栈最大容量   */
};
typedef PtrToSNode Stack;

Stack CreateStack( int MaxSize )
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S->Top = 0;
    S->MaxSize = MaxSize;
    return S;
}

bool Push( Stack S, ElementType X );
ElementType Pop( Stack S );

Operation GetOp();          /* 裁判实现，细节不表 */
void PrintStack( Stack S ); /* 裁判实现，细节不表 */

int main()
{
    ElementType X;
    Stack S;
    int N, done = 0;

    scanf("%d", &N);
    S = CreateStack(N);
    while ( !done ) {
        switch( GetOp() ) {
        case push: 
            scanf("%d", &X);
            Push(S, X);
            break;
        case pop:
            X = Pop(S);
            if ( X!=ERROR ) printf("%d is out\n", X);
            break;
        case end:
            PrintStack(S);
            done = 1;
            break;
        }
    }
    return 0;
}

/* 你的代码将被嵌在这里 */
bool Push(Stack S, ElementType X)
{
if (S->Top==S->MaxSize)
{
printf("Stack Full\n");
return false;
}
else
{
S->Data[(S->Top)++] = X;
return true;
}
}

ElementType Pop(Stack S)
{
if (S->Top == 0)
{
printf("Stack Empty\n");
return ERROR;
}
else 
        return S->Data[--(S->Top)];
}

编程题

7-1 符号配对 (30分)

请编写程序检查C语言源程序中下列符号是否配对：/* 与 */、( 与 )、[ 与 ]、{ 与 }。

输入格式:

输入为一个C语言源程序。当读到某一行中只有一个句点.和一个回车的时候，标志着输入结束。程序中需要检查配对的符号不超过100个。

输出格式:

首先，如果所有符号配对正确，则在第一行中输出YES，否则输出NO。然后在第二行中指出第一个不配对的符号：如果缺少左符号，则输出?-右符号；如果缺少右符号，则输出左符号-?。

输入样例1：

void test()
{
    int i, A[10];
    for (i=0; i<10; i++) /*/
        A[i] = i;
}
.

输出样例1：

NO
/*-?

输入样例2：

void test()
{
    int i, A[10];
    for (i=0; i<10; i++) /**/
        A[i] = i;
}]
.

输出样例2：

NO
?-]

输入样例3：

void test()
{
    int i
    double A[10];
    for (i=0; i<10; i++) /**/
        A[i] = 0.1*i;
}
.

输出样例3：

YES

代码

#include<stdio.h>
#include<stdlib.h>
typedef struct
{
    int *data;
    int top;
}stack,*Stack;

void initstack(Stack S)
{
    S->data=(int*)malloc(100*sizeof(int));
    S->top=-1;
}

int panduan(char a)
{
    switch(a)
    {
        case '(':
            return 1;
        case  '[':
            return 2;
        case '{':
            return 3;
        case ')':
            return -1;
        case ']':
            return -2;
        case '}':
            return -3;
        case '/':
            return 4;
        case '*':
            return 5;
        case '.':
            return 10;
        case '\n':
            return 11;
        default:
            return 0;
    }
}

char* chu(int number)
{
    char *a; 
    switch(number)
    {
        case 1:
              a="(";
            return a;
        case -1:
            a=")";
            return a;
        case 2:
            a="[";
            return a;
        case -2:
            a="]";
            return a;
        case 3:
            a="{";
            return a;
        case -3:
            a="}";
            return a;
        case 6:
            a="/*";
            return a;
        case -6:
            a="*/";
            return a;
        default :
            return 0;
    }
}

int main()
{
    Stack S;
    int state=0;
    S=(Stack)malloc(sizeof(stack));
    initstack(S);
    char a;
    int flag=0;
    int number;
    int lastnumber;
    int last=0;
    while(1)
    {
        flag++;
        scanf("%c",&a);
        number=panduan(a);
        if(number==10)
        {
            flag=9;
            continue;
        }
        if(number==11&&flag==10)
        {
            number=lastnumber;
            break;  
        }
        if(number==11)
        continue;
        if(number==4&&last!=5)
        {
            last=4;
            continue;
        }
        else if(number==5&&last==4)
        {
            number=6;
            last=0;
        }
        else if(number==5&&last!=4)
        {
            last=5;
            continue;
        }
        else if(number==4&&last==5) 
        {
            number=-6;
            last=0;
        }
        if(number!=0&&number>0)
        {
            S->data[++S->top]=number;
        }
        else if(number!=0&&number<0)
        {
            if((S->data[S->top]+number)==0&&S->top>=0)
            S->top--;
            else if(S->top==-1)
            {
                printf("NO\n?-%s",chu(number));
                state=1;
                break;
            }
            else
            {
                state=1;
                printf("NO\n%s-?",chu(S->data[S->top]));
                break;
            }
        }
        lastnumber=number;
    }
    if(S->top==-1&&state!=1)
    printf("YES");
    else if(S->top!=-1&&state!=1)
    printf("NO\n%s-?",chu(S->data[0])); 

}

    转藏 分享 献花（0）

    来自： 流楚丶格念 > 《待分类》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多