浙江大學07計算機上機題(含答案)

1、 一、 最小長方形題目描述：    給定一系列2維平面點的坐標(x, y)，其中x和y均為整數(shù)，要求用一個最小的長方形框?qū)⑺悬c框在。長方形框的邊分別平行于x和y坐標軸，點落在邊上也算是被框在。輸入：    測試輸入包含若干測試用例，每個測試用例由一系列坐標組成，每對坐標占一行，其中|x|和|y|小于 231；一對0 坐標標志著一個測試用例的結(jié)束。注意(0, 0)不作為任何一個測試用例里面的點。一個沒有點的測試用例標志著整個輸入的結(jié)束。輸出：    對每個測試用例，在1行輸出2對整數(shù)，其間用一個空格隔開。

2、第1對整數(shù)是長方形框左下角的坐標，第2對整數(shù)是長方形框右上角的坐標。樣例輸入：12 5623 5613 100 012 340 00 0樣例輸出：12 10 23 5612 34 12 34答案：#include <iostream>using namespace std;int main()int x1,y1,x2,y2,x,y;while(cin>>x>>y&&(x|y)x1=x2=x; y1=y2=y;while(cin>>x>>y&&(x|y)x1=x1<x?x1:x,y1=y1<y

3、?y1:y,x2=x2>x?x2:x,y2=y2>y?y2:y;cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;return 0;AC通過了另#include<iostream>using namespace std;int Max(int a,int f)    int ma;    ma=a0;      &

4、#160; for(int i=1;i<f;i+)                        if(ai>ma)  ma=ai;                return ma;        int Min(int a,int f)    int mi;    mi=a0;

5、60;       for(int i=1;i<f;i+)                        if(ai<mi)  mi=ai;                return mi;        int main()        int a14

6、61,a2461,i,flag,m,n;        /a10=1;        /flag=0;        while(cin>>m>>n&&(m|n)                a10=m;a20=n;    for(i=0;a1i!=0|a2i!=0;i+)       cin&g

7、t;>a1i+1>>a2i+1;        flag=i;        cout<<Min(a1,flag)<<" "<<Min(a2,flag)<<" "<< Max(a1,flag)<<" "<<Max(a2,flag)<<endl;        return 0; 用數(shù)組做的 &#

8、160;僅供參考另：#include <stdio.h>int main()        int x,y,x_min,x_max,y_min,y_max;        while(1)                        x_min=232;x_max=-232;               

9、 y_min=232;y_max=-232;                while (scanf("%d %d",&x,&y)&&(x!=0|y!=0)                                        if (x>x_max)&

10、#160;                               x_max=x;                        if (x<x_min)                       

11、;         x_min=x;                        if (y>y_max)                                y_max=y;            &

12、#160;           if (y<y_min)                                y_min=y;                                if (x_min=23

13、2&&x_max=-232)                        break;                printf("%d %d %d %dn",x_min,y_min,x_max,y_max);                return 0;C語言#includ

14、e"stdio.h"int main()   int x1,y1,x2,y2;   int x,y,flag;   while(1)      x1=231;y1=231;x2=-231;y2=-231;    while(1)              scanf("%d%d",&x,&y);   &

15、#160;   if(x=0&&y=0)         flag+;         if(flag=2)return 1;           else printf("%d %d %d %dn",x1,y1,x2,y2);break;             

16、0;     else                      flag=0;             x1=x1<x?x1:x;             y1=y1<y?y1:y;        

17、0;    x2=x2>x?x2:x;             y2=y2>y?y2:y;                       return 1;已ac#include<stdio.h>int main()int x300,y300,i,xx,xd,yx,yd,k;while(scanf("%d%d",&a

18、mp;x0,&y0)!=EOF)if(x0=0&&y0=0)return 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;i<=k;i+)if(xx>xi)xx=xi;if(xd<xi)xd=xi;if(yx>yi)yx=yi;if(yd<yi)yd=yi;printf("%d %d %d %dn",xx,yx,xd,yd);return 0;二

