ST数据结构作业与实验参考答案(一)

1、9000:矩形面积Problem Descripti on声明一个名为rect的矩形类，其属性为矩形的左下角和右上角两个点的x和y坐标，该类有效矩形只存在于直角坐标系的第一象限内。若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“ dataerror 。一 In put输入的第一行为一个数字 n,表示下面有n组数据，每组数据包括 2行；每组数据中的第一行表示矩形左 下角点的x和y坐标，第二行表示矩形右上角点的x和y坐标。data error。Output若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出Sample Input 22 24 41 23 4一 Sam

2、ple Output44/9000ANSWER#in cludeusing n amespace std;class rectpublic:rect(i nt a,i nt b,i nt c,i nt d);rect() int area();private:int x1,y1,x2,y2;rect:rect(i nt a,i nt b,i nt c,i nt d) x1=a;y仁b;x2=c;y2=d;int rect:area() return (x2-x1)*(y2-y1);int mai n()int a,b,c,d, n;cinn;while( n-)cin abcd;if(a0|b

3、0|c0|d=c|b=d) coutdata errore ndl;else rect r(a,b,c,d);coutr.area()e ndl;return 0;9002:数组的循环移位一 Problem Descripti on对于一个给定的字符型数组循环左移i位，要求尽量不申请空间，实现原地”操作。一 In put输入的第一行为一个数字n,代表接下来有n组数据，每组数据包括 2行；每组数据中的第一行为一个字符串(长度不超过50),第二行为一个数字 m,代表要左移的位数。一 Output循环左移后的字符型数组内容。一 Sample In put1abcdefgh3一 Sample Outp

4、ut defghabc/9002ANSWER#in cludeusing n amespace std;#defi ne N 20void Reverse(char a,i nt from,i nt to)int i,j;char t;i=from;j=to; while(i ai;n=strle n(a);i=i% n;Con verse(a ,n ,i);coutae ndl; return 0;9003:合并顺序表一 Problem Descripti on假设有两个由小到大有序的有序顺序表A和B,现要求将表B并入表A中，且A表仍保持由小到大的有序性。若合并后的顺序表表长超过总容量20，

5、则输出“not enough。”一 In put第一行为一个数字 n,表示下面有n组数据，每组数据包括4行；每组数据中的第一行表示表A的表长，第二行表示表A的数据元素，第三行表示表B的表长，第四行表示表B的数据元素。一 Output若合并成功，输出两行信息，第一行表示合并后A表的表长，第二行表示合并后A表的数据元素，元素之间用一个空格分隔；若合并后的顺序表表长超过总容量20,则输出“not enough”Sample In put141 3 8 1736 10 15Sample Output 71 3 6 8 10 15 17/9003ANSWER#in clude using n amesp

6、ace std;con st int MaxSize=20;/有两个由小到大有序的有序顺序表A和Bvoid comb in e(i nt A,i nt A_le n,i nt B,i nt B_le n)if(A_le n+B_le n) MaxSize)cout not eno ughn;elseint i=O,j=O,k=O;for(i=0;iAj)找到Bi 在A表中的插入位置 jj+;for(k=A_len-1;k=j;k-)把j(包括j)以后的元素往后挪一个位置，空出j来。Ak+1=Ak;Aj=Bi;把Bi 插入A表中的位置jA_le n+;/A表长度加1coutA_le nen dl

