C++数据结构上机作业DS作业和实验参考答案总汇.docx

1、C+数据结构上机作业DS作业和实验参考答案总汇2013级DS作业和实验参考答案总汇目录20141217第一次作业：复习C+ 9000，9002第二次作业：顺序表插入和删除操作9003，9004第三次作业：顺序表查找操作和单链表建立9012，9006第四次作业：单链表操作9014，9016，9017第五次作业：特殊线性表栈操作9045，9042，9041第六次作业：特殊线性表队列操作9038，9040第七次作业：二叉树的顺序存储9050第八次作业：复制二叉树9063第九次作业：二叉树的高度宽度9057，9067第十次作业：图的邻接矩阵及遍历9070，9072，9087第十一次作业：图的生成树90

2、76，9077，9088第十二次作业：图的最短路径9092，9091，9085！第一次实验：顺序表9010，9005第二次实验：顺序表2 9097第三次实验：单链表 9007第四次实验：循环链表9008第五次实验：递归 9039第六次实验：二叉树的建立及遍历9019第七次实验：二叉树的结点9054，9056第八次实验：二叉树的存储转换9049第九次实验：哈夫曼编码9068第十次实验：图的邻接表及度9071，9079第十一次实验：图的存储转换9089，9084，9083第十二次实验：模拟考试 ！第一次作业：复习C+9000，90029000:矩形面积Problem Description声明一个

3、名为rect的矩形类，其属性为矩形的左下角和右上角两个点的x和y坐标，该类有效矩形只存在于直角坐标系的第一象限内。若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“data error”。 Input输入的第一行为一个数字n，表示下面有n组数据，每组数据包括2行；每组数据中的第一行表示矩形左下角点的x和y坐标，第二行表示矩形右上角点的x和y坐标。 Output若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“data error”。 Sample Input22 24 41 23 4Sample Output44/9000ANSWER CODE1#include

4、using namespace std;class rectpublic: 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; cinn; while(n-) cinabcd; if(a0|b0|c0|d=c|b=d) coutdata errorendl; els

5、e rect r(a,b,c,d); coutr.area()endl; return 0;9002:数组的循环移位Problem Description对于一个给定的字符型数组循环左移i位，要求尽量不申请空间，实现“原地”操作。 Input输入的第一行为一个数字n,代表接下来有n组数据，每组数据包括2行；每组数据中的第一行为一个字符串（长度不超过50），第二行为一个数字m，代表要左移的位数。 Output循环左移后的字符型数组内容。 Sample Input1abcdefgh3Sample Outputdefghabc/9002ANSWER CODE1#includeusing namesp

6、ace std;#define N 20void Reverse(char a,int from,int to) int i,j;char t;i=from;j=to; while(im; while(m-) cinai; n=strlen(a);i=i%n; Converse(a,n,i); coutaendl; return 0;第二次作业：顺序表插入和删除操作9003，90049003:合并顺序表Problem Description假设有两个由小到大有序的有序顺序表A和B，现要求将表B并入表A中，且A表仍保持由小到大的有序性。若合并后的顺序表表长超过总容量20，则输出“not enou

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