19、、 統(tǒng)計字符題目描述：    統(tǒng)計一個給定字符串中指定的字符出現(xiàn)的次數(shù)。輸入：    測試輸入包含若干測試用例，每個測試用例包含2行，第1行為一個長度不超過5的字符串，第2行為一個長度不超過80的字符串。注意這里的字符串包含空格，即空格也可能是要求被統(tǒng)計的字符之一。當讀到'#'時輸入結(jié)束，相應的結(jié)果不要輸出。輸出：    對每個測試用例，統(tǒng)計第1行中字符串的每個字符在第2行字符串中出現(xiàn)的次數(shù)，按如下格式輸出：    c0 n0   

20、; c1 n1    c2 n2    .     其中ci是第1行中第i個字符，ni是ci出現(xiàn)的次數(shù)。樣例輸入：ITHIS IS A TESTi ngthis is a long test string#樣例輸出：I 2i 3 5n 2g 2答案：#include<iostream>#include<string>using  namespace std;int main()        string pa,line;

21、        int i,j;        while(getline(cin,pa)&&pa!="#")                        getline(cin,line);                int co5=0;     

22、;           for(i=0;i<line.size();i+)                                        for(j=0;j<pa.size()&&paj!=linei;j+);             

23、                 coj+=j<pa.size();                                for(i=0;i<pa.size();i+)                    

24、                     cout<<pai<<" "<<coi<<endl;                         return 0;這個程序只對輸入不同字母才有效另：#include<stdio.h>#include<string.h>i

25、nt main()    char a6,b201;    while(gets(a)&&a0!='#')             int m=strlen(a),n=0,sum;         gets(b);         n=strlen(b);       

26、60;for(int i=0;i<m;i+)                     sum=0;                 for(int j=0;j<n;j+)               if(ai=bj) 

27、; sum+;            printf("%c %dn",ai,sum);                      return 0; 這是我的    僅供參考三、 游船出租題目描述：    現(xiàn)有公園游船租賃處請你編寫一個租船管理系統(tǒng)。當游客租船時，管理員輸入船號并

28、按下S鍵，系統(tǒng)開始計時；當游客還船時，管理員輸入船號并按下E鍵，系統(tǒng)結(jié)束計時。船號為不超過100的正整數(shù)。當管理員將0作為船號輸入時，表示一天租船工作結(jié)束，系統(tǒng)應輸出當天的游客租船次數(shù)和平均租船時間。    注意：由于線路偶爾會有故障，可能出現(xiàn)不完整的紀錄，即只有租船沒有還船，或者只有還船沒有租船的紀錄，系統(tǒng)應能自動忽略這種無效紀錄。輸入：    測試輸入包含若干測試用例，每個測試用例為一整天的租船紀錄，格式為：    船號（1100） 鍵值（S或E） 發(fā)生時間（小時:分鐘）  

29、60; 每一天的紀錄保證按時間遞增的順序給出。當讀到船號為-1時，全部輸入結(jié)束，相應的結(jié)果不要輸出。輸出：    對每個測試用例輸出1行，即當天的游客租船次數(shù)和平均租船時間（以分鐘為單位的精確到個位的整數(shù)時間）。樣例輸入：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 <iostream>2. #include <string>

30、;3. #include <sstream>4. #include <map>5. #include <ifstream>6. #include <algorithm>7. #include <cmath>8. using namespace std;9. class boatTime10. 11. public:12.     boatTime(string str);13.     int operator - (const boatTime& rhs);14.  

31、60; int hour;15.     int minute;16. ;17. boatTime:boatTime(string str)18. 19.     string str1, str2;20.     str1.assign(str, 0, 2);21.     str2.assign(str, 3, 2);22.     istringstream is1(str1);23.     is1 >> hour;24.     is