7、; for(i=0;i(A_le n-1);i+)coutAi; coutAi A_le n;for(i=0;iAi; cin B_le n;for(i=0;iBi; combi ne(A,A_le n,B,B_le n);9004:连续删除Problem Descripti on从由小到大有序的顺序表中删除其值在s, t之间(含s和t)的所有元素，且不改变顺序表的有序性。如果s=t则显示“ data error；否则输出顺序表的表长和顺序表中的元素，若处理后的顺序表为空，则不输出任 何信息。In put输入的第一行为一个数字n,表示下面有n组数据，每组数据包括3行；每组数据中的第一行包含两个

8、数字s和t，第二行为顺序表的表长len (0len=t，则直接输出“data error，否则输出两行信息：第一行为处理后顺序表的表长,第二行为处理后顺序表中的元素，元素之间用一个空格分隔，如果处理后的顺序表为空，则不输出任何信 息。Sample Input 18 1871 3 5 10 17 19 25Sample Output51 3 5 19 25/9004ANSWER#in clude using n amespace std; int mai n()int n, s,t,le n, A21,i,s_i,t_i,j,spa n; cinn;while( n-)cin stle n; f

9、or(i=0;i Ai;if(s=t | len20) coutdata errore ndl;c on ti nu e; s_i=0;t_i=le n-1;while(As_is & s_it & t_i=0) t_i-; if(s_i=t_i)spa n=t_i-s_i+1; for(j=s_i;jle n;j+) Aj=Aj+spa n; len-=spa n;if(le n!=0)coutle nen dl;for(i=0;ilen-1;i+) coutAi;coutAie ndl;return 0;9005:最长相等子序列长度Problem Descripti on中最给定一个有n个

10、元素的整数数组 b, b中连续的相等元素构成的子序列称为平台。设计一个算法求 长平台的长度。In put第一行为一个数字 m，表示下面有m组数据，每组数据包括 2行；每组数据中的第一行表示数组的长度 （不会超过20，但可为空表），第二行表示数组的所有元素。Output输出最长平台的长度。Sample In put2811 3 8 8 8 8 8 710 11 3 3 25 8 8 8 8 8 7Sample Output 55/9005ANSWER#in elude using n amespace std;int mai n()int m,n ,i,b21,c,max;cinm;while(

11、m-)cinn;if(n20) cout0n;continue;for(i=0;i bi;i=0;c=max=1;dowhile(bi=bi+1) &(imax) max=c;c=1;while(i n);coutmaxe ndl;return 0;9006:单链表的建立和遍历Problem Descripti on输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。In putN个整数。输入数据有多组，每组数据占两行；每组第一行为一个数字N (N=50 );第二行有Output输出这组整数，数字之间用一个空格分隔。Sample In put512 32 45 78

12、 54Sample Output12 32 45 78 54/9006ANSWER#in clude using n amespace std;struct Nodei nt data;Node * next; int mai n() int N,i,A51;Node *head=new Node,*p,*tail; while(ci nN)if(N0)for(i=0;i Ai; tail=head;for(i=0;idata=Ai; tail-n ext=p; tail=p;tail-n ext=NULL;p=head-n ext;for(i=0;iN-1;i+)coutdatan ext;

13、coutdata using namespace std; struct Node int data; Node * next; int main()int i,n,x,A51; Node *p,*first,*q,*r,*s;while(cinn)if(n=0)cinx; coutvvxvvendl;continue;first=new Node;first-next=NULL;s=new Node;s-data=x;s-next=first-next; first-next=s; else if(n=1 & nv=50)for(i=O;ivn;i+)cinAi;cinx;/尾插法 crea

14、LinkListfirst=new Node; for(i=0;ivn;i+) s=new Node;first-next=NULL;s-data=Ai;s-next=r-next;r=first;r-next=s; r=s;/按值查找p=first-next;q=first; while(p)if(p-data=x) q-next=p-next;else if(p-datavx)q=p; else if(p-datax) s=new Node;delete p; p=p-next; s-data=x;break;s-next=p;q-next=s;break; if(p=NULL)s=new

15、 Node;s-data=x;s-next=p;q-next=s;/if/遍历 LinkList if(first-next)p=first-next; coutvvp-data;p=p-next;while(p)coutvv vvp-data;p=p-next; coutvvendl;/释放 LinkListp=first;while(p) q=p-next;delete p;p=q; /whilereturn 0;9008:约瑟夫环问题(循环链表)Problem Descripti on对任意n个人，密码为m ,实现约瑟夫环问题。约瑟夫环是一个数学的应用问题：已知n个人(以编号1 ,2，3

16、n分别表示)围坐在一张圆桌周围。从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到 m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。In put每行为一组数据，包括2个正整数n和m (n, m0 )。Output依次写出出圈的顺序，数字之间用一个空格分隔。Sample In put6 37 3Sample Output3 6 4 2 5 13 6 2 7 5 1 4/9008ANSWER#in cludeusing n amespace std;struct Nodeint data;Node * next;int mai n()int i,j, n,m

17、;Node *first,*q,*p,*s,*r;while(ci nn m)/构建无头结点的循环单链表first =new Node;first-data=1;r=first;for(i=2;idata=i;r- n ext=s;r=s;r-n ext=first;/Prin t cirLi nklist/p=first- n ext;if(first)coutdata;while(p!=first)cout data;p=p-n ext;p=first;j=1;q=r;/q是 p 的前趋结点while(p!=q)while(jn ext;j+;q-n ext=p-n ext;coutdat

18、an ext;j=1; coutdatae ndl;return 0;9010:拆分顺序表一 Problem Descripti on0的元有一顺序表 A，请将其拆分成两个顺序表B和C,使A中大于0的元素存放在 B中，小于或等于素存放在C中。一 In put有多组数据，每组第一行表示A表长n (0n=20)；第二行表示顺序表 A的各元素。一 Output将顺序表B和C的元素分两行输出，每行中相邻两元素之间用一个空格分隔，空表则不输出任何信息。Sample Input 911 3 -3 3 -4 0 -2 6 32Sample Output 11 3 3 6 32-3 -4 0 -2 /9010

19、ANSWER #in clude using n amespace std; int mai n()int n,i,j,k,A21,B21,C21; while(ci nn) if(n0 & n=20)for(i=0;i Ai;j=k=0;for(i=0;i0) Bj+=Ai;else Ck+=Ai;if(j0)for(i=0;ij-1;i+) coutBi;coutBi0)for(i=0;ik-1;i+) coutCi; coutCie ndl; return 0;9012:找唯一数Problem Descripti on在一个表长为n的顺序表中，除一个元素之外，其余的元素都出现了两次。请找

20、出这个仅出现一次的元素。一 In put有多组数据，每组第一行表示表长n (1=n=11111);第二行表示顺序表的各元素。一 Output输出这个唯一数。一 Sample In put2 2 1 3 172 1 1 3 -1 2 3Sample Output 3-1/9012ANSWER#in clude using n amespace std;int mai n()int n,i,j,A11112,B11112;while(ci nn)if(n =1 & n=11111)for(i=0;i Ai; for(i=0;in;i+) Bi=1;for(i=0;i n;i+)for(j=i+1;

21、j n;j+)if(Ai=Aj) Bi=0;Bj=0;break;for(i=0;i n;i+)if(Bi=1)coutAie ndl;return 0;9014:删最小值Problem Descripti on设有一单链表，现要求删除其最小值(假设最小值唯一)。若删除成功，则输出被删的最小值；若删除失 败，则输出not exist。”In put有多组数据，每组第一行为单链表的元素个数n ( 0=n100 );第二行为单链表的各个元素。一 Output若删除成功，则输出被删的最小值；若删除失败，则输出“not exist。一 Sample In put84 2 6 -3 1 9 14 552

22、 4 1 6 7Sample Output -3/9014ANSWER#in cludeusing n amespace std;struct Node int data;Node *n ext; int mai n()in t i,n ,data100,mi n; Node *first,*p,*q,*s,*tail;while(ci nn)if(n=0)cout not exist n;c ontinu e;for(i=0;i datai;first =new Node;first- n ext=NULL;tail=first;for(i=0;idata=datai;tail-n ext=

23、s;tail=s;tail- next=NULL;p=first;mi n=first-n ext-data;while(p- next)q=p;p=p-n ext;min=p-data;if(p-datan ext;q=first;while(p)if(p-data=min )break; elseq=p;p=p-n ext; if(p & q)q-n ext=p-n ext;delete p;cout minen dl; elsecout not exist n; return 0;9016:查找倒数第k个结点Problem Descripti on一 In put有多组数据，每组第一行为

24、单链表元素个数n和k值(00 );第二行为单链表的各元素。一 Output输出该单链表中倒数第k个结点的值。若该结点不存在，则输出 “not find。”一 Sample In put4 11 2 3 4 55 51 2 3 4 5Sample Output/9016ANSWER #in clude using n amespace std;struct Node int date;Node *n ext;int mai n()int n,k,i,c,data100;Node *first,*r,*p,*s;while(ci nn k)for(i=0;i datai;first =new No

25、de;r=first;for(i=0;idate=datai;r-n ext=s;r=s;r-n ext=NULL;II倒数第k个就是正数第n-k+1 个。if(k=1)p=first- n ext;c=1;while(p & cn ext;c+; if(p & c=(n _k+1)coutdatee ndl; else cout not fin d0 , 0n100 );第二行为n张选票的内容。一 Output输出每个候选人的得票结果，数字之间用一个空格隔开。一 Sample Input3 61 3 1 2 2 15 83 3 4 3 3 2 1 1Sample Output3 2 12 1

26、 4 1 0/9017ANSWER#in cludeusing n amespace std;int mai n()in t votes100, n,i,m,c;while(ci nmn)for(i=1;i=m;i+) votesi=0;for(i=0;i c;votesc+;for(i=1;im;i+) coutvotesi; coutvotesme ndl;return 0;9038:循环队列的操作Problem Descripti on现有一长度为n的整数序列和一最大容量为m的循环队列(用长为m+1的一维数组实现)，要求将该序列中的偶数存入循环队列中；当循环队列满时，将循环队列中的所有元

27、素全部出队，并按存入的先后顺序在 同一行内依次输出，即每行输出m个元素，每个元素后输出一个空格。In put有多组数据，每组第一行为整数序列的个数n和循环队列的最大容量 m (m=*=100, 0m10)；第二行为整数序列的各个元素。Output有多行数据，先输出对应行号，每行输出m个元素，均为偶数，每个元素后输出一个空格。Sample In put10 49 10 2 7 16 8 12 4 3 110 39 10 2 7 16 8 12 1 3 4一 Sample Output 1:10 2 16 81:10 2 162:8 12 4 /9038ANSWER #in elude using

28、 n amespace std; int mai n()int i,j,c,l, n,m,A101,Queue101,fro nt,rear;while(ci nnm)for(i=0;i Ai; fron t=rear=0;c=0;l=0;for(i=0;i n; i+)if(cm & Ai%2=0)c+;rear=(rear+1)%(m+1);Queuerear=Ai;if(c=m)cout+l:;for(j=fro nt+1;j=rear;j+) coutQueuej coute ndl;c=0;fr on t=rear=0; return 0;9039:递归法求最大值一 Problem

29、Descripti on设整数序列a1,a2,.,an，给出求解最大值的递归程序。一 In put有多组数据，每组第一行为序列长度n (0*50),第二行为该整数序列的各元素。一 Output输出该整数序列中的最大值。Sample In put-2 4 10 2 358 1-1 6 5Sample Output108/9039ANSWER#in elude using n amespace std;int max(i nt A,i nt n)if(n=1) return A0;else if(An-1=max(A,n-1) return An-1;else return max(A, n-1)

30、;int mai n()int i,n ,A101;while(ci nn)for(i=0;i Ai;coutmax(A ,n)en dl;return 0;9040:火车车厢重排Problem Descripti on一列货运列车共有 n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的 编号相同。这样，在每个车站只需卸掉最后一节车厢。因此，对于给定的任意次序车厢，必须进行重新排 列，使其符合要求。车厢重排工作可通过转轨站完成，在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨

31、位于入轨和出轨之间。假定缓冲轨按先进先出的方式工作，现要求设计算法解决火车车厢重排问题。In put有多组数据，每组第一行为车厢节数n和缓冲轨数目k（ 2=k=5，k=n=10），第二行为初始给定的车厢编号次序序列。Output若给定的车厢编号次序序列可重排，则输出1;否则输出0。Sample Input9 33 6 9 2 4 7 1 8 59 33 6 9 2 4 7 5 8 1Sample Output0/9040ANSWER#in clude #in clude using n amespace std; int mai n()int n ,k,carNum11,i,j,rearra

32、nge; while(ci nn k)for(i=0;i carNumi; queue Q5;rearra nge=1;for(i=0;i n;i+)for(j=0;jQj.back()Qj.push(carNumi);break;if(j=k)rearra nge=O;break;coutrearra ngee ndl; return 0;9041:判括号匹配一 Problem Descripti on任意输入一个由若干个圆括号、方括号和花括号组成的字符串，设计一个算法判断该串中的括号是否配对。In put有多组数据，每组为一个包含3类括号的字符串，串长不超过100。Output若该串中的括

33、号匹配输出1,否则输出0。Sample In put()()()Sample Output100/9041ANSWER#in clude using n amespace std;int mai n()int i,le n, flag;char str100,stack100,top=-1;while(ci n str)len=strle n( str);flag=0;top=-1;for(i=0;ile n; i+)if(stri=( | stri= | stri=)stack+top=stri;else if(stri=) & (stacktop=() | (stri=T) & (stac

34、ktop=T) | (stri=) & (stacktop=)top-;elsecout0n;flag=1;break;if(top=-1 & i=len & flag=0)cout1n;else if(flag=0)cout0n;return 0;9042:判操作序列有效性Problem Descripti on假设以i和o分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则成为非法序列。请编写一个对该操作序列的有效性 进行判断，若有效输出1，无效输出0。In put有多组数据，每组为由I和O组成的序列，序列长度不超

35、过50。Output操作序列有效输出1，无效输出0。Sample In putIOIIOIOOIOOIOIIOSample Output10/9042ANSWER#in clude using n amespace std;int mai n()int n ,i,flag;char str51,stack51,top=-1;while(ci n str)n=strle n( str);top=_1;flag=0;for(i=0;i-1) top-;elsecout0n;flag=1;break; elsecout0n;flag=1;break;if(top=-1 & i=n & flag=0)cout1n; return 0;elseif(flag=0) cout0n;*9045:判栈输出序列的有效性Problem Descripti on设一个栈的输入序列为1,2,3,.,n-1,n 。请编写一个算法，判断一个序列p1,p2,p3,.,pn 是否是一个有效的栈输出序列。若有效输出1