復試06-14上機真題及答案

1、航空航天大學計算機系復試 06-14 上機及復試上機指導1.本只是提供輔助作用，關鍵還是研友平時動手能力練習和對算法、數據結構的理解，參加過 ACM 的有一定優(yōu)勢 沒參加過的也不用緊張，北航的上機題相對于和，難度上小很多，多練習的話，問題不大;2.上機時，可以快速閱讀所有的題目，按照從易到難的次序做題，保證會的一定得分;3.熟悉編程環(huán)境，熟悉 c 的常用函數;4.為了快速測試代碼的正確性，尤其是矩陣輸入的情況，可以利用標準輸入重定向，freopen(“c:input.txt”,”r”,stdin);加快測試過程;5.注意程序邊界條件的測試;6.如果你疑問，或者提供的材料有問題，歡迎們： 提供北

2、航計算機報考和選導師指導，或者到給留言。14 年上機題第一題，階乘數。輸入一個正整數，輸出時，先輸出這個數本身，跟著一個逗號，再輸出這個數的各位數字的階乘和，等號，階乘和的計算結果，并判斷階乘和是否等于原數，如果相等輸出 Yes，否則輸出 No。題目說明輸入的正整數以及其各位階乘和都不會超出型的表示范圍。輸入樣例 1：145輸出樣例 1：145,1!+4!+5!=145Yes輸入樣例 2：1400輸出樣例 2：1400,1!+4!+0!+0!=27No第二題，五子棋。輸入一個 19*19 的矩陣，只包含數字 0、1、2，表示兩人下五子棋的狀態(tài)，1、2 分別表示兩人的棋子，0 表示空格。要求判斷

3、當前狀態(tài)下是否有人獲勝（橫向、豎向或者斜線方向連成 5 個同色棋子）。題目說明輸入樣例保證每條線上至多只有連續(xù) 5 個同色棋子，并且保證至多只有1 人獲勝。如果有人獲勝，輸出獲勝者（1或 2）加一個冒號，接著輸出獲勝的五連珠的第一個棋子的坐標，從上到下從左到右序號最小的為第一個，序號從 1 開始果無人獲勝，輸出 no。如樣例略。第三題，排版題。輸入若干行字符，表示某的演職員表，每行只有一個冒號，冒號前面是職位，冒號后面是，要求把各行冒號對齊，刪除多余空格后輸出。先輸入一個數字，表示排版要求的冒號位置，該位置號保證比各行冒號前的最大字符數還要大。再輸入若干行字符，最多 50 行，每行最多100

4、個字符，除空格、制表符和回車之外都是有效字符，要求每行的冒號處于格式要求的位置，冒號兩邊與有效單詞之間各有一個空格，冒號前面的單詞之間只有一個空格（刪除多余的空格和制表符），在冒號左邊右對齊，前面全由空格填充，冒號后面的單詞之間也只有一個空格，在冒號右邊左對齊，最后一個單詞后不加空格直接換行。 13 年上機題第一題，給一個真分數的分子分母，輸出約分后的分子分母，送分題，25 分；第二題，簡單版八皇后，15 分；第三題，給出一個標準輸入的正數（開頭末尾沒有多余的 0），輸出其科學表示結果。比如：輸入0.000002，輸出 2e-6；輸入 123.456，輸出1.23456e2；輸入 123456

5、，輸出 1.23456e212 年上機題1.【問題描述】某些整數能分解成若干個連續(xù)整數的和的形式，例如151515= 1= 4= 7+23455 + 68某些整數不能分解為連續(xù)整數的和，例如：16輸入：一個整數N（N = 10000）輸出：整數 N 對應的所有分解組合，按照每個分解中的最小整數從小到大輸出，每個分解占一行，每個數字之間有一個空格（每行最后保留一個空格）；如果沒有任何分解組合，則輸出 NONE。根據題目，任何可以進行分解的整數，必然滿足(m+n)(n-m+1)/2 的形式，可以所有m 和n 組合，如果滿足則輸出，否則輸出 None。嘗試#include #include main