32、tringstream is2(str2);25.     is2 >> minute;26. 27. inline int boatTime:operator - (const boatTime& rhs) /計算2個時間段的差值28. 29.     return  hour * 60 + minute - rhs.hour * 60 - rhs.minute;30. 31. int main()32. 33.   /  ifstream cin("1.txt&

33、quot;);34.     int no;35.     map<int, pair<string, string> > timeList;36.     string rent;37.     string currentTime;38.     intt = 0;39.     int timeSum = 0;40.     while(cin >> no && no != -1)41.  

34、;   42.         cin >> rent >> currentTime;43.         if(no < 0 | no > 100)44.             continue;45.         if(no = 0)46.     

35、   47.             cout <<t << " "48.             if(cnt = 0)49.                 cout << "0"50.      &

36、#160;      else51.                 cout << round(static_cast<double>(timeSum * 1./t);52.             cout << endl;53.            t = 0;54

37、.             timeSum = 0;55.             timeList.clear();56.             continue;57.         58.         if(rent = &q

38、uot;S")59.         60.            timeList.insert(make_pair(no, make_pair(rent, currentTime);61.         62.         else63.         64

39、.             if(timeList.find(no) != timeList.end()65.             66.                 +cnt;67.                 timeSum

40、 += boatTime(currentTime) - boatTime(timeListno.second);68.                 timeList.erase(timeList.find(no);69.             70.         71.     72.     return

41、0;73. 這個題看上去比較簡單，但是做了好久一直wa，看了2L終于發(fā)現(xiàn)分鐘需要四舍五入。以前一直用的ceil上取整。換成round就ac了。思路：將船號，按鍵，時間放入一個map中，船號為key，后面元素兩個放入pair中。判斷輸入為S的時候插入記錄，如果為E則在map中查找是否有對應的S記錄，如果沒有則是廢操作，忽視之，如果可以查到，則增加租船的次數(shù)和時間。然后當船號為0的時候輸出租船次數(shù)和時間另：本題沒必要把所有的數(shù)據(jù)都存入，只需存儲最后歸還的時間和借出的時間即可?？梢园言O置一個變量標記每條船是否被借出，然后求出先借出后歸還船的時間差。 1. #include<stdio.h>

42、;2. 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.  

43、        while(scanf("%d",&number) != EOF)10.                 if(number = -1)        return 0;11.                  int count = 0;12.      

44、;            double totaltime = 0;13.                  /*處理number不為0的情況*/ 14.                  while(number)15.             

45、            scanf(" %c %d:%d",&S_E,&hour,&minute);16.                          temptime = hour * 60 + minute;17.                 

46、;         if(S_E = 'S')/*如果是借出則把借出的該船標記置1,*/ 18.                                  boatnumber.flag = 1;19.                    &#

47、160;             boatnumber.time = temptime;20.                          21.                          else22.      

48、                            if(boatnumber.flag)/*如果是歸還之前已借出的該船 ,則記下時間差值,數(shù)目加1,并把標志置0.*/ 23.                                    

49、0;     totaltime += temptime - boatnumber.time;24.                                          count +;25.                      

50、                    boatnumber.flag = 0;26.                                  27.                   

51、      28.                          scanf("%d",&number);29.                  30.                  /*如果

52、船號為0時,依然正常輸入各值,但此時不做處理*/ 31.                  scanf(" %c %d:%d",&S_E,&hour,&minute);32.                  if(count)  totaltime = totaltime/count;33.      

53、       printf ("%d %.0lfn",count,totaltime);34.         35.         return 0;36. 下面是在網(wǎng)上找的的一份c+代碼很簡練，大家共同學習下。 1. #include <iostream>2. #include <cstdio>3. using namespace std;4. int main()5. 6.     int n,t100,h,m,c

54、o=0,to=0;7.     char cmd10,tt10;8.     for(memset(t,-1,sizeof(t);cin>>n&&n>=0;)9.         cin>>cmd>>tt;10.         if(n>0)11.             sscanf(tt,

55、"%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.       

56、      cout<<co<<" "<<(co?to/co+(to%co*2>=co):0)<<endl;16.             co=to=0;17.         18.     19.     return 0;20. 四、 EXCEL排序題目描述：   

57、Excel可以對一組紀錄按任意指定列排序?，F(xiàn)請你編寫程序?qū)崿F(xiàn)類似功能。    對每個測試用例，首先輸出1行“Case i:”，其中 i 是測試用例的編號（從1開始）。隨后在 N 行中輸出按要求排序后的結(jié)果，即：當 C=1 時，按學號遞增排序；當 C=2時，按的非遞減字典序排序；當 C=3 時，按成績的非遞減排序。當若干學生具有一樣或者一樣成績時，則按他們的學號遞增排序。輸入：    測試輸入包含若干測試用例。每個測試用例的第1行包含兩個整數(shù) N (N<=100000) 和 C，其中 N 是紀錄的條數(shù)，C 是指定排序的列號。以下有

58、N行，每行包含一條學生紀錄。每條學生紀錄由學號（6位數(shù)字，同組測試中沒有重復的學號）、（不超過8位且不包含空格的字符串）、成績（閉區(qū)間0, 100的整數(shù)）組成，每個項目間用1個空格隔開。當讀到 N=0 時，全部輸入結(jié)束，相應的結(jié)果不要輸出。輸出：    對每個測試用例，首先輸出1行“Case i:”，其中 i 是測試用例的編號（從1開始）。隨后在 N 行中輸出按要求排序后的結(jié)果，即：當 C=1 時，按學號遞增排序；當 C=2時，按的非遞減字典序排序；當 C=3 時，按成績的非遞減排序。當若干學生具有一樣或者一樣成績時，則按他們的學號遞增排序。樣例輸入：3 1000

59、007 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 6000000

60、7 James 85000002 James 90000010 Amy 90答案：我覺得這次代碼寫得比較簡潔：用Alrotithm庫進行排序 1. #include <iostream>2. #include <fstream>3. #include <string>4. #include <algorithm>5. using namespace std;6. struct info7.         string id;8.         string nam

61、e;9.         int score;10. ;11. bool cmp_id(const struct info a,const struct info b)12. 13.         return a.id<b.id;14. 15. bool cmp_name(const struct info a,const struct info b)16. 17.         if(=)18.      

62、  return a.id<b.id;19.         else20.         return <;21. 22. bool cmp_score(const struct info a,const struct info b)23. 24.         if(a.score=b.score)25.         return a.id<b.id;26.  

63、      else27.         return a.score<b.score;28. 29. int main(int argc, char *argv)30. 31. /ifstream cin("input.txt");32.         int n,c,count=0;33.         while(cin>>n>>c)34.       &

64、#160; 35.                 if(n=0&&c=0)36.                 break;37.                 count+;38.                 struct info datan;39.

65、                 for(int i=0;i<n;i+)40.                 cin>>datai.id>>>>datai.score;41.                 switch(c)42.        

66、60;       43.                         case 1:44.                         sort(data,data+n,cmp_id);45.                  

67、      break;46.                         case 2:47.                         sort(data,data+n,cmp_name);48.                

68、60;       break;49.                         case 3:50.                         sort(data,data+n,cmp_score);51.                

69、; 52.                 printf("Case %d:n",count);53.                 for(int i=0;i<n;i+)54.                         printf("%s %s %dn",dat

70、ai.id.c_str(),.c_str(),datai.score);55.                         56. 五、 暢通工程題目描述：    省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可）。經(jīng)過調(diào)查評估，得到的統(tǒng)計表中列出了有可能建設公路的若干條道路的成本?，F(xiàn)請你編寫程序，計算出全省暢通需要的最低成本。輸入： 

71、0;  測試輸入包含若干測試用例。每個測試用例的第1行給出評估的道路條數(shù) N、村莊數(shù)目M (N, M < =100 )；隨后的 N 行對應村莊間道路的成本，每行給出一對正整數(shù)，分別是兩個村莊的編號，以與此兩村莊間道路的成本（也是正整數(shù)）。為簡單起見，村莊從1到M編號。當N為0時，全部輸入結(jié)束，相應的結(jié)果不要輸出。輸出：    對每個測試用例，在1行里輸出全省暢通需要的最低成本。若統(tǒng)計數(shù)據(jù)不足以保證暢通，則輸出“?”。樣例輸入：3 31 2 11 3 22 3 41 32 3 20 100樣例輸出：3?答案：用的是Prim算法 1. /Prim Al

72、gorithm2. #include <iostream>3. #include <fstream>4. #include <cstring>5. #include <queue>6. #define CITY 1017. #define INFINITE 0x7fffffff8. using namespace std;9. int distCITYCITY;10. int flagCITY;11. int cityNum;12. int prim();13. int visitedCount();14. int main(int argc,

73、char *argv)15. 16.         ifstream cin("input.txt");17.         int i,roadNum,outcome;18.         while(cin>>roadNum)19.         20.                 if(roadNum=0)2

74、1.                 break;22.                 memset(dist,0,sizeof(dist);23.                 memset(flag,0,sizeof(flag);24.                 c

75、in>>cityNum;25.                 int terA,terB,distance;26.                 for(i=0;i<roadNum;i+)27.                 28.               &#

76、160;         cin>>terA>>terB>>distance;29.                         distterAterB=distance;30.                         distterBterA=distance;31.

77、                 32.                 outcome=prim();33.                 if(outcome=-1)34.                 cout<<"?"<<e

78、ndl;35.                 else36.                 cout<<outcome<<endl;37.         38. 39.40. int prim()41. 42.         int i,j;43.         int newBegi

79、n,newEnd;44.         int allDistance=0;45.         int min;46.         flag1=1;47.         while(visitedCount()<cityNum)48.         49.                 newBe

80、gin=0;50.                 newEnd=0;51.                 min=INFINITE;52.                 for(i=1;i<=cityNum;i+)53.                 54.

81、60;                       if(flagi=1)55.                         56.                                 for(

82、j=1;j<=cityNum;j+)57.                                 58.                                         if(distij!=0&&a

83、mp;flagj=0)59.                                         60.                                         &

84、#160;       if(min>distij)61.                                                 62.                      

85、60;                                 min=distij;63.                                                &#

86、160;    newBegin=i;64.                                                     newEnd=j;65.                 &

87、#160;                               66.                                         67.            

88、                     68.                         69.                 70.                 if(newBegin=0&&am

89、p;newEnd=0)71.                 return -1;72.                 flagnewEnd=1;73.                 allDistance+=distnewBeginnewEnd;74.         75.     

90、0;   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算法 + D

91、FS遍歷 1. #include <stdio.h>2. #include <stdlib.h>3. #include <string.h>4. #define M 1005. #define MAX 10000006. int distMM;7. int arcsMM;8. int visitedM;9.10. typedef struct11.         int fromvex,endvex;12.         int length;13. edge; 14. vo

92、id 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

93、)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.    

94、     edge e;27.         for(i = 1;i < n;i +)28.                 Ti - 1.fromvex = 1;29.                 Ti - 1.endvex = i + 1;30.                 Ti

95、 - 1.length = dist0i;31.         32.         for(k = 0;k < n-1;k +)33.                 min = MAX;34.                 for(j = k;j < n -1;j +)35.         &#

96、160;               if(Tj.length < min)36.                                 min = Tj.length;37.                         

97、0;       m = j;38.                         39.                 40.                 sum += Tm.length;41.            

98、     e = Tm;42.                 Tm = Tk;43.                 Tk = e;44.                 v = Tk.endvex;45.                 for(j = k

99、 + 1;j < n-1;j +)46.                         d  = distv - 1Tj.endvex- 1;47.                         if(d < Tj.length)48.             &

100、#160;                   Tj.length = d;49.                                 Tj.fromvex = v;50.                        

101、; 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 &l