1-1对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。
(2分)作者DS课程组单位浙江大学1-1答案正确(2 分)
1-2对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。
(2分)作者徐镜春单位浙江大学1-2答案正确(2 分)
1-3若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。
(2分)作者DS课程组单位浙江大学1-3答案正确(2 分)
1-4循环队列也存在着空间溢出问题。
(2分)作者李廷元单位民用航空飞行学院1-4答案正确(2 分)
1-5假设模式串是abababaab，则KMP模式匹配算法中的next[j] = 0 1 1 2 3 4 5 6 2。
(2分)作者徐镜春单位浙江大学1-5答案正确(2 分)
1-6循环链表不是线性表。
(2分)作者李廷元单位民用航空飞行学院1-6答案正确(2 分)
1-7链式存储的优点是插入、删除元素时不会引起后续元素的移动，缺点是只能顺序访问各元素。
(2分)作者DS课程组单位临沂大学1-7答案正确(2 分)
1-8栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。
(2分)作者DS课程组单位临沂大学1-8答案正确(2 分)
1-9若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。
(2分)作者李廷元单位民用航空飞行学院1-9答案正确(2 分)
1-10若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。
(2分)作者徐镜春单位浙江大学1-10答案正确(2 分)
2-1设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为
(2分)作者郝秀兰单位湖州师范学院2-1答案正确(2 分)
2-2在N个结点的顺序表中，算法的时间复杂度为O(1)的操作是：
(2分)作者DS课程组单位浙江大学2-2答案正确(2 分)
2-3下列关于栈的叙述中，错误的是：
采用非递归方式重写递归程序时必须使用栈
函数调用时，系统要用栈保存必要的信息
只要确定了入栈次序，即可确定出栈次序
栈是一种受限的线性表，允许在其两端进行操作
(2分)作者考研试卷单位浙江大学2-3答案正确(2 分)
2-4循环队列的队空条件为（ ）
(2分)作者lyuinfo单位临沂大学2-4答案正确(2 分)
2-5循环队列的队满条件为（ ）
(2分)作者lyuinfo单位临沂大学2-5答案正确(2 分)
5-1下列代码的功能是返回带头结点的单链表L的逆转链表。
List Reverse( List L )
{
Position Old_head, New_head, Temp;
New_head = NULL;
Old_head = L->Next;
while ( Old_head ) {
Temp = Old_head->Next; 3分;
New_head = Old_head;
Old_head = Temp;
} 3分;
return L;
}
作者DS课程组单位浙江大学时间限制400 ms内存限制64 MB5-1答案正确(6 分)
5-2下面是利用尾递归函数求n的阶乘。请填空。
#include<stdio.h>
int factTR(int n, int a)
{
if (n == 0)
return 3分;
return factTR(n - 1, 3分);/*尾递归*/
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", factTR(n, 1));
return 0;
}
作者李廷元单位民用航空飞行学院时间限制400 ms内存限制64 MB5-2答案正确(6 分)
5-3下列代码的功能是将二叉树T中的结点按照层序遍历的顺序输出。
typedef struct TreeNode *Tree;
struct TreeNode
{
int Key;
Tree Left;
Tree Right;
};
void Level_order ( Tree T )
{
Queue Q;
if ( !T ) return;
Q = CreateQueue( MaxElements );
Enqueue( T, Q );
while ( !IsEmpty( Q ) ){
T = Front_Dequeue ( Q ); /* return the front element and delete it from Q */
printf("%d ", T->Key);
if ( T->Left )
3分;
if ( 3分 )
3分;
}
}
作者陈越单位浙江大学时间限制400 ms内存限制64 MB5-3答案正确(9 分)
本题要求给定二叉树的高度。
函数接口定义：
int GetHeight( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
要求函数返回给定二叉树BT的高度值。
裁判测试程序样例：
#include <stdio.h>#include <stdlib.h>typedef char ElementType;typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */int GetHeight( BinTree BT );int main(){
BinTree BT = CreatBinTree(); printf("%d\n", GetHeight(BT)); return 0;
}/* 你的代码将被嵌在这里 */
输出样例（对于图中给出的树）：
4
作者陈越单位浙江大学代码长度限制16 KB时间限制400 ms内存限制64 MBint GetHeight( BinTree BT)
{
int m,n;
if(BT==NULL){
return 0;
}
else
{
m=GetHeight(BT->Left);
n=GetHeight(BT->Right);
if (m>n){
return(m+1);
}
else{
return(n+1);
}
}
}
C语言标准函数库中包括 strlen 函数，用于计算字符串的长度。作为练习，我们自己编写一个功能与之相同的函数。
函数原型
int StrLen(const char *str);
说明：str为串的起始地址，函数值为字符串的长度(不含结束标记'\0')。
裁判程序
#include <stdio.h>#include <string.h>int StrLen(const char *str);int main(){ char a[1024]; int n;
gets(a);
n = StrLen(a); printf("%d\n", n); return 0;
}/* 你提交的代码将被嵌在这里 */
输入样例
abcd
输出样例
4
作者李祥单位湖北经济学院代码长度限制16 KB时间限制100 ms内存限制64 MBint StrLen(const char *str){
int i=0;
while(str[i]!='\0'){
i++;
}
return i;
}
本题要求在一个数组中实现两个堆栈。
函数接口定义：
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-1
对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。
(2分)
作者
DS课程组
单位
浙江大学
1-1
答案正确
(2 分)
1-2
对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。
(2分)
作者
徐镜春
单位
浙江大学
1-2
答案正确
(2 分)
1-3
若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。
(2分)
作者
DS课程组
单位
浙江大学
1-3
答案正确
(2 分)
1-4
循环队列也存在着空间溢出问题。
(2分)
作者
李廷元
单位
民用航空飞行学院
1-4
答案正确
(2 分)
1-5
假设模式串是abababaab，则KMP模式匹配算法中的next[j] = 0 1 1 2 3 4 5 6 2。
(2分)
作者
徐镜春
单位
浙江大学
1-5
答案正确
(2 分)
1-6
循环链表不是线性表。
(2分)
作者
李廷元
单位
民用航空飞行学院
1-6
答案正确
(2 分)
1-7
链式存储的优点是插入、删除元素时不会引起后续元素的移动，缺点是只能顺序访问各元素。
(2分)
作者
DS课程组
单位
临沂大学
1-7
答案正确
(2 分)
1-8
栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。
(2分)
作者
DS课程组
单位
临沂大学
1-8
答案正确
(2 分)
1-9
若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。
(2分)
作者
李廷元
单位
民用航空飞行学院
1-9
答案正确
(2 分)
1-10
若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。
(2分)
作者
徐镜春
单位
浙江大学
1-10
答案正确
(2 分)
2-1
设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为
(2分)
作者
郝秀兰
单位
湖州师范学院
2-1
答案正确
(2 分)
2-2
在N个结点的顺序表中，算法的时间复杂度为O(1)的操作是：
(2分)
作者
DS课程组
单位
浙江大学
2-2
答案正确
(2 分)
2-3
下列关于栈的叙述中，错误的是：
采用非递归方式重写递归程序时必须使用栈
函数调用时，系统要用栈保存必要的信息
只要确定了入栈次序，即可确定出栈次序
栈是一种受限的线性表，允许在其两端进行操作
(2分)
作者
考研试卷
单位
浙江大学
2-3
答案正确
(2 分)
2-4
循环队列的队空条件为（ ）
(2分)
作者
lyuinfo
单位
临沂大学
2-4
答案正确
(2 分)
2-5
循环队列的队满条件为（ ）
(2分)
作者
lyuinfo
单位
临沂大学
2-5
答案正确
(2 分)
5-1
下列代码的功能是返回带头结点的单链表L的逆转链表。
List Reverse( List L )
{
Position Old_head, New_head, Temp;
New_head = NULL;
Old_head = L->Next;
while ( Old_head ) {
Temp = Old_head->Next; 3分;
New_head = Old_head;
Old_head = Temp;
} 3分;
return L;
}
作者
DS课程组
单位
浙江大学
时间限制
400 ms
内存限制
64 MB
5-1
答案正确
(6 分)
5-2
下面是利用尾递归函数求n的阶乘。请填空。
#include<stdio.h>
int factTR(int n, int a)
{
if (n == 0)
return 3分;
return factTR(n - 1, 3分);/*尾递归*/
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", factTR(n, 1));
return 0;
}
作者
李廷元
单位
民用航空飞行学院
时间限制
400 ms
内存限制
64 MB
5-2
答案正确
(6 分)
5-3
下列代码的功能是将二叉树T中的结点按照层序遍历的顺序输出。
typedef struct TreeNode *Tree;
struct TreeNode
{
int Key;
Tree Left;
Tree Right;
};
void Level_order ( Tree T )
{
Queue Q;
if ( !T ) return;
Q = CreateQueue( MaxElements );
Enqueue( T, Q );
while ( !IsEmpty( Q ) ){
T = Front_Dequeue ( Q ); /* return the front element and delete it from Q */
printf("%d ", T->Key);
if ( T->Left )
3分;
if ( 3分 )
3分;
}
}
作者
陈越
单位
浙江大学
时间限制
400 ms
内存限制
64 MB
5-3
答案正确
(9 分)
本题要求给定二叉树的高度。
函数接口定义：
int GetHeight( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
要求函数返回给定二叉树BT的高度值。
裁判测试程序样例：
#include <stdio.h>#include <stdlib.h>typedef char ElementType;typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */int GetHeight( BinTree BT );int main(){
BinTree BT = CreatBinTree(); printf("%d\n", GetHeight(BT)); return 0;
}/* 你的代码将被嵌在这里 */
输出样例（对于图中给出的树）：
4
作者
陈越
单位
浙江大学
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
int GetHeight( BinTree BT)
{
int m,n;
if(BT==NULL){
return 0;
}
else
{
m=GetHeight(BT->Left);
n=GetHeight(BT->Right);
if (m>n){
return(m+1);
}
else{
return(n+1);
}
}
}C语言标准函数库中包括 strlen 函数，用于计算字符串的长度。作为练习，我们自己编写一个功能与之相同的函数。
函数原型
int StrLen(const char *str);
说明：str为串的起始地址，函数值为字符串的长度(不含结束标记'\0')。
裁判程序
#include <stdio.h>#include <string.h>int StrLen(const char *str);int main(){ char a[1024]; int n;
gets(a);
n = StrLen(a); printf("%d\n", n); return 0;
}/* 你提交的代码将被嵌在这里 */
输入样例
abcd
输出样例
4
作者
李祥
单位
湖北经济学院
代码长度限制
16 KB
时间限制
100 ms
内存限制
64 MB
int StrLen(const char *str){
int i=0;
while(str[i]!='\0'){
i++;
}
return i;
}本题要求在一个数组中实现两个堆栈。
函数接口定义：
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 MB
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)++];
}
}