6、()n;while(scanf(%d,&n) != EOF) begin,end;found = 0; for(begin=1;beginn;begin+)for(end=begin+1;endn;end+)/ 連續(xù)整數求和sum = (begin + end)*(end-begin+1)/2; if(sum = n) / 可以分解，輸出結果found = 1;i; for(i=begin;i=end;i+)prf(%d ,i);prf(n);if(found = 0)prf(NONEn);return 0;代碼：解題思路：2.【問題描述】小島面積1 1 1 1 1 1111011 00 01

7、 01 01 1001110 11 01 10 01 1上面矩陣的中的 1 代表海岸線，0 代表小島。求小島面積（即被 1 中包圍的 0 的個數）。注意：僅求這樣的 0，該 0 所在行中被兩個 1 包圍，該 0 所在列中被兩個 1 包圍。輸入：第一行輸入一個整數N，表示輸入方陣的維數輸入一個N 維方陣輸出：小島面積樣例輸入：61111011101111000011 10 00 11 11 01 1110101樣例輸出：8理解題目本身意思，可以發(fā)現對于矩陣中的 0 是否屬于內陸，取決于該 0 所處的行和列上，如果 0 滿足，如下條件則 O 為內陸，否則不是。0 所在的行，0 的左邊和右邊必須有

8、10 所在的列，0 的上面和下面必須有 1所以，解題思路就是，遍歷所有的行和列，改行或列，最左面和最右面（或者最上面和最下面）1 的坐標，然后當遇到 0，判斷是否處于是，則是內陸，面積加 1，否則不加。代碼：#include #include 的值的中間，#define DEBUG_BUAA_122main()N; /矩陣維數island100100;/輸入島數據的方陣解題思路：data1004;#ifdef DEBUG_BUAA_122 freopen(/Users/bwiunbuaa/tmp/oj/buaa_122.in,#endif /* JOBDU_H_ */ while(scanf(

9、%d,&N) != EOF)i,j;/初始化r,stdin);memset(data,-1,100*4*sizeof(/讀入數據 for(i=0;iN;i+)for(j=0;jN;j+);scanf(%d,&islandij);for(i=0;iN;i+)for(j=0;jN;j+)if(islandij = 1) /小島邊界if(datai0 = -1) datai0 = j;if(dataj2 = -1) dataj2 = i;datai1 = j;dataj3 = i;area = 0; for(i=0;iN;i+)for(j=0;j dataj2 & i datai1)area+;da

10、tai0& j /prf(i=%d,j=%dn,i,j); for debugprf(%dn,area);return 0;3.【問題描述】統(tǒng)計關鍵字出現位置輸入：一行標準c 語言代碼（字符個數小于 300），統(tǒng)計出該字符串中關鍵字的 if，while，for 所在的位置，按照關鍵字出現的順序依次輸出。注意雙引號內的不需要統(tǒng)計。輸入：一行標準c 語言代碼，字符個數小于 300輸出：關鍵字 if，while，for 對應的位置，按照關鍵字出現的順序依次輸出。輸出格式為：關鍵字，后跟冒號，然后是出現的位置。掃描到關鍵字就輸出，每個輸出占一行。樣例輸入：#include #include main(

11、) main() i = 0; if(i = 0) prf(YES); return 0;ifwhile = 0;forif = 1;char if_for_while= a;char *str = while; while(ifwhile = 0) ifwhile = 1;forif = 0; if(forif= 0) if_for_while = b; if(ifwhile = 1) if_for_while = c; return 0;樣例輸出：if:43 while:88 if:133if:170首先把輸入字符串切分為一個個的單詞，然后對每個單詞進行匹配。注意 c 語言中的 strto

12、k 函數，不能夠返回位置（當分隔符連續(xù)時，比如+=,計算出前導的分割符有幾個），所以不能滿足本題的要求，必須自己寫獲取單詞的函數（反正也不復雜啦）。因為考慮到引號，的解決方案是首先對輸入字符串進行預處理，將“”內的每個字符都替換為#，然后再進行單詞分割（切詞），最后進行匹配。具體步驟：輸入源碼字符串預處理，將”內的每個字符替換為#一次獲取源碼中的單詞，看是否為查找的，如果是則輸出#include#include #include#define #define#defineDEBUG_BUAA_123 MAX_WORD_LEN 128MAX_LEN 300代碼：解題思路：#define KW_N

13、UM 3/* 將一段源代碼中間的，位于雙引號“”的以#代替*/void replaceQuota(char buf) i;len = strlen(buf); quotaL = 0,quotaR = 0;for(i=0;ilen;i+) if(bufi = )if(quotaL = 0) /左引號quotaL = 1;else /右引號quotaL = quotaR = 0;elseif(quotaL = 1) /該字符屬于引號之間的，替換為#bufi =#;/ 判斷字符是否為分隔符isdelim(char ch)switch(ch)case case case case case case

14、case case casecase :=:,:;:(:):return1;default:return 0;/* 從input數組下標處開始一個單詞,返回的單詞放在word數組中* 返回下次查找開始的位置*/getWord(char input, len = strlen(input); i;isbegin = 0;,char word)wfor(i= 0;i=len) ? -1:i; /如果到文件結尾了，返回-1main()char input300;char wordMAX_WORD_LEN;#ifdef DEBUG_BUAA_123 freopen(/Users/bwiunbuaa/t

15、mp/oj/buaa_123.in,#endif /* JOBDU_H_ */r, stdin);char delim = ,();,+-*/=?:;/單詞分隔符while(gets(input) != NULL)/首先對input進行預處理，將引號中間的字符都轉化為# replaceQuota(input);beg_= 0;dobeg_= getWord(input,beg_,word);wlen = strlen(word);/判斷是否為指定的關鍵字if(strcmp(if,word) = 0)f(if:%dn,beg_-wlen+1);/位置以1開始，而不是0，所pr以要加1else i

16、f(strcmp(while,word) = 0)prf(while:%dn,beg_-wlen+1);else if(strcmp(for,word) = 0)prf(for:%dn,beg_-wlen+1);whieg_= 0);return 0;11 年上機題1.【問題描述】孿生數定義： 如果 A 的約數（因數，包含 1，但不包含A 本身）之和等于 B ， B 的約數（因數）之和等于 A ， A 和 B 稱為孿生數（A 和B 不相等）。試找出正整數 M 和 N 之間的孿生數。輸入：從控制臺輸入兩個正整數M 和N（1=MN=20000），中間用一個空格分隔。輸出：在標準輸出上輸出符合題目描

