北京理工大学数据结构编程练习进步标准答案.doc

《北京理工大学数据结构编程练习进步标准答案.doc》由会员分享，可在线阅读，更多相关《北京理工大学数据结构编程练习进步标准答案.doc（144页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、,.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. 退出输入：根据所选功能的不同，输入格式要求

2、如下所示（第一个数据是功能选择编号，参见测试用例）： 1 多项式A包含的项数，以指数递增的顺序输入多项式A各项的系数（整数）、指数（整数）多项式B包含的项数，以指数递增的顺序输入多项式B各项的系数（整数）、指数（整数）多项式C包含的项数，以指数递增的顺序输入多项式C各项的系数（整数）、指数（整数） 0 操作终止，退出。 输出：对应一组输入，输出一次操作的结果（参见测试用例）。 1 多项式输出格式：以指数递增的顺序输出: ,参见测试用例。零多项式的输出格式为 0 无输出 1.#include#includeusing std:cin;using std:cout;using std:endl;s

3、truct 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-p

4、next=(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

5、;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);out

6、put(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 输出：按照出列的顺序依次输出出列人的编号

7、，编号中间相隔一个空格,每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=(PDAT

8、E) 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 bi

9、gger 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 综教楼后有一个深坑，关于

10、这个坑的来历，有很多种不同的说法。其中一种说法是，在很多年以前，这个坑就已经在那里了。这种说法也被大多数人认可，这是因为该坑有一种特别的结构，想要人工建造是有相当困难的。从横截面图来看，坑底成阶梯状，由从左至右的 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，而这个坑最特别的地方在于坑底每个平面的高度都是不同的。每到夏天，雨水会把坑填满，而在其它的季节，则需要通过人工灌水的方式把坑填满。灌水

11、点设在坑底位置最低的那个平面，每分钟灌水量为一个单位（即高度和宽度均为 1）。随着水位的增长，水自然会向其它平面扩散，当水将某平面覆盖且水高达到一个单位时，就认为该平面被水覆盖了。请你计算每个平面被水覆盖的时间。 灌水 水满后自动扩散 | | * | * * | * * * * V * * V * * * * * * . * * * * * * : * * * * * * : * * * * * * * * * * * * * * * * * * * *4 分钟后 26 分钟后 50 分钟后平面 1 被水覆盖 平面 3 被水覆盖平面 2 被水覆盖输入输入的第一行是一个整数 N，表示平面的数量。

12、从第二行开始的 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=nu

13、m;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=le

14、ft;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

15、-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)=m

16、yclock;output(timedate,n);3. 单词压缩存储(10分)成绩: 10 / 折扣: 0.8如果采用单链表保存单词，可采用如下办法压缩存储空间。如果两个单词的后缀相同，则可以用同一个存储空间保存相同的后缀。例如，原来分别采用单链表保存的单词Str1“abcdef”和单词Str2“dbdef”，经过压缩后的存储形式如下。请设计一个高效的算法完成两个单链表的压缩存储，并估计你所设计算法的时间复杂度。要求：阅读预设代码，编写函数SNODE * ziplist( SNODE * head1, SNODE * head2 )ziplist的功能是：在两个串链表中，查找公共后缀，若有公

17、共后缀，则压缩 并返回指向公共后缀的指针；否则返回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

18、(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-nex

19、t=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*)mall

20、oc(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. 6

21、7. 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

22、; 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 * he

23、ad1, 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!=p

24、2-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! 不匹配输出

25、 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

26、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! 例（上图所示的迷宫数

27、组）输入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;d

28、atexy=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+;brea

29、k;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

30、(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 开始；每驾飞机需要等待的时间是从其提要求开始到分