ST数据结构作业与实验参考答案（一）

9000:矩形面积

Problem Description

声明一个名为rect的矩形类，其属性为矩形的左下角和右上角两个点的x和y坐标，该类有效矩形只存在于直角坐标系的第一象限内。若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“data error”。 Input

输入的第一行为一个数字n，表示下面有n组数据，每组数据包括2行；每组数据中的第一行表示矩形左下角点的x和y坐标，第二行表示矩形右上角点的x和y坐标。 Output

若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“data error”。 Sample Input 2 2 2 4 4 1 2 3 4

Sample Output

4 4

//9000ANSWER

#include using namespace std; class rect {

public: rect(int a,int b,int c,int d); ~rect() {} int area(); private: int x1,y1,x2,y2; };

rect::rect(int a,int b,int c,int d) { x1=a;y1=b;x2=c;y2=d;} int rect::area()

{ return (x2-x1)*(y2-y1);} int main() {

int a,b,c,d,n; cin>>n; while(n--) {

cin>>a>>b>>c>>d;

if(a<0||b<0||c<0||d<0||a>=c||b>=d) cout<<\ else

{ rect r(a,b,c,d); cout<

return 0; }

9002:数组的循环移位

Problem Description

对于一个给定的字符型数组循环左移i位，要求尽量不申请空间，实现“原地”操作。 Input

输入的第一行为一个数字n,代表接下来有n组数据，每组数据包括2行；每组数据中的第一行为一个字符串（长度不超过50），第二行为一个数字m，代表要左移的位数。 Output

循环左移后的字符型数组内容。 Sample Input 1

abcdefgh 3

Sample Output

defghabc

//9002ANSWER

#include using namespace std; #define N 20

void Reverse(char a[],int from,int to) { int i,j;char t; i=from;j=to; while(i

void Converse(char a[],int n,int i) { Reverse(a,0,i-1); Reverse(a,i,n-1); Reverse(a,0,n-1); }

int main() { char a[N];int m,n,i; cin>>m; while(m--) { cin>>a>>i; n=strlen(a);i=i%n; Converse(a,n,i);

cout<

return 0; }

9003:合并顺序表

Problem Description

假设有两个由小到大有序的有序顺序表A和B，现要求将表B并入表A中，且A表仍保持由小到大的有序性。若合并后的顺序表表长超过总容量20，则输出“not enough”。 Input

第一行为一个数字n,表示下面有n组数据，每组数据包括4行；每组数据中的第一行表示表A的表长，第二行表示表A的数据元素，第三行表示表B的表长，第四行表示表B的数据元素。 Output

若合并成功，输出两行信息，第一行表示合并后A表的表长，第二行表示合并后A表的数据元素，元素之间用一个空格分隔；若合并后的顺序表表长超过总容量20，则输出“not enough”。 Sample Input 1 4

1 3 8 17 3

6 10 15

Sample Output

7

1 3 6 8 10 15 17 //9003ANSWER

#include using namespace std; const int MaxSize=20;

//有两个由小到大有序的有序顺序表A和B

void combine(int A[],int A_len,int B[],int B_len) { if((A_len+B_len)>MaxSize) cout<<\ else { int i=0,j=0,k=0; for(i=0;i

while(B[i]>A[j])//找到B[i]在A表中的插入位置j {j++;}

for(k=A_len-1;k>=j;k--)//把j(包括j)以后的元素往后挪一个位{A[k+1]=A[k];}

A[j]=B[i];//把B[i]插入A表中的位置j

置，空出j来。

A_len++;//A表长度加1 } cout<

void main() { int A[MaxSize], B[MaxSize], A_len, B_len, n, i; cin>>n; while(n--) { cin>>A_len; for(i=0;i>A[i];} cin>>B_len; for(i=0;i>B[i];} combine(A,A_len,B,B_len); } }

9004:连续删除

Problem Description

从由小到大有序的顺序表中删除其值在[s, t]之间（含s和t）的所有元素，且不改变顺序表的有序性。如果s>=t则显示“data error”；否则输出顺序表的表长和顺序表中的元素，若处理后的顺序表为空，则不输出任何信息。 Input

输入的第一行为一个数字n，表示下面有n组数据，每组数据包括3行；每组数据中的第一行包含两个数字s和t，第二行为顺序表的表长len（0

对于每组数据，如果s>=t，则直接输出“data error”，否则输出两行信息：第一行为处理后顺序表的表长，第二行为处理后顺序表中的元素，元素之间用一个空格分隔，如果处理后的顺序表为空，则不输出任何信息。

Sample Input 1 8 18 7

1 3 5 10 17 19 25 Sample Output 5

1 3 5 19 25

//9004ANSWER

#include using namespace std; int main() { int n,s,t,len,A[21],i,s_i,t_i,j,span; cin>>n; while(n--) { cin>>s>>t>>len; for(i=0;i>A[i]; if(s>=t || len<=0 ||len>20) {cout<<\ s_i=0;t_i=len-1; while(A[s_i]t && t_i>=0) t_i--; if(s_i<=t_i) { span=t_i-s_i+1; for(j=s_i;j9005:最长相等子序列长度

Problem Description

给定一个有n个元素的整数数组b，b中连续的相等元素构成的子序列称为平台。设计一个算法求b中最长平台的长度。 Input

第一行为一个数字m，表示下面有m组数据，每组数据包括2行；每组数据中的第一行表示数组的长度n（不会超过20，但可为空表），第二行表示数组的所有元素。 Output

输出最长平台的长度。 Sample Input 2 8

11 3 8 8 8 8 8 7 10

11 3 3 25 8 8 8 8 8 7

}

9012:找唯一数

Problem Description

在一个表长为n的顺序表中，除一个元素之外，其余的元素都出现了两次。请找出这个仅出现一次的元素。 Input

有多组数据，每组第一行表示表长n（1<=n<=11111）；第二行表示顺序表的各元素。 Output

输出这个唯一数。 Sample Input 5

2 2 1 3 1 7

2 1 1 3 -1 2 3 Sample Output

3 -1

//9012ANSWER

#include using namespace std; int main() { int n,i,j,A[11112],B[11112]; while(cin>>n) { if(n>=1 && n<=11111) { for(i=0;i>A[i]; for(i=0;i}

9014:删最小值

Problem Description

设有一单链表，现要求删除其最小值（假设最小值唯一）。若删除成功，则输出被删的最小值；若删除失败，则输出“not exist”。

Input

有多组数据，每组第一行为单链表的元素个数n（0<=n<100）；第二行为单链表的各个元素。 Output

若删除成功，则输出被删的最小值；若删除失败，则输出“not exist”。 Sample Input 8

4 2 6 -3 1 9 14 5 5

2 4 1 6 7 Sample Output -3 1

//9014ANSWER

#include using namespace std;

struct Node{int data;Node *next;}; int main() { int i,n,data[100],min; Node *first,*p,*q,*s,*tail; while(cin>>n) { if(n==0){cout<<\ for(i=0;i>data[i]; first=new Node; first->next=NULL;tail=first; for(i=0;idata=data[i];tail->next=s;tail=s;} tail->next=NULL; p=first;min=first->next->data; while(p->next) { q=p;p=p->next; if(p->datadata; } p=first->next;q=first; while(p) {if(p->data==min)break; else{q=p;p=p->next;}} if(p && q){q->next=p->next;delete p;cout<

9016:查找倒数第k个结点

Problem Description

有一单链L，请输出该单链表中倒数第k个结点的值。若该结点不存在，则输出“not find”。 Input

有多组数据，每组第一行为单链表元素个数n和k值（00）；第二行为单链表的各元素。 Output

输出该单链表中倒数第k个结点的值。若该结点不存在，则输出“not find”。 Sample Input 5 1

1 2 3 4 5 5 5

1 2 3 4 5 Sample Output 5 1

//9016ANSWER

#include using namespace std;

struct Node{int date; Node *next;}; int main() { int n,k,i,c,data[100];Node *first,*r,*p,*s; while(cin>>n>>k) { for(i=0;i>data[i]; first=new Node; r=first; for(i=0;idate=data[i]; r->next=s;r=s; } r->next=NULL; }

9017:统计选票

Problem Description

设有m个候选人n张选票，每张选票选且只选一人，候选人编号依次为1，2，3，...，m。现将这n张选票存于一单链表中，要求统计并输出每个候选人的得票结果。

//倒数第k个就是正数第n-k+1个。 if(k<=n && k>=1) { p=first->next;c=1; while(p && c<(n-k+1)){p=p->next;c++;} if(p && c==(n-k+1)){cout<date<

return 0;

Input

有多组数据，每组第一行为候选人总数m和选票总数n（m>0，0

输出每个候选人的得票结果，数字之间用一个空格隔开。 Sample Input 3 6

1 3 1 2 2 1 5 8

3 3 4 3 3 2 1 1 Sample Output 3 2 1

2 1 4 1 0

//9017ANSWER

#include using namespace std; int main() { int votes[100],n,i,m,c; while(cin>>m>>n) { for(i=1;i<=m;i++) votes[i]=0; for(i=0;i>c; votes[c]++; } for(i=1;i

9038:循环队列的操作

Problem Description

现有一长度为n的整数序列和一最大容量为m的循环队列（用长为m+1的一维数组实现），要求将该序列中的偶数存入循环队列中；当循环队列满时，将循环队列中的所有元素全部出队，并按存入的先后顺序在同一行内依次输出，即每行输出m个元素，每个元素后输出一个空格。 Input

有多组数据，每组第一行为整数序列的个数n和循环队列的最大容量m（m<=n<=100，0

有多行数据，先输出对应行号，每行输出m个元素，均为偶数，每个元素后输出一个空格。 Sample Input 10 4

9 10 2 7 16 8 12 4 3 1

10 3

9 10 2 7 16 8 12 1 3 4 Sample Output

1:10 2 16 8 1:10 2 16 2:8 12 4

//9038ANSWER

#include using namespace std; int main() { int i,j,c,l,n,m,A[101],Queue[101],front,rear; while(cin>>n>>m) { for(i=0;i>A[i]; front=rear=0;c=0;l=0; for(i=0;i

9039:递归法求最大值

Problem Description

设整数序列a1,a2,...,an，给出求解最大值的递归程序。 Input

有多组数据，每组第一行为序列长度n（0

输出该整数序列中的最大值。 Sample Input

5

-2 4 10 2 3 5

8 1 -1 6 5 Sample Output

10 8

//9039ANSWER

#include using namespace std; int max(int A[],int n) { if(n==1) return A[0]; else { if(A[n-1]>=max(A,n-1)) return A[n-1]; else return max(A,n-1);} }

int main() { int i,n,A[101]; while(cin>>n) { for(i=0;i>A[i]; cout<

9040:火车车厢重排

Problem Description

一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同。这样，在每个车站只需卸掉最后一节车厢。因此，对于给定的任意次序车厢，必须进行重新排列，使其符合要求。车厢重排工作可通过转轨站完成，在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出的方式工作，现要求设计算法解决火车车厢重排问题。 Input

有多组数据，每组第一行为车厢节数n和缓冲轨数目k（2<=k<=5，k<=n<=10），第二行为初始给定的车厢编号次序序列。 Output

若给定的车厢编号次序序列可重排，则输出1；否则输出0。 Sample Input 9 3

3 6 9 2 4 7 1 8 5 9 3

3 6 9 2 4 7 5 8 1 Sample Output

1 0

//9040ANSWER

#include #include

using namespace std; int main(){ int n,k,carNum[11],i,j,rearrange; while(cin>>n>>k) { for(i=0;i>carNum[i]; queue Q[5];rearrange=1; for(i=0;iQ[j].back()) {Q[j].push(carNum[i]);break;} } if(j==k) {rearrange=0;break;} } cout<

9041:判括号匹配

Problem Description

任意输入一个由若干个圆括号、方括号和花括号组成的字符串，设计一个算法判断该串中的括号是否配对。

Input

有多组数据，每组为一个包含3类括号的字符串，串长不超过100。

Output

若该串中的括号匹配输出1，否则输出0。

Sample Input

([{}]) ([{}}) ([{)]}

Sample Output

1 0 0

//9041ANSWER

#include using namespace std;

int main() { int i,len,flag; char str[100],stack[100],top=-1; while(cin>>str) { len=strlen(str);flag=0;top=-1; for(i=0;i

9042:判操作序列有效性

Problem Description

假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则成为非法序列。请编写一个对该操作序列的有效性进行判断，若有效输出1，无效输出0。

Input

有多组数据，每组为由I和O组成的序列，序列长度不超过50。

Output

操作序列有效输出1，无效输出0。

Sample Input

IOIIOIOO IOOIOIIO

Sample Output

1 0

//9042ANSWER

#include using namespace std; int main() { int n,i,flag; char str[51],stack[51],top=-1; while(cin>>str)

{ n=strlen(str);top=-1;flag=0; for(i=0;i-1) top--; else{cout<<\ } else{cout<<\ } if(top==-1 && i==n && flag==0){cout<<\ else{if(flag==0) cout<<\} return 0;

}

*******************************************************************************************

9045:判栈输出序列的有效性

Problem Description

设一个栈的输入序列为1,2,3,...,n-1,n。请编写一个算法，判断一个序列p1,p2,p3,...,pn是否是一个有效的栈输出序列。若有效输出1，无效输出0。

Input

有多组数据，每组第一行为序列长度n（n<=50），第二行为一个由1~n值组成的长度为n且值无重复的序列。

Output

栈输出序列有效输出1，无效输出0。

Sample Input

3

1 2 3 3

3 1 2

Sample Output

1 0

//9045ANSWER

#include using namespace std; int main() {

int n,i,j,in,out;//in输入序列指针，out输出序列指针 int output[51],stack[51],top=-1; while(cin>>n) { for(i=0;i>output[i];

}

top=-1;in=0; for(i=0;iin){ for(j=in+1;j<=out;j++) stack[++top]=j; in=out; } if(stack[top]==output[i]) top--; else{cout<<\ } if(i==n && top==-1 ) cout<<\ }

return 0;

9097:杀猪！！

Problem Description

一户人家养了一群猪(n头,编号1,2,3....n)，每头猪都有自己初始体重w(double)和体重增长率x。每天猪的

体重都会发生变化，是胖是瘦取决于体重增长率，体重增长率为负，变瘦，为正，变胖。(体重增长率：double,-0.2

输入数据有多组，每组数据第一行为猪的头数n(0

第三行为n头猪的体重增长率 Output

按先后被杀的顺序输出猪的编号。每组输出数据，输出一行，编号之间用逗号隔开 Sample Input 6

4 32 99 3 2 45

0.1 -0.15 0 -0.19 0.19 -0.04 Sample Output

3,6,2,1,5,4

//9097ANSWER

#include using namespace std; int main() {

int n,i,j,flag,maxi;double max;//max一定是double类型 while(cin>>n) { if(n<=50 && n>0) { double * pw=new double[n+1]; double * px=new double[n+1];

}

for(i=1;i<=n;i++)cin>>pw[i]; for(i=1;i<=n;i++)cin>>px[i]; flag=1; for(j=1;j<=n;j++) { max=0;maxi=0;

for(i=1;i<=n;i++){if(pw[i]>max){max=pw[i];maxi=i;}} if(flag==1){cout<

return 0;