17、述的 M 和 N 之間的全部孿生數對（包括 M 和 N）。每行輸出一對孿生數，用一個空格隔開，小的先輸出；各行孿生數按照第一個數從小到大的順序輸出，一對孿生數只輸出一次。 如果沒有符合要求的孿生數對，則輸出字符串“NONE”。輸入樣例20 300200 250輸出樣例 220 284 NONE樣例說明樣 例 1 輸 入 的 區(qū) 間 為 20,300 ， 其 間 有 一 對 孿 生 數 對 ， 即 ： 220（1+2+4+5+10+11+20+22+44+55+110=284）和 284（1+2+4+71+142=220）。樣例 2 輸入的區(qū)間是200,250，其間沒有孿生數對，所以輸出字符串：

18、NONE。評分標準該題要求輸出區(qū)間中的所有孿生數對，共有 5 個測試點，提交程序文件名為 exle1.c 或exle1.cpp。這題目很簡單，比較每對數的約數和，看是否滿足條件，如果滿足則輸出。#include #include /計算x約數的和yinzisum(x)i=1,sum=0;if(x = 1) return 0; while(i y)max=x; min=y;elsemax=y; min=x;* array=(*)malloc(sizeof()*(max-min+1);for(i=0;imax-min+1;i+) arrayi=yinzisum(min+i);for(i=0;ima

