资源描述
1.一元多项式相加(10分)成绩: 10 / 折扣: 0.8题目说明：编写一元多项式加法运算程序。要求用线性链表存储一元多项式（参照课本）。该程序有以下几个功能：1. 多项式求和输入：输入三个多项式，建立三个多项式链表Pa、Pb、Pc （提示：调用CreatePolyn(polynomial &P,int m)。输出：显示三个输入多项式Pa、Pb、Pc、和多项式Pa+Pb、多项式Pa+Pb+Pc （提示：调用AddPolyn(polynomial &Pa, polynomial Pb), 调用PrintPolyn(polynomial P)。0. 退出输入：根据所选功能的不同，输入格式要求如下所示（第一个数据是功能选择编号，参见测试用例）： 1 多项式A包含的项数，以指数递增的顺序输入多项式A各项的系数（整数）、指数（整数）多项式B包含的项数，以指数递增的顺序输入多项式B各项的系数（整数）、指数（整数）多项式C包含的项数，以指数递增的顺序输入多项式C各项的系数（整数）、指数（整数） 0 操作终止，退出。 输出：对应一组输入，输出一次操作的结果（参见测试用例）。 1 多项式输出格式：以指数递增的顺序输出: ,参见测试用例。零多项式的输出格式为 0 无输出 1.#include#includeusing std:cin;using std:cout;using std:endl;struct dateint a;int b;struct date* pnext;typedef struct date DATE;typedef struct date* PDATE;void output(PDATE p)int f=0;p=p-pnext;while(p!=NULL)if(p-a!=0)f=1;couta,b;if(p-pnext=NULL)coutendl;elsecoutpnext;if(f=0)coutpnext;/skip headif(p2!=NULL) p2=p2-pnext;while(p1!=NULL)&(p2!=NULL)if(p1-bp2-b)p3-pnext=(PDATE)malloc(sizeof(DATE);p3=p3-pnext;p3-a=p2-a;p3-b=p2-b;p3-pnext=NULL;p2=p2-pnext;else if(p1-bb)p3-pnext=(PDATE)malloc(sizeof(DATE);p3=p3-pnext;p3-a=p1-a;p3-b=p1-b;p3-pnext=NULL;p1=p1-pnext;elsep3-pnext=(PDATE)malloc(sizeof(DATE);p3=p3-pnext;p3-a=p1-a+p2-a;p3-b=p1-b;p3-pnext=NULL;p1=p1-pnext;p2=p2-pnext;/end whileif(p1=NULL)p3-pnext=p2;if(p2=NULL)p3-pnext=p1;int main()int flag;int n;PDATE P6=NULL;PDATE p=NULL;for(int i=0;ia=0;Pi-b=0;Pi-pnext=NULL;cinflag;if(flag=1)for(int i=1;in;while(n-!=0)p-pnext=(PDATE)malloc(sizeof(DATE);p=p-pnext;cinp-ap-b;p-pnext=NULL;output(Pi);add(P1,P2,P4);output(P4);add(P4,P3,P5);output(P5);0 约瑟夫问题(10分)成绩: 10 / 折扣: 0.80 约瑟夫问题成绩10分 折扣0.8 (本题要求用循环链表实现) 0 ,1, 2, 3题,只能选做三题.约瑟夫问题是一个经典的问题。已知n个人（不妨分别以编号1，2，3，n 代表）围坐在一张圆桌周围，从编号为 k 的人开始，从1开始顺时针报数1, 2, 3, .，顺时针数到m 的那个人，出列并输出。然后从出列的下一个人开始，从1开始继续顺时针报数，数到m的那个人，出列并输出，依此重复下去，直到圆桌周围的人全部出列。 输入：n,k,m 输出：按照出列的顺序依次输出出列人的编号，编号中间相隔一个空格,每10个编号为一行。 非法输入的对应输出如下a) 输入：n、k、m任一个小于1输出：n,m,k must bigger than 0. b) 输入：kn输出：k should not bigger than n.例输入9,3,2输出4 6 8 1 3 7 2 9 5#include#include#includestruct dateint a;struct date* next;typedef struct date DATE;typedef struct date* PDATE;PDATE setnew(PDATE p,int a)PDATE pt;pt=(PDATE) malloc (sizeof(DATE);pt-a=a;pt-next=p-next;p-next=pt;return pt;int count;PDATE del(PDATE p0)if(!count)printf(n);count=10;printf(%d ,p0-a);PDATE p=p0-next;p0-a=p-a;p0-next=p-next;free(p);count-;return p0;int main()count=10;int n=0,k=0,m=0;scanf(%d,%d,%d,&n,&m,&k);if(!(n0&m0&k0)printf(n,m,k must bigger than 0.n);else if(mn)printf(k should not bigger than n.n);elsePDATE p=NULL;PDATE head=(DATE *)malloc(sizeof(DATE);head-next=head;head-a=1;p=head;for(int i=2;ia!=m)p=p-next;while(n)/int temp=k;int temp=k%n+n;while(-temp)p=p-next;del(p);n-;printf(n);2. 综教楼后的那个坑成绩: 10 / 折扣: 0.8描述在 LIT 综教楼后有一个深坑，关于这个坑的来历，有很多种不同的说法。其中一种说法是，在很多年以前，这个坑就已经在那里了。这种说法也被大多数人认可，这是因为该坑有一种特别的结构，想要人工建造是有相当困难的。从横截面图来看，坑底成阶梯状，由从左至右的 1.N 个的平面构成（其中 1 N 100,000），如图： : : 8 7 6 5 4 - 高度 3 2 1平面 1 23 每个平面 i 可以用两个数字来描述，即它的宽度 Wi 和高度 Hi，其中 1 Wi 1,000、1 Hi 1,000,000，而这个坑最特别的地方在于坑底每个平面的高度都是不同的。每到夏天，雨水会把坑填满，而在其它的季节，则需要通过人工灌水的方式把坑填满。灌水点设在坑底位置最低的那个平面，每分钟灌水量为一个单位（即高度和宽度均为 1）。随着水位的增长，水自然会向其它平面扩散，当水将某平面覆盖且水高达到一个单位时，就认为该平面被水覆盖了。请你计算每个平面被水覆盖的时间。 灌水 水满后自动扩散 | | * | * * | * * * * V * * V * * * * * * . * * * * * * : * * * * * * : * * * * * * * * * * * * * * * * * * * *4 分钟后 26 分钟后 50 分钟后平面 1 被水覆盖 平面 3 被水覆盖平面 2 被水覆盖输入输入的第一行是一个整数 N，表示平面的数量。从第二行开始的 N 行上分别有两个整数，分别表示平面的宽度和高度。输出输出每个平面被水覆盖的时间。#include#includestruct datelong long * timedate;long h;int w;struct date* pl;struct date* pr;typedef struct date DATE;typedef struct date* PDATE;PDATE setnew(PDATE p0,int w,long h,long long * num)/p0为左邻PDATE p=(PDATE) malloc(sizeof(DATE);p-timedate=num;p-pl=p0;p-pr=NULL;p0-pr=p;p-h=h;p-w=w;return p;void output(long long* p,long n)while(n-)printf(%lldn,*(+p);int main()long long myclock;long n;int w;long h;PDATE p=NULL,pt=NULL;/set leftpPDATE left=(PDATE) malloc(sizeof(DATE);left-timedate=NULL;left-pl=NULL;left-pr=NULL;left-h=1000000;left-w=0;p=left;pt=left;scanf(%d,&n);long long* timedate=new long longn+1;for(long i=0;iwh;scanf(%d%d,&w,&h);p=setnew(p,w,h,timedate+i+1);if(pt-hh)pt=p;PDATE right=setnew(p,0,1000000,NULL);p=pt;myclock=0;while(p-pl-h!=p-pr-h)*(p-timedate)=myclock+p-w;/计算时间并删除合并if(p-pl-hp-pr-h) myclock+=(p-pr-h-p-h)*p-w;p-pr-w+=p-w;p-pl-pr=p-pr;p-pr-pl=p-pl;pt=p;p=p-pr;delete pt;else if(p-pl-hpr-h)myclock+=(p-pl-h-p-h)*p-w;p-pl-w+=p-w;p-pl-pr=p-pr;p-pr-pl=p-pl;pt=p;p=p-pl;delete pt;/移至下一进水点if(p-pl-hp-h&p-pr-hp-h)continue;else if(p-pl-hpr-h)/左移while(p-hp-pl-h)p=p-pl;else /右移while(p-hp-pr-h)p=p-pr;myclock+=p-w;*(p-timedate)=myclock;output(timedate,n);3. 单词压缩存储(10分)成绩: 10 / 折扣: 0.8如果采用单链表保存单词，可采用如下办法压缩存储空间。如果两个单词的后缀相同，则可以用同一个存储空间保存相同的后缀。例如，原来分别采用单链表保存的单词Str1“abcdef”和单词Str2“dbdef”，经过压缩后的存储形式如下。请设计一个高效的算法完成两个单链表的压缩存储，并估计你所设计算法的时间复杂度。要求：阅读预设代码，编写函数SNODE * ziplist( SNODE * head1, SNODE * head2 )ziplist的功能是：在两个串链表中，查找公共后缀，若有公共后缀，则压缩 并返回指向公共后缀的指针；否则返回NULL预设代码前置代码view plaincopy to clipboardprint?1. /*PRESETCODEBEGIN-NEVERTOUCHCODEBELOW*/2. 3. #include 4. #include 5. 6. typedefstructsdata 7. chardata; 8. structsdata*next; 9. SNODE; 10. 11. voidsetlink(SNODE*,char*),outlink(SNODE*); 12. intlistlen(SNODE*); 13. SNODE*ziplist(SNODE*,SNODE*); 14. SNODE*findlist(SNODE*,SNODE*); 15. 16. intmain() 17. 18. SNODE*head1,*head2,*head; 19. charstr1100,str2100; 20. 21. gets(str1); 22. gets(str2); 23. 24. head1=(SNODE*)malloc(sizeof(SNODE); 25. head2=(SNODE*)malloc(sizeof(SNODE); 26. head=(SNODE*)malloc(sizeof(SNODE); 27. head-next=head1-next=head2-next=NULL; 28. 29. setlink(head1,str1); 30. setlink(head2,str2); 31. 32. head-next=ziplist(head1,head2); 33. 34. head-next=findlist(head1,head2); 35. outlink(head); 36. return0; 37. 38. 39. voidsetlink(SNODE*head,char*str) 40. 41. SNODE*p; 42. 43. while(*str!=0) 44. p=(SNODE*)malloc(sizeof(SNODE); 45. p-data=*str; 46. p-next=NULL; 47. str+; 48. head-next=p; 49. head=p; 50. 51. return; 52. 53. 54. voidoutlink(SNODE*head) 55. 56. while(head-next!=NULL) 57. 58. printf(%c,head-next-data); 59. head=head-next; 60. 61. printf(n); 62. return; 63. 64. 65. intlistlen(SNODE*head) 66. 67. intlen=0; 68. while(head-next!=NULL) 69. 70. len+; 71. head=head-next; 72. 73. returnlen; 74. 75. 76. SNODE*findlist(SNODE*head1,SNODE*head2) 77. 78. intm,n; 79. SNODE*p1=head1,*p2=head2; 80. 81. m=listlen(head1); 82. n=listlen(head2); 83. 84. while(mn) 85. p1=p1-next; 86. m-; 87. 88. while(mnext; 90. n-; 91. 92. 93. while(p1-next!=NULL&p1-next!=p2-next) 94. 95. p1=p1-next; 96. p2=p2-next; 97. 98. returnp1-next; 99. 100. 101. /*Hereiswaitingforyou!*/102. /* 103. SNODE*ziplist(SNODE*head1,SNODE*head2) 104. 105. 106. */107. 108. /*PRESETCODEEND-NEVERTOUCHCODEABOVE*/SNODE * ziplist( SNODE * head1, SNODE * head2 ) int m, n; SNODE *p1=head1, *p2=head2,*p11=NULL,*p22=NULL;m = listlen( head1 );n = listlen( head2 );while ( m n )p1 = p1-next;m-;while ( m next;n-;p11=p1;p22=p2;while(p1-next-next!=NULL)if(p1-next-data!=p2-next-data)p11=p1-next;p22=p2-next;p1=p1-next;p2=p2-next;if(p1-next-data!=p2-next-data)return NULL;elsep22-next=p11-next;return p11-next; 4. 括号匹配（10分）成绩: 10 / 折扣: 0.84 括号匹配 （10分）成绩: 10 / 折扣: 0.8 假设一个算术表达式中包含圆括号、方括号两种类型的括号，试编写一个判断表达式中括号是否匹配的程序，匹配返回Match succeed!，否则返回Match false!。例 1+2*(3+4*(5+6)括号匹配 (1+2)*(1+2*(1+2)+3) 括号不匹配输入包含圆括号、方括号两种类型括号的算术表达式输出匹配输出 Match succeed! 不匹配输出 Match false!例输入 1+2* (3+4*(5+6) 输出Match succeed! #includeint main()int flag=0;char a1000=0;char* p;p=&a0;char temp;temp=getchar();*p=temp;while(temp!=n)switch (temp)case (:p+;*p=temp;break;case ):if(*p!=()printf(Match false!n);return 0;*p=0;p-;break;case :p+;*p=temp;break;case:if(*p!=)printf(Match false!n);return 0;*p=0;p-;break;/endswiychtemp=getchar();/end whilwprintf(Match succeed!n);return 0;5. 迷宫问题（15分）成绩: 15 / 折扣: 0.85 迷宫问题（15分）成绩: 15 / 折扣: 0.8迷宫有一个入口，一个出口。一个人从入口走进迷宫，目标是找到出口。阴影部分和迷宫的外框为墙，每一步走一格，每格有四个可走的方向，探索顺序为：南、东、北、西。 输入：输入迷宫数组输出：若有解，输出从入口到出口的一条路径，否则输出 there is no solution! 例（上图所示的迷宫数组）输入4 4 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 输出 #includeusing std:cin;using std:cout;using std:endl;int main()int a,b;cinab;bool date102102;for(int i=0;i102;i+)for (int j=0;j102;j+)dateij=1;int stack5004=0;int p=1;stack02=5;stack10=1;stack11=1;stack13=5;for(int x=1;x=a;x+)/input start for(int y=1;ytemp;datexy=temp;/input finishint p1,p2;while(!(stackp0=a&stackp1=b)/find startswitch (stackp2)case 0:/downif(stackp2=stackp3)stackp2+;break;p1=stackp0+1;p2=stackp1;if(datep1p2)/wallstackp2+;goto x1;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=2;break;case 1:/rightx1:if(stackp2=stackp3)stackp2+;break;p1=stackp0;p2=stackp1+1;if(datep1p2)/wallstackp2+;goto x2;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=3;break;case 2:/upx2:if(stackp2=stackp3)stackp2+;break;p1=stackp0-1;p2=stackp1;if(datep1p2)/wallstackp2+;goto x3;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=0;break;case 3:/leftx3:if(stackp2=stackp3)stackp2+;break;p1=stackp0;p2=stackp1-1;if(datep1p2)/wallstackp2+;goto x4;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=1;break;case 4:/backx4:stackp2=0;p-;break;case 5:coutthere is no solution!n;return 0;/find finishp=1;while(stackp2)coutstackp0,stackp1 ;p+;coutstackp0,stackp1 endl;return 0;6. 飞机场调度(15分)成绩: 15 / 折扣: 0.8在本实验中，需要同学们利用队列实现一个飞机场调度模拟，根据不同的输入参数得到不同的模拟结果。程序运行开始，首先需要输入以下参数： 机场跑道数，飞机降落占用跑道时间（整数）， 飞机起飞占用跑道时间（整数） 整个模拟的时间以分钟为单位，从 0 开始，每分钟的开始需要输入： 该分钟要求降落飞机数， 该分钟要求起飞飞机数 机场调度原则是降落优先起飞，在此原则下按来的顺序排队；每驾飞机都有一个编号，要起飞飞机从 1 开始，要降落飞机从 5001 开始；每驾飞机需要等待的时间是从其提要求开始到分配跑道为止；每个跑道都有一个编号（从 1 开始），都可以用来降落和起飞，但同一时间只能被一架飞机占用，占用时间为该飞机降落（起飞）占用跑道时间。 当输入的要求降落飞机数和要求起飞飞机数都小于 0 时，表示机场关闭，不再接受新的请求，但余下没有降落（起飞）的飞机需照常进行。 模拟过程中需要随时输出以下数据： 1. 当前时间 (%4d) 2. 所有从占用变为空闲的跑道编号 （在输入降落、起飞飞机数前输出） 3. 可以降落（起飞）飞机编号（ 04d ）、跑道编号（ 02d ） （在输入降落、起飞飞机数后输出） 模拟结束后，程序需输出以下统计结果： 1. 模拟时间（ 4d ） 2. 降落平均等待时间（ 4.1f ） 3. 起飞平均等待时间（ 4.1f ） 4. 每条跑道被占用时间（ 4d ） 5. 跑道平均被占用的百分比（ 4.1f ， 平均占用时间 100/ 模拟时间） 例： （下面的黑斜体为输入） 4 3 5 Current Time: 0 1 4 airplane 5001 is ready to land on runway 01 airplane 0001 is ready to takeoff on runway 02 airplane 0002 is ready to takeoff on runway 03 airplane 0003 is ready to takeoff on runway 04 Current Time: 1 0 0 Current Time: 2 0 2 Current Time: 3 runway 01 is free 3 0 airplane 5002 is ready to land on runway 01 Current Time: 4 0 0 Current Time: 5 runway 02 is free runway 03 is free runway 04 is free 0 0 airplane 5003 is ready to land on runway 02 airplane 5004 is ready to land on runway 03 airplane 0004 is ready to takeoff on runway 04 Current Time: 6 runway 01 is free 2 4 airplane 5005 is ready to land on runway 01 Current Time: 7 -1 -1 Current Time: 8runway 02 is freerunway 03 is freeairplane 5006 is ready to land on runway 02airplane 0005 is ready to takeoff on runway 03Current Time: 9runway 01 is freeairplane 0006 is ready to takeoff on runway 01Current Time: 10runway 04 is freeairplane 0007 is ready to takeoff on runway 04Current Time: 11runway 02 is freeairplane 0008 is ready to takeoff on runway 02Current Time: 12Current Time: 13runway 03 is freeairplane 0009 is ready to takeoff on runway 03Current Time: 14runway 01 is freeairplane 0010 is ready to takeoff on runway 01Current Time: 15runway 04 is freeCurrent Time: 16runway 02 is freeCurrent Time: 17Current Time: 18runway 03 is freeCurrent Time: 19runway 01 is freesimulation finishedsimulation time: 19average waiting time of landing: 1.0average waiting time of takeoff: 4.2runway 01 busy time: 19runway 02 busy time: 16runway 03 busy time: 18runway 04 busy time: 15runway average busy time percentage: 89.5% /#include#includeint time,wayn,downtime,uptime,up,down,upwaiting,downwaiting,upcount,downcount,use;int* way;float* waytime;int manage()for(int i=1;i0)*(way+i)=downtime;(*(waytime+i)+=downtime;printf(airplane %04d is ready to land on runway %02dn,downcount+,i);downwaiting-;use+;else if(upwaiting0)*(way+i)=uptime;(*(waytime+i)+=uptime;printf(airplane %04d is ready to takeoff on runway %02dn,upcount+,i);upwaiting-;use+;else*(way+i)=-1;else if(*(way+i)0)*(way+i)=downtime;(*(waytime+i)+=downtime;printf(airplane %04d is ready to land on runway %02dn,downcount+,i);downwaiting-;use+;else if(upwaiting0)*(way+i)=uptime;(*(waytime+i)+=uptime;printf(airplane %04d is ready to takeoff on runway %02dn,upcount+,i);upwaiting-;use+;/end of forreturn 0;int main()float avewaitingup=0;float avewaitingdown=0;scanf(%d%d%d,&wayn,&downtime,&uptime);way=(int*) malloc (sizeof(int)*(wayn+1);waytime=(float*) malloc (sizeof(float)*(wayn+1);for(int i=0;i=0&down=0;)upwaiting+=up;downwaiting+=down;manage();avewaitingup+=upwaiting;avewaitingdown+=downwaiting;for(int i=0;i=wayn;i+)(*(way+i)-;printf(Current Time: %4dn,time+);for(int i=1;i=wayn;i+)if(*(way+i)=0)printf(runway %02d is freen,i);scanf(%d%d,&down,&up);manage();avewaitingup+=upwaiting;avewaitingdown+=downwaiting;while(use)for(int i=0;i=wayn;i+)(*(way+i)-;printf(Current Time: %4dn,time+);for(int i=1;i=wayn;i+)if(*(way+i)=0)printf(runway %02d is freen,i);manage();avewaitingup+=upwaiting;avewaitingdown+=downwaiting;time-;/finishprintf(simulation finishednsimulation time: %4dn,time);float aa=avewaitingdown/(downcount-5000-1),bb=avewaitingup/(upcount-1),cc=0;if(avewaitingdown=0|downcount=5001)aa=0;if(avewaitingup=0|upcount=1)bb=0;printf(average waiting time of landing: %4.1fnaverage waiting time of takeoff: %4.1fn,aa,bb);float all=0;int i=1;for(;i=wayn;i+)printf(runway %02d busy time: %4.0fn,i,*(waytime+i);all+=*(waytime+i);if(all=0|time=0|wayn=0)cc=0;elsecc=all/wayn/time*100;
展开阅读全文