1-1若一个栈的输入序列为1，2，3，…，，输出序列的第一个元素是，则第个输出元素是。
(1分)作者DS课程组单位浙江大学1-1答案正确(1 分)
1-2栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。
(1分)作者李廷元单位民用航空飞行学院1-2答案正确(1 分)
1-3栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。
(1分)作者DS课程组单位临沂大学1-3答案正确(1 分)
1-4在对不带头结点的链队列作出队操作时，不会改变头指针的值。
(1分)作者林华单位广东外语外贸大学1-4答案正确(1 分)
1-5不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。
(1分)作者林华单位广东外语外贸大学1-5答案正确(1 分)
1-6循环队列也存在着空间溢出问题。
(1分)作者李廷元单位民用航空飞行学院1-6答案正确(1 分)
1-7n个元素进队的顺序和出队的顺序总是一致的。
(1分)作者李廷元单位民用航空飞行学院1-7答案正确(1 分)
1-8若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。
(1分)作者李廷元单位民用航空飞行学院1-8答案正确(1 分)
1-9通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。
(1分)作者DS课程组单位浙江大学1-9答案正确(1 分)
1-10若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。
(1分)作者徐镜春单位浙江大学1-10答案正确(1 分)2-1将5个字母ooops按此顺序入栈，则有多少种不同的出栈顺序可以仍然得到ooops？
(2分)作者DS课程组单位浙江大学2-1答案正确(2 分)
2-2给定一个堆栈的入栈序列为{ 1, 2, , }，出栈序列为{ , , , }。如果，则存在多少种不同的出栈序列？
(2分)作者徐镜春单位浙江大学2-2答案正确(2 分)
2-3下列关于栈的叙述中，错误的是：
采用非递归方式重写递归程序时必须使用栈
函数调用时，系统要用栈保存必要的信息
只要确定了入栈次序，即可确定出栈次序
栈是一种受限的线性表，允许在其两端进行操作
(2分)作者考研试卷单位浙江大学2-3答案正确(2 分)
2-4两栈共享数组存储空间，前一个栈的栈顶指针为p后一个栈的栈顶指针为q，能进行正常入栈操作的条件是（ ）。
(2分)作者严冰单位浙大城市学院2-4答案正确(2 分)
2-6关于栈和队列的下列说法正确的是（）
(2分)作者DS课程组单位临沂大学2-6答案正确(2 分)
2-7在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ ）。
(2分)作者杨斌单位枣庄学院2-7答案正确(2 分)
2-9循环队列的队满条件为（ ）
(2分)作者lyuinfo单位临沂大学2-9答案正确(2 分)
2-10循环队列的队空条件为（ ）
(2分)作者lyuinfo单位临沂大学2-10答案正确(2 分)
2-11设循环队列中数组的下标范围是0—n-1，其头尾指针分别为f和r，则其元素的个数为（ ）
(2分)作者lyuinfo单位临沂大学2-11答案正确(2 分)5-1下面是利用尾递归函数求n的阶乘。请填空。
#include<stdio.h>
int factTR(int n, int a)
{
if (n == 0)
return 5分;
return factTR(n - 1, 5分);/*尾递归*/
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", factTR(n, 1));
return 0;
}作者李廷元单位民用航空飞行学院时间限制400 ms内存限制64 MB5-1答案正确(10 分)
5-2本题要求实现一个普通顺序队列。
当输入1 2 3 -1时，输出为1 2 3 。
当输入为1 2 3 4 5 6 7 8 9 10 11 -1时，输出为
queue is full!
1 2 3 4 5 6 7 8 9 10
请填空。
#include <stdio.h>
#include <stdbool.h>
#define MaxSize 10
int q[MaxSize];
int front;
int rear;
//空队列返回true,否则返回false
bool empty() {
return 3分;
}
//队列满返回true,否则返回false
bool full() {
return rear + 1 == MaxSize;
}
//入队列
void push(int x) {
++rear;
q[rear] = x;
}
//取队首元素
int getFront() {
return 3分;
}
//出队列
void pop() {
++front;
}
int main(int argc, char const *argv[])
{
int i; 4分; //初始化队列
while (scanf("%d", &i) != EOF) {
if (i == -1)break;
if (!full()) //队列未满时
push(i); //入队列
else
printf("queue is full!\n");
}
while (!empty()) { //输出队列元素
printf("%d ", getFront());
pop();
}
printf("\n");
return 0;
}作者李廷元单位民用航空飞行学院时间限制400 ms内存限制64 MB5-2答案正确(10 分)本题要求在一个数组中实现两个堆栈。
函数接口定义：
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。
裁判测试程序样例：
#include <stdio.h>#include <stdlib.h>#define ERROR 1e8typedef 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;
}/* 你的代码将被嵌在这里 */输入样例：
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
作者陈越单位浙江大学代码长度限制16 KB时间限制400 ms内存限制64 MBStack CreateStack( int MaxSize )
{
Stack S =(Stack)malloc(sizeof(struct SNode));
S->Data=(ElementType*)malloc(sizeof(ElementType)*MaxSize);
S->Top1=-1;
S->Top2=MaxSize;
S->MaxSize=MaxSize;
return S;
}
bool Push( Stack S, ElementType X, int Tag )
{
if(S->Top2-S->Top1==1){
printf("Stack Full\n");
return false;
}
if(Tag==1){
S->Data[++(S->Top1)]=X;
return true;
}
else{
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;
}
return S->Data[(S->Top1)--];
}
else{
if(S->Top2==S->MaxSize){
printf("Stack %d Empty\n",Tag);
return ERROR;
}
return S->Data[(S->Top2)++];
}
}
若一个栈的输入序列为1，2，3，…，，输出序列的第一个元素是，则第个输出元素是。
栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。
栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。
在对不带头结点的链队列作出队操作时，不会改变头指针的值。
不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。
循环队列也存在着空间溢出问题。
n个元素进队的顺序和出队的顺序总是一致的。
若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。
通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。
若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。
将5个字母ooops按此顺序入栈，则有多少种不同的出栈顺序可以仍然得到ooops？
给定一个堆栈的入栈序列为{ 1, 2, , }，出栈序列为{ , , , }。如果，则存在多少种不同的出栈序列？
下列关于栈的叙述中，错误的是：
采用非递归方式重写递归程序时必须使用栈
函数调用时，系统要用栈保存必要的信息
只要确定了入栈次序，即可确定出栈次序
栈是一种受限的线性表，允许在其两端进行操作
两栈共享数组存储空间，前一个栈的栈顶指针为p后一个栈的栈顶指针为q，能进行正常入栈操作的条件是（ ）。
关于栈和队列的下列说法正确的是（）
在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ ）。
循环队列的队满条件为（ ）
循环队列的队空条件为（ ）
设循环队列中数组的下标范围是0—n-1，其头尾指针分别为f和r，则其元素的个数为（ ）
下面是利用尾递归函数求n的阶乘。请填空。
#include<stdio.h>
int factTR(int n, int a)
{
if (n == 0)
return 5分;
return factTR(n - 1, 5分);/*尾递归*/
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", factTR(n, 1));
return 0;
}本题要求实现一个普通顺序队列。
当输入1 2 3 -1时，输出为1 2 3 。
当输入为1 2 3 4 5 6 7 8 9 10 11 -1时，输出为
queue is full!
1 2 3 4 5 6 7 8 9 10
请填空。
#include <stdio.h>
#include <stdbool.h>
#define MaxSize 10
int q[MaxSize];
int front;
int rear;
//空队列返回true,否则返回false
bool empty() {
return 3分;
}
//队列满返回true,否则返回false
bool full() {
return rear + 1 == MaxSize;
}
//入队列
void push(int x) {
++rear;
q[rear] = x;
}
//取队首元素
int getFront() {
return 3分;
}
//出队列
void pop() {
++front;
}
int main(int argc, char const *argv[])
{
int i; 4分; //初始化队列
while (scanf("%d", &i) != EOF) {
if (i == -1)break;
if (!full()) //队列未满时
push(i); //入队列
else
printf("queue is full!\n");
}
while (!empty()) { //输出队列元素
printf("%d ", getFront());
pop();
}
printf("\n");
return 0;
}本题要求在一个数组中实现两个堆栈。
函数接口定义：
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。
裁判测试程序样例：
#include <stdio.h>#include <stdlib.h>#define ERROR 1e8typedef 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;
}/* 你的代码将被嵌在这里 */输入样例：
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
Stack CreateStack( int MaxSize )
{
Stack S =(Stack)malloc(sizeof(struct SNode));
S->Data=(ElementType*)malloc(sizeof(ElementType)*MaxSize);
S->Top1=-1;
S->Top2=MaxSize;
S->MaxSize=MaxSize;
return S;
}
bool Push( Stack S, ElementType X, int Tag )
{
if(S->Top2-S->Top1==1){
printf("Stack Full\n");
return false;
}
if(Tag==1){
S->Data[++(S->Top1)]=X;
return true;
}
else{
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;
}
return S->Data[(S->Top1)--];
}
else{
if(S->Top2==S->MaxSize){
printf("Stack %d Empty\n",Tag);
return ERROR;
}
return S->Data[(S->Top2)++];
}
}