19、x-min+1;i+) for(j=i+1;jmax-min+1;j+)if(arrayi=j+min & arrayj=i+min)prf(%d %dn,i+min,j+min);flag=1;if(flag=0)prreturnf(NONEn);1;* s=(*)malloc(sizeof()*(max-min+1)2.【問題描述】先輸入兩個矩陣 A 和 B，然后輸入替換位置（左上角），編寫程序將矩陣 A 中從替換位置開始的子矩陣（與B 同樣大小）替換為B，并輸出替換后的矩陣?！据斎胄问健繌目刂婆_先輸入矩陣A 的行數和列數（行數和列數均大于等于 1，小于等于 20），然后在新的行上輸入矩陣

20、 A 的各行數字（以一個空格分隔的整數）。再以同樣的方式輸入矩陣 B。最后輸入替換位置（用一個空格分隔的兩個整數表示，行數和列數都從 1 開始計數，因此兩個整數都大于等于 1）。若替換位置超出了矩陣 A 的行數或列數，則原樣輸出矩陣A?！据敵鲂问健吭跇藴瘦敵錾戏中休敵鎏鎿Q后的矩陣，每行中各數字之間以一個空格分隔?！据斎霕永?1】5 610 234 -200 23 10 98 8 3000100 -1 1 2 035 02000829937399385 963 496 899【輸出樣例 1】10 2 34 -200 232000 100 9 9 9 08 7 85 963 496 8【樣例 1

21、說明】輸入的矩陣 A 為 5 行 6 列，矩陣 B 是 2 行 3 列，替換位置為第 3 行的第 3 列，即：將 A 中第 3 行第 3 列開始的、行數為 2 列數為 3 的子矩陣替換為B。【輸入樣例 2】3 410 22 7635 034 -156 -2000 98299239 99 93【輸出樣例 2】10 22 7635 034 -19 99 9【樣例 2 說明】輸入的矩陣 A 為 3 行 4 列，矩陣 B 是 2 行 3 列，替換位置為第 2 行的第 3 列，即：將 A 中第 2 行第 3 列開始的、行數為 2 列數為 3 的子矩陣替換為B。但該子矩陣超出了A 的范圍，所以只實現了部分

22、替換?！驹u分標準】該題要求輸出替換后的矩陣， 共有 5 個測試點，提交程序文件名為 exle2.c 或exle2.cpp。很簡單,略。解題思路：#include #include void main ()x0,y0,i,j,x1,y1,x2,y2;prf(輸入矩陣行列數行,列:);scanf(%d%d,&x0,&y0);* array0=( for(i=0;ix0;i+)array0i=(for(i=0;ix0;i+)*)malloc(sizeof(*)*x0);*)malloc(sizeof()*y0);for(j=0;jy0;j+)scanf(%d,&array0ij);prf(輸入矩陣行

23、列數行,列:);scanf(%d%d,&x1,&y1);* array1=(*)malloc(sizeof(*)*x1); for(i=0;ix1;i+)array1i=(*)malloc(sizeof()*y1); for(i=0;ix1;i+)for(j=0;jy1;j+)scanf(%d,&array1ij);prf(輸入替換坐標行,列:);scanf(%d%d,&x2,&y2); for(i=0;ix0 & ix1;i+)for(j=0;jy0 & jy1;j+)array0i+x2-1j+y2-1=array1ij; for(i=0;ix0;i+)for(j=0;jy0;j+)prf

24、(%d ,array0ij);phar(n);3. 【問題描述】從鍵盤輸入包含擴展符-的字符串，將其擴展為等價的完整字符，例如將 a-d 擴展為 abcd，并輸出擴展后的字符串。代碼：要求：只處理a-z、A-Z、0-9范圍內的字符擴展，即只有當擴展符前后的字符同時是小寫字母、大寫字母或數字時才進行擴展，其它情況不進行擴展，原樣輸出。例如：a-R、 D-e、0-b、4-B 等字符串都不進行擴展?！据斎胄问健繌逆I盤輸入包含擴展符的字符串【輸出形式】輸出擴展后的字符串【輸入樣例 1】ADEa-g-m02【輸出樣例 1】ADEabcdefghijklm02【輸入樣例 2】cdeT-bcd【輸出樣例 2

25、】cdeT-bcd【樣例說明】將樣例 1 的輸入 ADEa-g-m02 擴展為：ADEabcdefghijklm02；樣例 2 的輸入 cdeT-bcd 中，擴展符前的字符為大寫字母，擴展符后的字符為小寫字母，不在同一范圍內，所以不進行擴展。【評分標準】結果完全正確得 15 分，共 5 個測試點，每個測試點 3expand.cpp。分，提交程序文件expand.c 或很簡單，略。#include #include getindex(char ch)index=-1; if(ch=a & ch=0 & ch=A & ch=Z) index=2;return index;代碼：解題思路：main(