8、t int MaxSize=20;/有两个由小到大有序的有序顺序表A和Bvoid combine(int A,int A_len,int B,int B_len) if(A_len+B_len)MaxSize) coutnot enoughn; else int i=0,j=0,k=0; for(i=0;iAj)/找到Bi在A表中的插入位置j j+; for(k=A_len-1;k=j;k-)/把j(包括j)后的元素往后挪一个位置，空出j来。 Ak+1=Ak; Aj=Bi;/把Bi插入A表中的位置j A_len+;/A表长度加1 coutA_lenendl; for(i=0;i(A_len-1

9、);i+) coutAi ; coutAin; while(n-) cinA_len; for(i=0;iAi; cinB_len; for(i=0;iBi; combine(A,A_len,B,B_len); 9004:连续删除Problem Description从由小到大有序的顺序表中删除其值在s, t之间（含s和t）的所有元素，且不改变顺序表的有序性。如果s=t则显示“data error”；否则输出顺序表的表长和顺序表中的元素，若处理后的顺序表为空，则不输出任何信息。 Input输入的第一行为一个数字n，表示下面有n组数据，每组数据包括3行；每组数据中的第一行包含两个数字s和t，第二

10、行为顺序表的表长len（0len=t，则直接输出“data error”，否则输出两行信息：第一行为处理后顺序表的表长，第二行为处理后顺序表中的元素，元素之间用一个空格分隔，如果处理后的顺序表为空，则不输出任何信息。 Sample Input18 1871 3 5 10 17 19 25Sample Output51 3 5 19 25/9004ANSWER CODE1#include using namespace std;int main() int n,s,t,len,A21,i,s_i,t_i,j,span; cinn; while(n-) cinstlen; for(i=0;iAi;

11、 if(s=t | len20) coutdata errorendl;continue; s_i=0;t_i=len-1; while(As_is & s_it & t_i=0) t_i-; if(s_i=t_i) span=t_i-s_i+1; for(j=s_i;jlen;j+) Aj=Aj+span; len-=span; if(len!=0) coutlenendl; for(i=0;ilen-1;i+) coutAi ; coutAiendl; return 0;第三次作业：顺序表查找操作和单链表建立9012，90069012:找唯一数Problem Description在一个表

12、长为n的顺序表中，除一个元素之外，其余的元素都出现了两次。请找出这个仅出现一次的元素。 Input有多组数据，每组第一行表示表长n（1=n=11111）；第二行表示顺序表的各元素。 Output输出这个唯一数。 Sample Input52 2 1 3 172 1 1 3 -1 2 3Sample Output3-1/9012ANSWER CODE1#include using namespace std;int main() int n,i,j,A11112,B11112; while(cinn) if(n=1 & n=11111) for(i=0;iAi; for(i=0;in;i+) B

13、i=1; for(i=0;in;i+) for(j=i+1;jn;j+) if(Ai=Aj) Bi=0;Bj=0;break; for(i=0;in;i+) if(Bi=1)coutAiendl; return 0;9006:单链表的建立和遍历Problem Description输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。 Input输入数据有多组，每组数据占两行；每组第一行为一个数字N（N=50）；第二行有N个整数。 Output输出这组整数，数字之间用一个空格分隔。 Sample Input512 32 45 78 54Sample Output12

14、32 45 78 54/9006ANSWER CODE1#include using namespace std;struct Nodeint data;Node * next;int main() int N,i,A51; Node *head=new Node,*p,*tail; while(cinN) if(N0) for(i=0;iAi; tail=head; for(i=0;idata=Ai; tail-next=p; tail=p; tail-next=NULL;p=head-next; for(i=0;iN-1;i+) coutdatanext; coutdataendl; re

15、turn 0;第四次作业：单链表操作9014，9016，90179014:删最小值Problem Description设有一单链表，现要求删除其最小值（假设最小值唯一）。若删除成功，则输出被删的最小值；若删除失败，则输出“not exist”。 Input有多组数据，每组第一行为单链表的元素个数n（0=n100）；第二行为单链表的各个元素。 Output若删除成功，则输出被删的最小值；若删除失败，则输出“not exist”。 Sample Input84 2 6 -3 1 9 14 552 4 1 6 7Sample Output-31/9014ANSWER CODE1#includeus

16、ing namespace std;struct Nodeint data;Node *next;int main() int i,n,data100,min; Node *first,*p,*q,*s,*tail; while(cinn) if(n=0)coutnot existn;continue; for(i=0;idatai; first=new Node; first-next=NULL;tail=first; for(i=0;idata=datai;tail-next=s;tail=s; tail-next=NULL; p=first;min=first-next-data; wh

17、ile(p-next) q=p;p=p-next; if(p-datadata; p=first-next;q=first; while(p) if(p-data=min)break; elseq=p;p=p-next; if(p & q)q-next=p-next;delete p;coutminendl; elsecoutnot existn; return 0;9016:查找倒数第k个结点Problem Description有一单链L，请输出该单链表中倒数第k个结点的值。若该结点不存在，则输出“not find”。 Input有多组数据，每组第一行为单链表元素个数n和k值（0n0）；第

18、二行为单链表的各元素。 Output输出该单链表中倒数第k个结点的值。若该结点不存在，则输出“not find”。 Sample Input5 11 2 3 4 55 51 2 3 4 5Sample Output51/9016ANSWER CODE1#includeusing namespace std;struct Nodeint date; Node *next;int main() int n,k,i,c,data100;Node *first,*r,*p,*s; while(cinnk) for(i=0;idatai; first=new Node; r=first; for(i=0

19、;idate=datai; r-next=s;r=s; r-next=NULL; /倒数第k个就是正数第n-k+1个。 if(k=1) p=first-next;c=1; while(p & cnext;c+; if(p & c=(n-k+1)coutdateendl; else coutnot find0，0n100）；第二行为n张选票的内容。 Output输出每个候选人的得票结果，数字之间用一个空格隔开。 Sample Input3 61 3 1 2 2 15 83 3 4 3 3 2 1 1Sample Output3 2 12 1 4 1 0/9017ANSWER CODE1#incl

20、udeusing namespace std;int main() int votes100,n,i,m,c; while(cinmn) for(i=1;i=m;i+) votesi=0; for(i=0;ic; votesc+; for(i=1;im;i+) coutvotesi ; coutvotesmendl; return 0;第五次作业：特殊线性表栈操作9045，9042，90419045:判栈输出序列的有效性Problem Description设一个栈的输入序列为1,2,3,.,n-1,n。请编写一个算法，判断一个序列p1,p2,p3,.,pn是否是一个有效的栈输出序列。若有效输

21、出1，无效输出0。 Input有多组数据，每组第一行为序列长度n（n=50），第二行为一个由1n值组成的长度为n且值无重复的序列。Output栈输出序列有效输出1，无效输出0。Sample Input31 2 333 1 2Sample Output10/9045ANSWER CODE1#include using namespace std;int main() int n,i,j,in,out;/in输入序列指针，out输出序列指针 int output51,stack51,top=-1; while(cinn) for(i=0;ioutputi; top=-1;in=0; for(i=0

22、;iin) for(j=in+1;j=out;j+) stack+top=j; in=out; if(stacktop=outputi) top-; elsecout0n;break; if(i=n & top=-1 ) cout1n; return 0;9042:判操作序列有效性Problem Description假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则成为非法序列。请编写一个对该操作序列的有效性进行判断，若有效输出1，无效输出0。 Input有多组数据，每组为由I和O组成的序列，序列长度不

23、超过50。 Output操作序列有效输出1，无效输出0。 Sample InputIOIIOIOOIOOIOIIOSample Output10/9042ANSWER CODE1#include using namespace std;int main() int n,i,flag; char str51,stack51,top=-1; while(cinstr) n=strlen(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; elseif(flag=0) cout0