浙江大学07计算机上机题(含答案)

《浙江大学07计算机上机题(含答案)》由会员分享，可在线阅读，更多相关《浙江大学07计算机上机题(含答案)（24页珍藏版）》请在装配图网上搜索。

1、 一、 最小长方形题目描述： 给定一系列2维平面点的坐标(x, y)，其中x和y均为整数，要求用一个最小的长方形框将所有点框在。长方形框的边分别平行于x和y坐标轴，点落在边上也算是被框在。输入： 测试输入包含若干测试用例，每个测试用例由一系列坐标组成，每对坐标占一行，其中|x|和|y|小于 231；一对0 坐标标志着一个测试用例的结束。注意(0, 0)不作为任何一个测试用例里面的点。一个没有点的测试用例标志着整个输入的结束。输出： 对每个测试用例，在1行输出2对整数，其间用一个空格隔开。第1对整数是长方形框左下角的坐标，第2对整数是长方形框右上角的坐标。样例输入：12 5623 5613 10

2、0 012 340 00 0样例输出：12 10 23 5612 34 12 34答案：#include using namespace std;int main()int x1,y1,x2,y2,x,y;while(cinxy&(x|y)x1=x2=x; y1=y2=y;while(cinxy&(x|y)x1=x1x?x1:x,y1=y1x?x2:x,y2=y2y?y2:y;coutx1 y1 x2 y2endl;return 0;AC通过了另#includeusing namespace std;int Max(int a,int f) int ma; ma=a0; for(int i=1

