北航计算机复试-06-14上机真题及答案

北京航空航天大学计算机系考研复试06-14上机真题及答案复试上机指导1.本真题只是提供辅助作用，关键还是研友平时动手能力练习和对算法、数据结构的理解，参加过ACM的有一定优势没参加过的也不用紧张，北航的上机题相对于清华和北大，难度上小很多，多练习的话，问题不大;2.上机时，可以快速阅读所有的题目，按照从易到难的次序做题，保证会的一定得分;3.熟悉编程环境，熟悉c的常用函数;4.为了快速测试代码的正确性，尤其是矩阵输入的情况，可以利用标准输入重定向，freopen(“c:\\input.txt”,”r”,stdin);加快测试过程;5.注意程序边界条件的测试;6.如果你有什么疑问，或者我们提供的材料有问题，欢迎联系我们：[e-mail]提供北航计算机报考和选导师指导，或者到kao400.com给我们留言。14年上机题第一题，阶乘数。输入一个正整数，输出时，先输出这个数本身，跟着一个逗号，再输出这个数的各位数字的阶乘和，等号，阶乘和的计算结果，并判断阶乘和是否等于原数，如果相等输出Yes，否则输出No。题目说明输入的正整数以及其各位阶乘和都不会超出int型的表示范围。输入样例1：145输出样例1：145,1!+4!+5!=145Yes输入样例2：1400输出样例2：1400,1!+4!+0!+0!=27No第二题，五子棋。输入一个19*19的矩阵，只包含数字0、1、2，表示两人下五子棋的棋牌状态，1、2分别表示两人的棋子，0表示空格。要求判断当前状态下是否有人获胜（横向、竖向或者斜线方向连成5个同色棋子）。题目说明输入样例保证每条线上至多只有连续5个同色棋子，并且保证至多只有1人获胜。如果有人获胜，输出获胜者（1或2）加一个冒号，接着输出获胜的五连珠的第一个棋子的坐标，从上到下从左到右序号最小的为第一个，序号从1开始编号。如果无人获胜，输出no。样例略。第三题，排版题。输入若干行字符，表示某电影的演职员表，每行只有一个冒号，冒号前面是职位，冒号后面是姓名，要求把各行冒号对齐，删除多余空格后输出。先输入一个数字，表示排版要求的冒号位置，该位置号保证比各行冒号前的最大字符数还要大。再输入若干行字符，最多50行，每行最多100个字符，除空格、制表符和回车之外都是有效字符，要求每行的冒号处于格式要求的位置，冒号两边与有效单词之间各有一个空格，冒号前面的单词之间只有一个空格（删除多余的空格和制表符），在冒号左边右对齐，前面全由空格填充，冒号后面的单词之间也只有一个空格，在冒号右边左对齐，最后一个单词后不加空格直接换行。13年上机题第一题，给一个真分数的分子分母，输出约分后的分子分母，送分题，25分；第二题，简单版八皇后，15分；第三题，给出一个标准输入的正数（开头末尾没有多余的0），输出其科学计数法表示结果。比如：输入0.000002，输出2e-6；输入123.456，输出1.23456e2；输入123456，输出1.23456e212年上机题1.【问题描述】某些整数能分解成若干个连续整数的和的形式，例如15=1+2＋3＋4＋515=4+5+615=7+8某些整数不能分解为连续整数的和，例如：16输入：一个整数N（N=10000）输出：整数N对应的所有分解组合，按照每个分解中的最小整数从小到大输出，每个分解占一行，每个数字之间有一个空格（每行最后保留一个空格）；如果没有任何分解组合，则输出NONE。解题思路：根据题目，任何可以进行分解的整数，必然满足(m+n)(n-m+1)/2的形式，可以暴力尝试所有m和n组合，如果满足则输出，否则输出None。代码：#includestdio.h#includestdlib.hintmain(){intn;while(scanf(%d,&n)!=EOF){intbegin,end;intfound=0;for(begin=1;beginn;begin++){for(end=begin+1;endn;end++){//连续整数求和intsum=(begin+end)*(end-begin+1)/2;if(sum==n){//可以分解，输出结果found=1;inti;for(i=begin;i=end;i++){printf(%d,i);}printf(\n);}}}if(found==0){printf(NONE\n);}}return0;}2.【问题描述】小岛面积111111110001100010110111010100111111上面矩阵的中的1代表海岸线，0代表小岛。求小岛面积（即被1中包围的0的个数）。注意：仅求这样的0，该0所在行中被两个1包围，该0所在列中被两个1包围。输入：第一行输入一个整数N，表示输入方阵的维数输入一个N维方阵输出：小岛面积样例输入：6111111110001100010110111010100111111样例输出：8解题思路：理解题目本身意思，可以发现对于矩阵中的0是否属于内陆，取决于该0所处的行和列上，如果0满足，如下条件则O为内陆，否则不是。0所在的行，0的左边和右边必须有10所在的列，0的上面和下面必须有1所以，解题思路就是，遍历所有的行和列，记录改行或列，最左面和最右面（或者最上面和最下面）1的坐标，然后当遇到0，判断是否处于记录的值的中间，是，则是内陆，面积加1，否则不加。代码：#includestdio.h#includestdlib.h#defineDEBUG_BUAA_122intmain(){intN;//矩阵维数intisland[100][100];//输入岛数据的方阵intdata[100][4];#ifdefDEBUG_BUAA_122freopen(/Users/bwiunbuaa/tmp/oj/buaa_122.in,r,stdin);#endif/*JOBDU_H_*/while(scanf(%d,&N)!=EOF){inti,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;}}}intarea=0;for(i=0;iN;i++){for(j=0;jN;j++){if(island[i][j]==0){//小岛边界if(idata[j][2]&&idata[j][3]&&jdata[i][0]&&jdata[i][1]){area++;//printf(i=%d,j=%d\n,i,j);fordebug}}}}printf(%d\n,area);}return0;}3.【问题描述】统计关键字出现位置输入：一行标准c语言代码（字符个数小于300），统计出该字符串中关键字的if，while，for所在的位置，按照关键字出现的顺序依次输出。注意双引号内的不需要统计。输入：一行标准c语言代码，字符个数小于300输出：关键字if，while，for对应的位置，按照关键字出现的顺序依次输出。输出格式为：关键字，后跟冒号，然后是出现的位置。扫描到关键字就输出，每个输出占一行。样例输入：#includestdio.hintmain(){inti=0;if(i==0)printf(YES);return0;}#includestdio.hintmain(){intifwhile=0;intforif=1;charif_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';}return0;}样例输出：if:43while:88if:133if:170解题思路：首先把输入字符串切分为一个个的单词，然后对每个单词进行匹配。注意c语言中的strtok函数，不能够返回位置（当分隔符连续时，比如+=,计算出前导的分割符有几个），所以不能满足本题的要求，必须自己写获取单词的函数（反正也不复杂啦）。因为考虑到引号的问题，我们的解决方案是首先对输入字符串进行预处理，将“”内的每个字符都替换为#，然后再进行单词分割（切词），最后进行匹配。具体步骤：输入源码字符串预处理，将””内的每个字符替换为#一次获取源码中的单词，看是否为查找的关键词，如果是则输出代码：#includestdio.h#includestdlib.h#includestring.h#defineDEBUG_BUAA_123#defineMAX_WORD_LEN128#defineMAX_LEN300#defineKW_NUM3/***将一段源代码中间的，位于双引号“”的以#代替*/voidreplaceQuota(charbuf[]){inti;intlen=strlen(buf);intquotaL=0,quotaR=0;for(i=0;ilen;i++){if(buf[i]==''){if(quotaL==0){//左引号quotaL=1;}else{//右引号quotaL=quotaR=0;}}else{if(quotaL==1){//该字符属于引号之间的，替换为#buf[i]='#';}}}}//判断字符是否为分隔符intisdelim(charch){switch(ch){case'':case'=':case',':case';':case'':case'':case'(':case')':case'{':case'}':return1;default:return0;}}/***从input数组下标pos处开始一个单词,返回的单词放在word数组中*返回下次查找开始的位置*/intgetWord(charinput[],intpos,charword[]){intlen=strlen(input);inti;intisbegin=0;intwpos=0;for(i=pos;ilen;i++){if(isdelim(input[i])){if(isbegin==0){//略过该分隔符continue;}else{//单词获取结束break;}}else{isbegin=1;word[wpos++]=input[i];}}word[wpos]='\0';//结束标志，勿忘，切记return(i=len)?-1:i;//如果到文件结尾了，返回-1}intmain(){charinput[300];charword[MAX_WORD_LEN];#ifdefDEBUG_BUAA_123freopen(/Users/bwiunbuaa/tmp/oj/buaa_123.in,r,stdin);#endif/*JOBDU_H_*/chardelim[]=,();\,+-*/=?:;//单词分隔符while(gets(input)!=NULL){//首先对input进行预处理，将引号中间的字符都转化为#replaceQuota(input);intbeg_pos=0;do{beg_pos=getWord(input,beg_pos,word);intwlen=strlen(word);//判断是否为指定的关键字if(strcmp(if,word)==0){printf(if:%d\n,beg_pos-wlen+1);//位置以1开始，而不是0，所以要加1}elseif(strcmp(while,word)==0){printf(while