26、)char str300,ch; ch=getchar();i=0,j; while(ch!=n)stri=ch; ch=getchar(); i+;stri=0; for(i=0;stri!=0;i+)if(stri=-)if(getindex(stri-1)=getindex(stri+1) getindex(stri-1)!=-1)ch=stri-1+1; while(chstri+1)&phar(ch);ch+;elsep return 0;har(stri);2010 年上機（回憶版）241.利用公式求 cos(x)=1-x /2!+x /4!-公式已給，重要的就是注意細節(jié)（比如階乘

27、的最好用 double 類型），二級 C 語言的難度。#include #include void main()char str0200,str1200,str400,ch; ch=getchar();i=0,j,k;while(ch!=n)str0i=ch; ch=getchar(); i+;str0i=0; i=0;ch=getchar();while(ch!=n)str1i=ch; ch=getchar(); i+;str1i=0; i=j=k=0;while(str0i!=0& str1j!=0)if(str0istr1j) if(str1j=strk-1)j+;elsestrk=st

28、r1j; j+;k+;elseif(str0i=strk-1)i+; j+;elsestrk=str0i; i+;j+; k+;if(str0i=0)while(str1j!=0)if(str1j!=strk-1) strk+=str1j+;elsej+;elsewhile(str0i!=0)if(str0i!=strk-1) strk+=str0i+;elsei+;length = strlen(str);for(i=0;ilength;i+)prf(%c,stri);#include #include void main()i,j,k,l;scanf(%d,&n);* array0=(fo

29、r(i=0;in;i+)*)malloc(sizeof()*n);scanf(%d,array0+i);* array1=(for(i=0;in;i+)*)malloc(sizeof()*n);scanf(%d,array1+i); for(i=0;in;i+)j=l=0;for(ii=0;ii+)if(array0i=array0ii) j+;for(k=0;kn;k+) if(array1k=array0i)l+;if(j!=l)prf(not equal!n);exit(0);prf(equal! n);09 年上機題1、【問題描述】3.兩個整數數組（無序，可有重復元素），判斷兩個整數數

30、組是否完全相同（重復元素的話，重復次數也要相同）代碼:立方根的 近迭代方程是 y(n+1) = y(n)*2/3 + x/(3*y(n)*y(n),其中 y0=x.求給定的 x 經過 n 次迭代后立方根的值。輸入：輸入有多組數據。每組一行，輸入 x n。輸出：迭代 n 次后的立方根，double 精度,保留小數點后面六位。樣例輸入：3000000 28樣例輸出：144.224957#include #include buaa_func_091()double x,y; i,n;while(scanf(%lf%d,&x,&n)y=x; for(i=1;i=n;i+) y=y*2/3+x/(3*y

31、*y); prf(%.6fn,y);return 0;!= EOF)2、數組排序輸入一個數組的值,求出各個值從小到大排序后的次序。輸入:輸入的第一個數為數組的長度,后面的數為數組中的值,以空格分割輸出:各輸入的值按從小到大排列的次序。sleinput:4-3 75 12 -3output: 1 3 2 1代碼：#include # define N 10000del(a,n);bubblesort(a,n);n);locate( main()a,b,aN,bN,i,j,n,num,z;while(scanf(%d,&n)!=EOF)for(i=0;in;i+)scanf(%d,&ai); bi