3、;ima)ma=ai; return ma; int Min(int a,int f) int mi; mi=a0; for(int i=1;if;i+) if(aimn&(m|n) a10=m;a20=n; for(i=0;a1i!=0|a2i!=0;i+) cina1i+1a2i+1; flag=i; coutMin(a1,flag) Min(a2,flag) Max(a1,flag) Max(a2,flag)endl; return 0; 用数组做的仅供参考另：#include int main() int x,y,x_min,x_max,y_min,y_max; while(1) x_

4、min=232;x_max=-232; y_min=232;y_max=-232; while (scanf(%d %d,&x,&y)&(x!=0|y!=0) if (xx_max) x_max=x; if (xy_max) y_max=y; if (yy_min) y_min=y; if (x_min=232&x_max=-232) break; printf(%d %d %d %dn,x_min,y_min,x_max,y_max); return 0;C语言#includestdio.hint main() int x1,y1,x2,y2; int x,y,flag; while(1)

5、x1=231;y1=231;x2=-231;y2=-231; while(1) scanf(%d%d,&x,&y); if(x=0&y=0) flag+; if(flag=2)return 1; else printf(%d %d %d %dn,x1,y1,x2,y2);break; else flag=0; x1=x1x?x1:x; y1=y1x?x2:x; y2=y2y?y2:y; return 1;已ac#includeint main()int x300,y300,i,xx,xd,yx,yd,k;while(scanf(%d%d,&x0,&y0)!=EOF)if(x0=0&y0=0)r

6、eturn 0;else i=0;doi+;scanf(%d%d,&xi,&yi);while(xi!=0|yi!=0);k=i-1;xx=x0;xd=x0;yx=y0;yd=y0;for(i=0;ixi)xx=xi;if(xdyi)yx=yi;if(ydyi)yd=yi;printf(%d %d %d %dn,xx,yx,xd,yd);return 0;二、 统计字符题目描述： 统计一个给定字符串中指定的字符出现的次数。输入： 测试输入包含若干测试用例，每个测试用例包含2行，第1行为一个长度不超过5的字符串，第2行为一个长度不超过80的字符串。注意这里的字符串包含空格，即空格也可能是要求被统

7、计的字符之一。当读到#时输入结束，相应的结果不要输出。输出： 对每个测试用例，统计第1行中字符串的每个字符在第2行字符串中出现的次数，按如下格式输出： c0 n0 c1 n1 c2 n2 . 其中ci是第1行中第i个字符，ni是ci出现的次数。样例输入：ITHIS IS A TESTi ngthis is a long test string#样例输出：I 2i 3 5n 2g 2答案：#include#includeusingnamespace std;int main() string pa,line; int i,j; while(getline(cin,pa)&pa!=#) getli

8、ne(cin,line); int co5=0; for(i=0;iline.size();i+) for(j=0;jpa.size()&paj!=linei;j+); coj+=jpa.size(); for(i=0;ipa.size();i+) coutpai coiendl; return 0;这个程序只对输入不同字母才有效另：#include#includeint main() char a6,b201; while(gets(a)&a0!=#) int m=strlen(a),n=0,sum; gets(b); n=strlen(b); for(int i=0;im;i+) sum=

9、0; for(int j=0;jn;j+) if(ai=bj)sum+; printf(%c %dn,ai,sum); return 0; 这是我的 仅供参考三、 游船出租题目描述： 现有公园游船租赁处请你编写一个租船管理系统。当游客租船时，管理员输入船号并按下S键，系统开始计时；当游客还船时，管理员输入船号并按下E键，系统结束计时。船号为不超过100的正整数。当管理员将0作为船号输入时，表示一天租船工作结束，系统应输出当天的游客租船次数和平均租船时间。 注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有租船没有还船，或者只有还船没有租船的纪录，系统应能自动忽略这种无效纪录。输入： 测试

10、输入包含若干测试用例，每个测试用例为一整天的租船纪录，格式为： 船号（1100） 键值（S或E） 发生时间（小时:分钟） 每一天的纪录保证按时间递增的顺序给出。当读到船号为-1时，全部输入结束，相应的结果不要输出。输出： 对每个测试用例输出1行，即当天的游客租船次数和平均租船时间（以分钟为单位的精确到个位的整数时间）。样例输入：1 S 08:102 S 08:351 E 10:002 E 13:160 S 17:000 S 17:003 E 08:101 S 08:202 S 09:001 E 09:200 E 17:00-1样例输出：2 1960 01 60答案：1. #include 2.

11、 #include 3. #include 4. #include 5. #include 6. #include 7. #include 8. using namespace std;9. class boatTime10. 11. public:12. boatTime(string str);13. int operator - (const boatTime& rhs);14. int hour;15. int minute;16. ;17. boatTime:boatTime(string str)18. 19. string str1, str2;20. str1.assign(s

12、tr, 0, 2);21. str2.assign(str, 3, 2);22. istringstream is1(str1);23. is1 hour;24. istringstream is2(str2);25. is2 minute;26. 27. inline int boatTime:operator - (const boatTime& rhs) /计算2个时间段的差值28. 29. returnhour * 60 + minute - rhs.hour * 60 - rhs.minute;30. 31. int main()32. 33. /ifstream cin(1.txt

13、);34. int no;35. mapint, pair timeList;36. string rent;37. string currentTime;38. intt = 0;39. int timeSum = 0;40. while(cin no & no != -1)41. 42. cin rent currentTime;43. if(no 100)44. continue;45. if(no = 0)46. 47. cout t ;48. if(cnt = 0)49. cout 0;50. else51. cout round(static_cast(timeSum * 1./t

14、);52. cout endl;53. t = 0;54. timeSum = 0;55. timeList.clear();56. continue;57. 58. if(rent = S)59. 60. timeList.insert(make_pair(no, make_pair(rent, currentTime);61. 62. else63. 64. if(timeList.find(no) != timeList.end()65. 66. +cnt;67. timeSum += boatTime(currentTime) - boatTime(timeListno.second)

15、;68. timeList.erase(timeList.find(no);69. 70. 71. 72. return 0;73. 这个题看上去比较简单，但是做了好久一直wa，看了2L终于发现分钟需要四舍五入。以前一直用的ceil上取整。换成round就ac了。思路：将船号，按键，时间放入一个map中，船号为key，后面元素两个放入pair中。判断输入为S的时候插入记录，如果为E则在map中查找是否有对应的S记录，如果没有则是废操作，忽视之，如果可以查到，则增加租船的次数和时间。然后当船号为0的时候输出租船次数和时间另：本题没必要把所有的数据都存入，只需存储最后归还的时间和借出的时间即可。可

16、以把设置一个变量标记每条船是否被借出，然后求出先借出后归还船的时间差。 1. #include2. struct3. int flag; /*标记船有无被借出,借出为1,否则为0*/ 4. int time;5. boat101;6. int main()7. int hour,minute,number,temptime;/*number为船号*/ 8. char S_E;/*标记是租借还是归还*/ 9. while(scanf(%d,&number) != EOF)10. if(number = -1) return 0;11. int count = 0;12. double total

17、time = 0;13. /*处理number不为0的情况*/ 14. while(number)15. scanf( %c %d:%d,&S_E,&hour,&minute);16. temptime = hour * 60 + minute;17. if(S_E = S)/*如果是借出则把借出的该船标记置1,*/ 18. boatnumber.flag = 1;19. boatnumber.time = temptime;20. 21. else22. if(boatnumber.flag)/*如果是归还之前已借出的该船 ,则记下时间差值,数目加1,并把标志置0.*/ 23. totalt

18、ime += temptime - boatnumber.time;24. count +;25. boatnumber.flag = 0;26. 27. 28. scanf(%d,&number);29. 30. /*如果船号为0时,依然正常输入各值,但此时不做处理*/ 31. scanf( %c %d:%d,&S_E,&hour,&minute);32. if(count)totaltime = totaltime/count;33. printf (%d %.0lfn,count,totaltime);34. 35. return 0;36. 下面是在网上找的的一份c+代码很简练，大家共

19、同学习下。 1. #include 2. #include 3. using namespace std;4. int main()5. 6. int n,t100,h,m,co=0,to=0;7. char cmd10,tt10;8. for(memset(t,-1,sizeof(t);cinn&n=0;)9. cincmdtt;10. if(n0)11. sscanf(tt,%d:%d,&h,&m);12. if(cmd0=S)tn-1=h*60+m;13. else if(tn-1=0)+co,to+=h*60+m-tn-1,tn-1=-1;14. else15. coutco =co)

20、:0)endl;16. co=to=0;17. 18. 19. return 0;20. 四、 EXCEL排序题目描述： Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。 对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有一样或者一样成绩时，则按他们的学号递增排序。输入： 测试输入包含若干测试用例。每个测试用例的第1行包含两个整数 N (N=100000) 和 C，其中 N

21、是纪录的条数，C 是指定排序的列号。以下有N行，每行包含一条学生纪录。每条学生纪录由学号（6位数字，同组测试中没有重复的学号）、（不超过8位且不包含空格的字符串）、成绩（闭区间0, 100的整数）组成，每个项目间用1个空格隔开。当读到 N=0 时，全部输入结束，相应的结果不要输出。输出： 对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有一样或者一样成绩时，则按他们的学号递增排序。样例输入：3 1

22、000007 James 85000010 Amy 90000001 Zoe 604 2000007 James 85000010 Amy 90000001 Zoe 60000002 James 984 3000007 James 85000010 Amy 90000001 Zoe 60000002 James 900 0样例输出：Case 1:000001 Zoe 60000007 James 85000010 Amy 90Case 2:000010 Amy 90000002 James 98000007 James 85000001 Zoe 60Case 3:000001 Zoe 6000

23、0007 James 85000002 James 90000010 Amy 90答案：我觉得这次代码写得比较简洁：用Alrotithm库进行排序 1. #include 2. #include 3. #include 4. #include 5. using namespace std;6. struct info7. string id;8. string name;9. int score;10. ;11. bool cmp_id(const struct info a,const struct info b)12. 13. return a.idb.id;14. 15. bool cm

24、p_name(const struct info a,const struct info b)16. 17. if(a.name=b.name)18. return a.idb.id;19. else20. return a.nameb.name;21. 22. bool cmp_score(const struct info a,const struct info b)23. 24. if(a.score=b.score)25. return a.idb.id;26. else27. return a.scorenc)34. 35. if(n=0&c=0)36. break;37. coun

25、t+;38. struct info datan;39. for(int i=0;idatai.iddatai.namedatai.score;41. switch(c)42. 43. case 1:44. sort(data,data+n,cmp_id);45. break;46. case 2:47. sort(data,data+n,cmp_name);48. break;49. case 3:50. sort(data,data+n,cmp_score);51. 52. printf(Case %d:n,count);53. for(int i=0;in;i+)54. printf(%

26、s %s %dn,datai.id.c_str(),datai.name.c_str(),datai.score);55. 56. 五、 畅通工程题目描述： 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。输入： 测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N, M =100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以与此两村庄

27、间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。输出： 对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。样例输入：3 31 2 11 3 22 3 41 32 3 20 100样例输出：3?答案：用的是Prim算法 1. /Prim Algorithm2. #include 3. #include 4. #include 5. #include 6. #define CITY 1017. #define INFINITE 0x7fffffff8. using namespace std;9. i

28、nt distCITYCITY;10. int flagCITY;11. int cityNum;12. int prim();13. int visitedCount();14. int main(int argc, char *argv)15. 16. ifstream cin(input.txt);17. int i,roadNum,outcome;18. while(cinroadNum)19. 20. if(roadNum=0)21. break;22. memset(dist,0,sizeof(dist);23. memset(flag,0,sizeof(flag);24. cin

29、cityNum;25. int terA,terB,distance;26. for(i=0;iterAterBdistance;29. distterAterB=distance;30. distterBterA=distance;31. 32. outcome=prim();33. if(outcome=-1)34. cout?endl;35. else36. coutoutcomeendl;37. 38. 39.40. int prim()41. 42. int i,j;43. int newBegin,newEnd;44. int allDistance=0;45. int min;4

30、6. flag1=1;47. while(visitedCount()cityNum)48. 49. newBegin=0;50. newEnd=0;51. min=INFINITE;52. for(i=1;i=cityNum;i+)53. 54. if(flagi=1)55. 56. for(j=1;jdistij)61. 62. min=distij;63. newBegin=i;64. newEnd=j;65. 66. 67. 68. 69. 70. if(newBegin=0&newEnd=0)71. return -1;72. flagnewEnd=1;73. allDistance

31、+=distnewBeginnewEnd;74. 75. return allDistance;76. 77.78. int visitedCount()79. 80. int i,sum=0;81. for(i=1;i=cityNum;i+)82. if(flagi=1)83. sum+;84. return sum;85. Prim算法 + DFS遍历 1. #include 2. #include 3. #include 4. #define M 1005. #define MAX 10000006. int distMM;7. int arcsMM;8. int visitedM;9.

32、10. typedef struct11. int fromvex,endvex;12. int length;13. edge; 14. void DFS(int i,int m)15. 16. int j;17. visitedi=1;18. for(j=1;j=m;j+)19. if(arcsij=1&visitedj=0)20. DFS(j,m);21. 22. void prim(int n)23. edge Tn - 1;24. int i,k,min,j,m,v,d;25. int sum = 0;26. edge e;27. for(i = 1;i n;i +)28. Ti -

33、 1.fromvex = 1;29. Ti - 1.endvex = i + 1;30. Ti - 1.length = dist0i;31. 32. for(k = 0;k n-1;k +)33. min = MAX;34. for(j = k;j n -1;j +)35. if(Tj.length min)36. min = Tj.length;37. m = j;38. 39. 40. sum += Tm.length;41. e = Tm;42. Tm = Tk;43. Tk = e;44. v = Tk.endvex;45. for(j = k + 1;j n-1;j +)46. d

34、= distv - 1Tj.endvex- 1;47. if(d Tj.length)48. Tj.length = d;49. Tj.fromvex = v;50. 51. 52. 53. printf(%dn,sum);54. 55. int main()56. int n,m,i,j;57. int from,end,value;58. while(scanf(%d %d,&n,&m) != EOF)59. memset(visited,0,M * sizeof(int);60. if(n = 0) return 0;61. for(i = 0;i M;i +)62. for(j = 0

35、;j M;j +)63. arcsij = 0;64. distij = MAX;65. 66. 67. for(i = 0;i n;i +)68. scanf(%d%d%d,&from,&end,&value);69. distfrom - 1end - 1 = value;70. distend - 1from - 1 = value;71. arcsfromend = 1;72. arcsendfrom = 1;73. 74. DFS(1,m);75. for(i = 1;i m)82. prim(m);83. 84. 85. return 0;86. 六、 最大报销额题目描述： 现有一

36、笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每发票的总额不得超过1000元，每发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。输入： 测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中 Q 是给定的报销额度，N（N=30）是发票数。随后是 N 行输入，每行的格式为： m Type_1:price_1 Type_2:price_2 . Type_m:price_m 其中正整数 m 是这发票上所开物品的件数，Type_i 和 price_i 是第

37、i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时，全部输入结束，相应的结果不要输出。输出： 对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。样例输入：200.00 32 A:23.50 B:100.001 C:650.003 A:59.99 A:120.00 X:10.001200.00 22 B:600.00 A:400.001 C:200.501200.50 32 B:600.00 A:400.001 C:200.501 A:100.00100.00 0样例输出：123.501000.001200.50答案：AC代码, 基本思路是递归求解 1. #inc

38、lude2. #include3. #include4. #include5. #include6.7. using namespace std;8.9. double a31;10. int top;11.12. double max(double x,double y)13. if(xy)return x;14. else return y;15. 16.17. double maxvalue(int k,double left,double Q)/递归求最大报销额 18. /coutleft=left Q=Qendl;19. int mark=0;20. double t=0;21. for(int i=k;itop;i+)22. if(ai=left)23. t=max(maxvalue(i+1,left-ai,Q