单选题
函数题
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])); }