32、=ai;bubblesort(a,n); num=del(a,n);for(z=0;zn-1;z+)prf(%d ,locate(a,bz,num);prf(%dn,locate(a,bn-1,num);return 0;del(a,n)i,j,k; for(i=0,j=i+1;jn;j+)if(ai!=aj)if(k=j-i-1)!=0) while(jn)aj-k=aj; j+; i+;j=i; n=n-k;if(an-2=an-1)代碼：n-;return n;bubblesort(a,n)i,j,temp; for(i=0;in;i+)for(j=i;jaj)temp=ai;ai=aj

33、; aj=temp;return 0;locate(a,b,n)i,j,k; for(i=0;in;i+)if(ai=b)return i+1;3、字符串的查找刪除給定文件 filext 按要求輸出 fileout.txt。輸入: 無空格的字符串輸出: 將 filext 刪除輸入的字符串(不區(qū)分大小寫),輸出至 fileout.txtsle輸入:in輸出:將 filext 中的 In、IN、iN、in 刪除,每行中的空格全部提前至行首,輸出至 fileout.txtfilext 中的值為:#include main()prf( Hi );輸出的 fileout.txt 為 #clude tma

34、()prtf(Hi);代碼：#include #include #include main()char a100; i,n,j;char c; scanf(%s,a); n=strlen(a); i=0;c=getchar(); while(c=getchar()!=EOF)if(tolower(c)=tolower(ai)i+;if(i=n)i=0;elseif(i=0)if(c!= )pelsehar(c);for(j=0;ji;j+)phar(aj);i=0;if(c!= )phar(c);08 年上機題1.素數輸入一個整數，要求輸出所有從 1 到這個整數之間個位為 1 的素數，如果沒有

35、則輸出-1（30 分）#include main()n,i,j,flag;while(scanf(%d,&n)!=EOF)flag=0; for(i=2;in;i+)for(j=2;ji;j+)if(i%j=0)break;if(j=i&(i-1)%10=0)if(!flag)prf(%d,i); flag=1;elseprf( %d,i);if(flag)prf(n);else if(!flag)prf(-1n);return 0;2.旋轉矩陣任意輸入兩個 9 階以下矩陣，要求判斷第二是第一個的旋轉矩陣，如果是，輸出旋轉角度（0、90、180、270），如果不是，輸出-1。要求先輸入矩陣階數

36、，然后輸入兩個矩陣，每行兩個數之間可以用任意個空格分隔。行之間用回車分隔，兩個矩陣間用任意的回車分隔。（60 分） #includejudge(a99,b99,n)i,j,count=0;if(a00=b00&a0n-1=b0n-1&an-10=bn-10&an-1n-1=bn-1n-1)for(i=0;in;i+)for(j=0;jn;j+) if(aij=bij) count+;if(count=n*n) return 0;else return -1;elseif(a00=b0n-1&a0n-1=bn-1n-1&an-10=b00&an-1n-1=bn-10)for(i=0;in;i+)

37、 for(j=0;jn;j+)if(aij=bjn-i-1) count+;if(count=n*n) return 90;else return -1;elseif(a00=bn-1n-1&a0n-1=bn-10&an-10=b0n-1&an-1 n-1=b00)for(i=0;in;i+) for(j=0;jn;j+)if(aij=bn-i-1n-j-1) count+;if(count=n*n) return 180;else return -1;elseif(a00=bn-10&a0n-1=b00&an-10=bn-1n-1&an-1n-1=b0n-1)for(i=0;in;i+) f

38、or(j=0;jn;j+)if(aij=bn-j-1i) count+;if(count=n*n) return 270;else return -1;else return -1;main()n,i,j,a99,b99;while(scanf(%d,&n)!=EOF)for(i=0;in;i+) for(j=0;jn;j+)scanf(%d,&aij);for(i=0;in;i+) for(j=0;jn;j+)scanf(%d,&bij);prf(%dn,judge(a,b,n);return 0;3.字符串匹配從 string.in 中讀入數據，然后用戶輸入一個短字符串。要求查找strin

39、g.in中和短字符串的所有匹配，輸出行號、匹配字符串到 string.out 文件中。匹配時不區(qū)分大小寫，并且可以有一個用中括號表示的模式匹配。如“aa123bb”，就是說 aa1bb、aa2bb、aa3bb 都算匹配。（60 分）#include #include #define MAXN 1000 +10 char aMAXNMAXN;charsMAXN;cmpch(char a,char b)if (a=0&a=a&a=A&a=Z& (a=b|(a+a-A)=b)return 1;else return 0;main()n,i,j,m,k,mark,len;while(scanf(%d,&n)=1) for(i=0;in;i+)scanf(%s,ai);scanf(%s,s); m=strlen(s);for(i=0;in;i+)len=strlen(ai); for(j=0,k=0;jlen,km;j+,k+)if(cmpch(aij,sk)continue; elseif(sk!=)goto out; elsemark=0; k=k+1; while(sk!=)if(cmpch(aij,sk) mark=1