北航计算机系考研复试上机真题及答案(06-12年).docx

北京航空航天大学计算机系考研复试 06-12上机真题及答案复试上机指导本真题只是提供辅助作用，关键还是研友平时动手能力练习和对算法、数据结构的理解，参加过ACM的有一定优势 没参加过的也不用紧张，北航的上机题相对于清华和北大，难度上小很多，多练习的话，问题不大;上机时，可以快速阅读所有的题目，按照从易到难的次序做题，保证会的一定得分;熟悉编程环境，熟悉c的常用函数;为了快速测试代码的正确性，尤其是矩阵输入的情况，可以利用标准输入重定向，freopen(“c:\\input.txt”,”r”,stdin);加快测试过程;注意程序边界条件的测试;如果你有什么疑问，或者我们提供的材料有问题，欢迎联系我们：bwiunbuaa@163.com 提供北航计算机报考和选导师指导，或者到 给我们留言。12年上机题1.【问题描述】某些整数能分解成若干个连续整数的和的形式，例如15 = 1 + 2＋3＋4＋5　15 = 4 + 5 + 615 = 7 + 8某些整数不能分解为连续整数的和，例如：16输入：一个整数N（N = 10000）输出：整数N对应的所有分解组合，按照每个分解中的最小整数从小到大输出，每个分解占一行，每个数字之间有一个空格（每行最后保留一个空格）；如果没有任何分解组合，则输出NONE。解题思路：根据题目，任何可以进行分解的整数，必然满足(m+n)(n-m+1)/2的形式，可以暴力尝试所有m和n组合，如果满足则输出，否则输出None。代码：#includestdio.h#includestdlib.hintmain(){int n;while(scanf(%d,n) != EOF){int begin,end;int found = 0;for(begin=1;beginn;begin++){for(end=begin+1;endn;end++){// 连续整数求和int sum = (begin + end)*(end-begin+1)/2;if(sum == n){// 可以分解，输出结果found = 1;int i;for(i=begin;i=end;i++){printf(%d ,i);}printf(\n);}}}if(found == 0){printf(NONE\n);}}return 0;}2.【问题描述】小岛面积? ???1 1 1 1 1 1? ?? ? 1 1 0 0 0 1? ?? ? 1 0 0 0 1 0? ?? ? 1 1 0 1 1 1? ?? ? 0 1 0 1 0 0? ?? ? 1 1 1 1 1 1上面矩阵的中的1代表海岸线，0代表小岛。求小岛面积（即被1中包围的0的个数）。注意：仅求这样的0，该0所在行中被两个1包围，该0所在列中被两个1包围。输入：第一行输入一个整数N，表示输入方阵的维数? 输入一个N维方阵输出：小岛面积样例输入：61 1 1 1 1 11 1 0 0 0 11 0 0 0 1 01 1 0 1 1 10 1 0 1 0 01 1 1 1 1 1样例输出：8解题思路：理解题目本身意思，可以发现对于矩阵中的0是否属于内陆，取决于该0所处的行和列上，如果0满足，如下条件则O为内陆，否则不是。0所在的行，0的左边和右边必须有10所在的列，0的上面和下面必须有1所以，解题思路就是，遍历所有的行和列，记录改行或列，最左面和最右面（或者最上面和最下面）1的坐标，然后当遇到0，判断是否处于记录的值的中间，是，则是内陆，面积加1，否则不加。代码：#includestdio.h#includestdlib.h#define DEBUG_BUAA_122intmain(){int N;//矩阵维数int island[100][100];//输入岛数据的方阵int data[100][4];#ifdef DEBUG_BUAA_122freopen(/Users/bwiunbuaa/tmp/oj/buaa_122.in, r, stdin);#endif/* JOBDU_H_ */while(scanf(%d,N) != EOF){int i,j;//初始化memset(data,-1,100*4*sizeof(int));//读入数据for(i=0;iN;i++){for(j=0;jN;j++){scanf(%d,island[i][j]);}}for(i=0;iN;i++){for(j=0;jN;j++){if(island[i][j] == 1){//小岛边界if(data[i][0] == -1){data[i][0] = j;}if(data[j][2] == -1){data[j][2] = i;}data[i][1] = j;data[j][3] = i;}}}int are