浙大計算機(jī)學(xué)院考研復(fù)試上機(jī)試題及參考答案.doc

浙江大學(xué)計算機(jī)復(fù)試上機(jī)2005-2007（由林子整理 QQ：170479150） 2005年浙江大學(xué)計算機(jī)學(xué)院考研復(fù)試上機(jī)試題及參考答案(1/5) 第一題：A+B(10分) 結(jié)題題目要求：讀入兩個小于100的正整數(shù)A和B，計算A+B。需要注意的是：A和B的每一位數(shù)字由對應(yīng)的英文單詞給出。輸入格式：測試輸入包含若干測試用例，每個測試用例占一行，格式為A + B =，相鄰兩字符串有一個空格間隔。當(dāng)A和B同時為0時輸入結(jié)束，相應(yīng)的結(jié)果不要輸出。輸出格式：對每個測試用例輸出1行，即A+B的值。輸入樣例：one + two =three four + five six =zero seven + eight nine =zero + zero =輸出樣例：39096#include #include #include #include int main(void)const char data126 = zero, one, two, three, four,five, six, seven, eight, nine, +, =;unsigned a, b;/* 轉(zhuǎn)換后的表達(dá)式參數(shù),如a+b(123+456)*/unsigned i, j, k;/* 臨時變量，作為下標(biāo)*/char str100;/* 輸入字符串，足夠大容量*/char temp6;/* 臨時字符串，用于檢索數(shù)字，如one-1*/char result30;/* 轉(zhuǎn)換后的表達(dá)式參數(shù)，如123+456=*/doa = b = i = j = k = 0;/* 初始化變量 */memset(str, 0, sizeof(str);memset(temp, 0, sizeof(temp);memset(result, 0, sizeof(result);gets(str);/* 獲取輸入字符串，不能使用scanf，因為有空格 */for(i=0, k=0; istrlen(str); +i)for(j=0;!isspace(stri)&istrlen(str);+i,+j) /* 提取一個單詞 */tempj = stri;tempj = 0; /* 字符串結(jié)束標(biāo)記 */for(j=0; j12; j+)/* 把這個單詞轉(zhuǎn)換為數(shù)字 */if(strcmp(temp, dataj) = 0)if( j 0 )。下面列出了N天的記錄。每天的記錄在第一行給出記錄的條目數(shù)M ( 0 )，下面是M行，每行的格式為證件號碼 簽到時間 簽離時間其中時間按“小時:分鐘:秒鐘”（各占2位）給出，證件號碼是長度不超過15的字符串。輸出格式：對每一天的記錄輸出1行，即當(dāng)天開門和關(guān)門人的證件號碼，中間用1空格分隔。注意：在裁判的標(biāo)準(zhǔn)測試輸入中，所有記錄保證完整，每個人的簽到時間在簽離時間之前，且沒有多人同時簽到或者簽離的情況。輸入樣例：31ME3021112225321 00:00:00 23:59:592EE301218 08:05:35 20:56:35MA301134 12:35:45 21:40:423CS301111 15:30:28 17:00:10SC3021234 08:00:00 11:25:25CS301133 21:45:00 21:58:40輸出樣例：ME3021112225321 ME3021112225321EE301218 MA301134SC3021234 CS301133#include #include #include typedef structchar id16;/* 證件號碼長度不超過15位 */char cometime9;/* 時間格式00:00:00 */char leavetime9;/* 時間格式00:00:00 */Record;int main()int N, M, i;/* 記錄的總天數(shù)N，每天記錄的條目數(shù)M */Record *pTimeList;/* 記錄該天出入人員的證件號碼、進(jìn)入時間、離開時間 */int first, last;/* 記錄每天開門的人和關(guān)門的人 */scanf(%d,& N);/* 讀入記錄的總天數(shù) */while(N-)scanf(%d, & M);/* 讀入該天的進(jìn)出人員數(shù) */pTimeList = (Record *)malloc(M*sizeof(Record);for(i=0,first=0,last=0; i 0 )first = i;if( strcmp( pTimeListlast.leavetime, pTimeListi.leavetime) 0)last = i; /* for i */printf(%s %sn, pTimeListfirst.id, pTimeListlast.id);free(pTimeList); /* for N */ 2005年浙江大學(xué)計算機(jī)學(xué)院考研復(fù)試上機(jī)試題及參考答案(3/5) 第三題：分?jǐn)?shù)統(tǒng)計（12分）題目要求：今天的上機(jī)考試雖然有實時的Ranklist，但上面的排名只是根據(jù)完成的題數(shù)排序，沒有考慮每題的分值，所以并不是最后的排名。給定錄取分?jǐn)?shù)線，請你寫程序找出最后通過分?jǐn)?shù)線的考生，并將他們的成績按降序打印。輸入格式：測試輸入包含若干場考試的信息。每場考試信息的第1行給出考生人數(shù)N ( 0 N 1000 )、考題數(shù)M ( 0 M = 10)、分?jǐn)?shù)線（正整數(shù)）G；第2行排序給出第1題至第M題的正整數(shù)分值；以下N行，每行給出一名考生的準(zhǔn)考證號（長度不超過20的字符串）、該生解決的題目總數(shù)m、以及這m道題的題號（題目號由1到M）。當(dāng)讀入的考生人數(shù)為0時，輸入結(jié)束，該場考試不予處理。輸出格式：對每場考試，首先在第1行輸出不低于分?jǐn)?shù)線的考生人數(shù)n，隨后n行按分?jǐn)?shù)從高到低輸出上線考生的考號與分?jǐn)?shù)，其間用1空格分隔。若有多名考生分?jǐn)?shù)相同，則按他們考號的升序輸出。輸入樣例：4 5 2510 10 12 13 15CS004 3 5 1 3CS003 5 2 4 1 3 5CS002 2 1 2CS001 3 2 3 51 2 4010 30CS001 1 22 3 2010 10 10CS000000000000000001 0CS000000000000000002 2 1 20輸出樣例：3CS003 60CS001 37CS004 3701CS000000000000000002 20#include #include #include typedef struct char id21;/* 準(zhǔn)考證號(=20字符)*/ int score;/* 該考生總分*/StuInfo;int main() int N, M, G, n;/* 考生人數(shù)，題目數(shù)，分?jǐn)?shù)線，上線考生數(shù)量 */ int *pMarkList;/* 第1題至第M題的正整數(shù)分值 */ StuInfo *pStuinfo;/* 考生信息 */ int i,j,k,a,b,c,m;/* 臨時變量 */ StuInfo tmp;/* 用于排序 */ while( scanf(%d, &N ) & N!=0 )/* 讀入考生人數(shù)N */ scanf(%d%d, &M, &G);/* 讀入題目數(shù)量和分?jǐn)?shù)線 */ pMarkList = (int *)malloc(M*sizeof(int);/* M道題目的分?jǐn)?shù) */ pStuinfo = (StuInfo *)malloc(N*sizeof(StuInfo);/* N個考生 */ for(i=0; iM; +i)/* 讀入M題每題分?jǐn)?shù) */ scanf(%d, & (pMarkListi) ); for(i=0, n=0; iN; +i)/* 讀入N個考生信息，i用于計數(shù)N次，cnt用于計算上線考生記錄 */ scanf(%s%d, & (pStuinfon.id), &m);/* 準(zhǔn)考證號，解出的題目數(shù)量m */ for(pStuinfon.score=0,j=0; j= G)/* 如果考生上線則記錄下來 */ n+; /* 否則不予記錄，便于排序 */ for(i=0; in-1; +i)/* 輸入完畢，對上線考生先按分?jǐn)?shù)排序，降序 */ for(k=i, j=i+1; j pStuinfok.score) k = j;tmp = pStuinfok;pStuinfok = pStuinfoi;pStuinfoi = tmp; for(i=0; in; i+=k) /* 相同總分考生再按照準(zhǔn)考證號排序 */ /* 統(tǒng)計相同分?jǐn)?shù)考生人數(shù)k */ for(k=1,j=i+1; jn; +j) if(pStuinfoi.score = pStuinfoj.score) k+; else break; /* 下標(biāo)i到i+k的考生分?jǐn)?shù)相同，對這k個考生排序，升序 */ for(a=i; a=i+k-1; a+) for(c=a, b=a+1; b 0) c = b;tmp = pStuinfoa;pStuinfoa = pStuinfoc;pStuinfoc = tmp; printf(%dn,n);/* 排序完畢，按照要求輸出，上線人數(shù) */ for(i=0; in; +i)/* 和每個上線考生的準(zhǔn)考證號和總分?jǐn)?shù) */ printf(%s %dn,pStuinfoi.id,pStuinfoi.score); free(pMarkList); free(pStuinfo); return 0; 2005年浙江大學(xué)計算機(jī)學(xué)院考研復(fù)試上機(jī)試題及參考答案(4/5) 第四題：最大連續(xù)子序列（13分）題目要求：給定K個整數(shù)的序列 N1, N2, ., NK ，其任意連續(xù)子序列可表示為 Ni, Ni+1, .,Nj ，其中 1 = i = j = K。最大連續(xù)子序列是所有連續(xù)子序列中元素和最大的一個，例如給定序列 -2, 11, -4, 13, -5, -2 ，其最大連續(xù)子序列為 11, -4, 13 ，最大和為20。在今年的數(shù)據(jù)結(jié)構(gòu)考卷中，要求編寫程序得到最大和，現(xiàn)在增加一個要求，即還需要輸出該子序列的第一個和最后一個元素。輸入格式：測試輸入包含若干測試用例，每個測試用例占2行，第1行給出正整數(shù)K( 10000)，第2行給出K個整數(shù)，中間用空格分隔。當(dāng)K為0時，輸入結(jié)束，該用例不被處理。輸出格式：對每個測試用例，在1行里輸出最大和、最大連續(xù)子序列的第一個和最后一個元素，中間用空格分隔。如果最大連續(xù)子序列不唯一，則輸出序號i和j最小的那個（如輸入樣例的第2、3組）。若所有K個元素都是負(fù)數(shù)，則定義其最大和為0，輸出整個序列的首尾元素。輸入樣例：6-2 11 -4 13 -5 -210-10 1 2 3 4 -5 -23 3 7 -2165 -8 3 2 5 01103-1 -5 -23-1 0 -20輸出樣例：20 11 1310 1 410 3 510 10 100 -1 -20 0 0#include #include #include int main()long int K, last; /* 輸入數(shù)據(jù)個數(shù)K1000；最大子序列最后一個元素的下標(biāo)last */long int ThisSum, MaxSum, TmpMaxSum, index, *pList;while( scanf(%d, &K) & K )ThisSum = 0;MaxSum = TmpMaxSum = last = LONG_MIN;pList = (long int *)malloc( K * sizeof(long int) );for(index = 0; index MaxSum)/* 輸入含有正數(shù)時，忽略最大子序列中首尾0的影響 */MaxSum = ThisSum;/* 更新MaxSum */if( MaxSum TmpMaxSum )/* 最大值更新時，更新最大子序列最后的數(shù)字 */* 保證最大子序列起始位置在輸入串的最前面 */TmpMaxSum = MaxSum;last = index;if( ThisSum = 0; index- )TmpMaxSum += pListindex;if(TmpMaxSum = MaxSum)break;if( MaxSum 0 ) /* K個數(shù)字都是負(fù)數(shù)，定義最大和為0，輸出首尾元素 */printf(%ld %ld %ldn, 0, pList0, pListK-1);elseprintf(%ld %ld %ldn, MaxSum, pListindex, pListlast );free(pList);return 0; 2005年浙江大學(xué)計算機(jī)學(xué)院考研復(fù)試上機(jī)試題及參考答案(5/5) 第五題：暢通工程（15分）題目要求：某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計表，表中列出了每條道路直接連通的城鎮(zhèn)。省政府“暢通工程”的目標(biāo)是使全省任何兩個城鎮(zhèn)間都可以實現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過道路可達(dá)即可）。問最少還需要建設(shè)多少條道路？輸入格式：測試輸入包含若干測試用例。每個測試用例的第1行給出兩個正整數(shù)，分別是城鎮(zhèn)數(shù)目N ( 1000 )和道路數(shù)目M；隨后的M行對應(yīng)M條道路，每行給出一對正整數(shù)，分別是該條道路直接連通的兩個城鎮(zhèn)的編號。為簡單起見，城鎮(zhèn)從1到N編號。當(dāng)N為0時，輸入結(jié)束，該用例不被處理。輸出格式：對每個測試用例，在1行里輸出最少還需要建設(shè)的道路數(shù)目。輸入樣例：4 21 34 33 31 22 35 21 23 5999 00輸出樣例：102998#include#includeusing namespace std;int n, visited1024;vectorvector connect(1024,vector(1024);int dfs(int a)int i;visiteda=1;for(i=1;inumtown & numtown!=0)cinnumroad;n = numtown;for(i=1;i=numtown;i+)for(j=1;j=numtown;j+)connectij = 0;for(i=1;i=numtown;i+)visitedi = 0;for(i=1;iab;connectab = connectba = 1;for(j=1;j=numtown;j+)connectij = 0;for(i=1;i=numtown;i+)visitedi = 0;for(i=1;iab;connectab = connectba = 1;for(i=1;i=numtown;i+)if (visitedi=0)dfs(i);count+;coutcountendl;return 0; 2006年浙江大學(xué)計算機(jī)學(xué)院考研復(fù)試上機(jī)試題及參考答案(1/5)第一題：A+B(16分)題目要求：讀入兩個小于10000的正整數(shù)A和B，計算A+B。需要注意的是：如果A和B的末尾K（不超過8）位數(shù)字相同，請直接輸出-1。輸入格式：測試輸入包含若干測試用例，每個測試用例占一行，格式為A B K，相鄰兩數(shù)字有一個空格間隔。當(dāng)A和B同時為0時輸入結(jié)束，相應(yīng)的結(jié)果不要輸出。輸出格式：對每個測試用例輸出1行，即A+B的值或者是-1。輸入樣例：1 2 111 21 1108 8 236 64 30 0 1輸出樣例：3-1-1100#include #include int main(void)unsigned int a, b, k;unsigned char ch150, ch250;do scanf(%d %d %d, &a, &b, &k); if( a=0&b=0 | k8 ) break; sprintf(ch1, %d, a); sprintf(ch2, %d, b); strrev(ch1);strrev(ch2); if(strlen(ch1)k)strncat(ch1+strlen(ch1)-1,00000000,8); if(strlen(ch2)k)strncat(ch2+strlen(ch2)-1,00000000,8); if(strncmp(ch1,ch2,k)=0) printf(%dn,-1); else printf(%dn,a+b);while(1);return 0; 2006年浙江大學(xué)計算機(jī)學(xué)院考研復(fù)試上機(jī)試題及參考答案(2/5) 2007-03-31 21:44:14 大 中 小 第二題：統(tǒng)計同成績學(xué)生人數(shù)（12分）題目要求：讀入N名學(xué)生的成績，將獲得某一給定分?jǐn)?shù)的學(xué)生人數(shù)輸出。輸入格式：測試輸入包含若干測試用例，每個測試用例的格式為第1行：N第2行：N名學(xué)生的成績，相鄰兩數(shù)字用一個空格間隔。第3行：給定分?jǐn)?shù)當(dāng)讀到N=0時輸入結(jié)束。其中N不超過1000，成績分?jǐn)?shù)為（包含）0到100之間的一個整數(shù)。輸出格式：對每個測試用例，將獲得給定分?jǐn)?shù)的學(xué)生人數(shù)輸出。輸入樣例：380 60 9060285 660560 75 90 55 75750輸出樣例：102#include #include int main(void)unsigned N, score, num, i;unsigned pList1000;doscanf(%d,&N);if(N=0) break;for(i=0;iN;i+) scanf(%d, &pListi);scanf(%d,&score);for(num=0,i=0;iN;i+) if(pListi=score) num+;printf(%dn, num);while(1);return 0; 2006年浙江大學(xué)計算機(jī)學(xué)院考研復(fù)試上機(jī)試題及參考答案(3/5)第三題：火星A+B （7分）（ZOJ ACM 2529）題目要求：讀入兩個不超過25位的火星正整數(shù)A和B，計算A+B。需要注意的是：在火星上，整數(shù)不是單一進(jìn)制的，第n位的進(jìn)制就是第n個素數(shù)。例如：地球上的10進(jìn)制數(shù)2，在火星上記為“1,0”，因為火星個位數(shù)是2進(jìn)制的；地球上的10進(jìn)制數(shù)38，在火星上記為“1,1,1,0”，因為火星個位數(shù)是2進(jìn)制的，十位數(shù)是3進(jìn)制的，百位數(shù)是5進(jìn)制的，千位數(shù)是7進(jìn)制的輸入格式：測試輸入包含若干測試用例，每個測試用例占一行，包含兩個火星正整數(shù)A和B，火星整數(shù)的相鄰兩位數(shù)用逗號分隔，A和B之間有一個空格間隔。當(dāng)A或B為0時輸入結(jié)束，相應(yīng)的結(jié)果不要輸出。輸出格式：對每個測試用例輸出1行，即火星表示法的A+B的值。輸入樣例：1,0 2,14,2,0 1,2,01 10,6,4,2,10 0輸出樣例：1,0,11,1,1,01,0,0,0,0,0=我的代碼=測試用例和輸出結(jié)果：1,0 2,11,0,14,2,0 1,2,01,1,1,01 10,6,4,2,11,0,0,0,0,00,1,0,1 0,0,1,11,2,00,0,0,0,1 1,0,01,0,10,0,0,1 0,0,0,0,0,11,096,88,82,78,72,70,66,60,58,52,46,42,40,36,30,28,22,18,16,12,10,6,4,2,1 96,88,82,78,72,70,66,60,58,52,46,42,40,36,30,28,22,18,16,12,10,6,4,2,11,96,88,82,78,72,70,66,60,58,52,46,42,40,36,30,28,22,18,16,12,10,6,4,2,00,0,0 0,1,0Press any key to continue#include #include #include #define N 25int IsPrime(int n)int i;if(n2)return 0;for(i=2; in; i+)if(n%i=0) return 0;return 1;int main(void)char op1300, op2300, *p;int i, j, index, num, num1, num2, cnt, breakflag;int PrimeListN+1, op1ListN, op2ListN, OutputListN+1;for(i = 0, j = 0; i N+1; j+)/* 計算每一位的進(jìn)制 */if(IsPrime(j) PrimeListi+ = j;doif(scanf(%s%s, op1, op2) = EOF)break;for(i=0; iN; i+)OutputListi = op1Listi = op2Listi = 0;OutputListN = 0;num1 = 0; breakflag = 1; p = strtok(op1,);while(p) /* 求出第一個輸入火星數(shù)的數(shù)組 */if( ( op1Listnum1+ = atoi(p) ) != 0)breakflag = 0;p = strtok(NULL,);if(breakflag) break; /* 第一個輸入為0，退出循環(huán)；如果放到ZOJ2529，刪除本行 */num2 = 0; breakflag = 1; p = strtok(op2,);while(p) /* 求出第二個輸入火星數(shù)的數(shù)組 */if( ( op2Listnum2+ = atoi(p) ) != 0)breakflag =0;p = strtok(NULL,);if(breakflag) break; /* 第二個輸入為0，退出循環(huán)；如果放到ZOJ2529，刪除本行 */num1-,num2-;/* preset num1 and num2 start from zero */if(num1 = 0; -i)op1Listi + num2 - num1 = op1Listi;op1Listi = 0;if(num1 num2)for(i = num2; i = 0; -i)op2List i + num1 - num2 = op2Listi;op2Listi = 0;cnt = (num1 num2) ? num1 : num2; /* cnt為兩個火星數(shù)的較大位數(shù)，便于確定輸出位數(shù) */for( index=0, i=cnt; i=0 ; i-, index+ )num = op1Listi + op2Listi + OutputListindex;if( num - PrimeListindex = 0 )OutputListindex = num - PrimeListindex;OutputListindex+1+;if( index + 1 cnt ) cnt+; /* 最高位進(jìn)位 */elseOutputListindex = num;while( OutputListcnt=0 & cnt ) cnt-; /* omit leading zeros */for( ; cnt =0 ; cnt- )printf(%d%c, OutputListcnt, (cnt=0)?n:,);while(1);return 0; 2006年浙江大學(xué)計算機(jī)學(xué)院考研復(fù)試上機(jī)試題及參考答案(4/5) 第4題：簡單計算器（7分）題目要求：讀入一個只包含 +, -, *, / 的正整數(shù)計算表達(dá)式，計算該表達(dá)式的值。輸入格式：測試輸入包含若干測試用例，每個測試用例占一行，每行不超過80個字符，整數(shù)和運(yùn)算符之間用一個空格分隔。沒有非法表達(dá)式。當(dāng)一行中只有0時輸入結(jié)束，相應(yīng)的結(jié)果不要輸出。輸出格式：對每個測試用例輸出1行，即該表達(dá)式的值，精確到小數(shù)點后2位。輸入樣例：1 + 24 + 2 * 5 - 7 / 110輸出樣例：3.0013.36#include #include #include #include #define EmptyStack (-1)typedef float ElementType;typedef struct StackRecord int Capacity; int TopOfStack; ElementType *Array;*Stack;Stack CreateStack(int StackSize) Stack S S = (Stack)malloc(sizeof(struct StackRecord); S-Capacity = StackSize; S-TopOfStack = EmptyStack; S-Array = (ElementType*)malloc(sizeof(ElementType)*StackSize); return S;void DisposeStack(Stack S) if(S!=NULL) /* be aware of order ! */ free(S-Array); free(S); /* if stack is empty, return 1 */int IsEmpty(Stack S) return S-TopOfStack = EmptyStack;/* if stack is full, return 1 */int IsFull(Stack S) return S-TopOfStack = S-Capacity;void Push(ElementType X, Stack S) if(IsFull(S) printf(Stack is full ! n); else S-Array+S-TopOfStack = X;ElementType Pop(Stack S) if(IsEmpty(S) printf(Stack is empty ! n); return 0; return S-ArrayS-TopOfStack -;ElementType Top(Stack S) if(IsEmpty(S) printf(Stack is empty ! n); return 0; else return S-ArrayS-TopOfStack;#define NUM 1#define OPRAND 0#define UNKNOWN -1struct List int type; char opcode; float operand;int main(void) unsigned char str81; /* index */ unsigned int num, p, index; float operand1,operand2; struct List pList100; /* p */ Stack S; do /* get input expression */ gets(str); if(strcmp(str,0)=0) break; /* initialize */ S = CreateStack(100); num = p = index = 0; for(index=0;index100;index+) pListindex.type = UNKNOWN; pListindex.opcode = 0; pListindex.operand = 0; /* create postfix */ for(index=0;indexstrlen(str);index+) /* create number */ if(isdigit(strindex) num = num*10 + strindex - 0; else num = 0; /* save number */ if(isdigit(strindex)&(!isdigit(strindex+1) pListp.type = NUM; pListp.operand = (float)num; p+; /* push operand */ if(strindex=*|strindex=/) while(!IsEmpty(S) & (Top(S)=* | Top(S)=/) pListp.type = OPRAND; pListp.opcode = (char)Pop(S); p+; Push(strindex,S); if(strindex=+|strindex=-) while(!IsEmpty(S) pListp.type = OPRAND; pListp.opcode = (char)Pop(S); p+; Push(strindex, S); while(!IsEmpty(S) pListp.type = OPRAND; pListp.opcode = (char)Pop(S); p+; /* calc postfix */ for(p=0; pListp.type!=UNKNOWN; p+) if(pListp.type = NUM) Push(pListp.operand, S); else if(pListp.type = OPRAND) operand2 = Pop(S); operand1 = Pop(S); switch(pListp.opcode) case + : Push( operand1 + operand2, S); break; case - : Push(