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

北京航空航天大学计算机系考研复试 06-14上机真题及答案

复试上机指导
1. 本真题只是提供辅助作用，关键还是研友平时动手能力练习和对算法、数据结构的理解，参加过ACM的有一定优势 没参加过的也不用紧张，北航的上机题相对于清华和北大，难度上小很多，多练习的话，问题不大;
2. 上机时，可以快速阅读所有的题目，按照从易到难的次序做题，保证会的一定得分;
3. 熟悉编程环境，熟悉c的常用函数;
4. 为了快速测试代码的正确性，尤其是矩阵输入的情况，可以利用标准输入重定向，freopen(“c:\\input.txt”,”r”,stdin);加快测试过程;
5. 注意程序边界条件的测试;
6. 如果你有什么疑问，或者我们提供的材料有问题，欢迎联系我们：bwiunbuaa@ 提供北航计算机报考和选导师指导，或者到 给我们留言。

14年上机题
第一题，阶乘数。输入一个正整数，输出时，先输出这个数本身，跟着一个逗号，再输出这个数的各位数字的阶乘和，等号，阶乘和的计算结果，并判断阶乘和是否等于原数，如果相等输出Yes，否则输出No。题目说明输入的正整数以及其各位阶乘和都不会超出int型的表示范围。

输入样例1：
       145

输出样例1：
       145,1!+4!+5!=145
       Yes

输入样例2：
       1400

输出样例2：
       1400,1!+4!+0!+0!=27
       No

第二题，五子棋。输入一个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.23456e2

12年上机题
1.【问题描述】
某些整数能分解成若干个连续整数的和的形式，例如
15 = 1 + 2＋3＋4＋5　
15 = 4 + 5 + 6
15 = 7 + 8
某些整数不能分解为连续整数的和，例如：16
输入：一个整数N（N <= 10000）
输出整数N对应的所有分解组合，按照每个分解中的最小整数从小到大输出，每个分解占一行，每个数字之间有一个空格（每行最后保留一个空格）；如果没有任何分解组合，则输出NONE。
解题思路：
根据题目，任何可以进行分解的整数，必然满足(m+n)(n-m+1)/2的形式，可以暴力尝试所有m和n组合，如果满足则输出，否则输出None。
代码：
#include
#include

int main(){
int n;
while(scanf("%d",&n) != EOF){
int begin,end;
int found = 0
for(begin=1;beginfound == 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维方阵
输出：
小岛面积
样例输入：
6
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
样例输出：
8
解题思路：
理解题目本身意思，可以发现对于矩阵中的0是否属于内陆，取决于该0所处的行和列上，如果0满足，如下条件则O为内陆，否则不是。
Ø 0所在的行，0的左边和右边必须有1
Ø 0所在的列，0的上面和下面必须有1
所以，解题思路就是，遍历所有的行和列，记录改行或列，最左面和最右面（或者最上面和最下面）1的坐标，然后当遇到0，判断是否处于记录的值的中间，是，则是内陆，面积加1，否则不加。
代码：
#include
#include

#define DEBUG_BUAA_122

int main(){
int N; //矩阵维数
int island[100][100]; //输入岛数据的方阵
int data[100][4];

#ifdef DEBUG_BUAA_122
freopen("/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;i data[i][0] = j;
}
if(data[j][2] == -1){
data[j][2] = i;
}
data[i][1] = j;
data[j][3] = i;
}
}
}
int area = 0;
for(i=0;i data[j][2] && i < data[j][3] && j > data[i][0] && j < data[i][1]){
area++;
//printf("i=%d,j=%d\n",i,j); for debug
}
}
}
}
printf("%d\n",area);
}
return 0;
}

3.【问题描述】
统计关键字出现位置
输入：
一行标准c语言代码（字符个数小于300），统计出该字符串中关键字的if，while，for所在的位置，按照关键字出现的顺序依次输出。注意双引号内的不需要统计。
输入：一行标准c语言代码，字符个数小于300
输出：
关键字if，while，for对应的位置，按照关键字出现的顺序依次输出。输出格式为：关键字，后跟冒号，然后是出现的位置。扫描到关键字就输出，每个输出占一行。
样例输入：
#include int main() {int i = 0; if(i == 0) printf("YES"); return 0;}
#include int main() {int ifwhile = 0; int forif = 1;char if_for_while = 'a';char *str = "while"; while(ifwhile == 0) {ifwhile = 1forif = 0;} if(forif == 0) {if_for_while = 'b';} if(ifwhile == 1) {if_for_while = 'c';} return 0;}
样例输出：
if:43
while:88
if:133
if:170
解题思路：
首先把输入字符串切分为一个个的单词，然后对每个单词进行匹配。注意c语言中的strtok函数，不能够返回位置（当分隔符连续时，比如+=,计算出前导的分割符有几个），所以不能满足本题的要求，必须自己写获取单词的函数（反正也不复杂啦）。因为考虑到引号的问题，我们的解决方案是首先对输入字符串进行预处理，将“”内的每个字符都替换为#，然后再进行单词分割（切词），最后进行匹配。具体步骤：
Ø 输入源码字符串预处理，将””内的每个字符替换为#
Ø 一次获取源码中的单词，看是否为查找的关键词，如果是则输出
代码：
#include
#include
#include

#define DEBUG_BUAA_123
#define MAX_WORD_LEN 128
#define MAX_LEN 300
#define KW_NUM 3

/**
* 将一段源代码中间的，位于双引号“”的以#代替
*/
void replaceQuota(char buf[]){
int i;
int len = strlen(buf);
int quotaL = 0,quotaR = 0;
for(i=0;i }
}
}
}

// 判断字符是否为分隔符
int isdelim(char ch){
switch(ch){
case ' ':
case '=':
case ',':
case ';':
case '<':
case '>':
case '(':
case ')':
case '{':
case '}':return 1;
default:return 0;
}
}

/**
* 从input数组下标pos处开始一个单词,返回的单词放在word数组中
* 返回下次查找开始的位置
*/
int getWord(char input[],int pos,char word[]){
int len = strlen(input);
int i;
int isbegin = 0;
int wpos = 0;
for(i=pos;iord[wpos++] = input[i];
}
}
word[wpos]='\0'; //结束标志，勿忘，切记
return (i>=len) ? -1:i; //如果到文件结尾了，返回-1
}

int main(){
char input[300];
char word[MAX_WORD_LEN];

#ifdef DEBUG_BUAA_123
freopen("/Users/bwiunbuaa/tmp/oj/buaa_123.in", "r", stdin);
#endif /* JOBDU_H_ */

char delim[] = " ,();\",+-*/=<>?:"; //单词分隔符

while(gets(input) != NULL){
//首先对input进行预处理，将引号中间的字符都转化为#
replaceQuota(input);
int beg_pos = 0;
do
{
beg_pos = getWord(input,beg_pos,word);
int wlen = strlen(word);
//判断是否为指定的关键字
if(strcmp("if",word) == 0){
printf("if:%d\n",beg_pos-wlen+1);//位置以1开始，而不是0，所以要加1
}
else if(strcmp("while",word) == 0){
printf("while:%d\n",beg_pos-wlen+1);
}
else if(strcmp("for",word) == 0){
printf("for:%d\n",beg_pos-wlen+1);
}
}while(beg_pos >= 0);
}
return 0;
}

11年上机题
1. 【问题描述】
孪生数定义： 如果 A 的约数（因数包含1，但不包含A本身）之和等于 B ， B 的约数（因数）之和等于 A ， A 和 B 称为孪生数（A和B不相等）。试找出正整数 M 和 N 之间的孪生数。
输入：
从控制台输入两个正整数M和N（1<=M例说明
样例1输入的区间为[20,300]，其间有一对孪生数对，即：220（1+2+4+5+10+11+20+22+44+55+110=284）和284（1+2+4+71+142=220）。样例2输入的区间是[200,250]，其间没有孪生数对，所以输出字符串：NONE。
评分标准
该题要求输出区间中的所有孪生数对，共有5个测试点，提交程序文件名为example1.c或example1.cpp。
解题思路：
这题目很简单，比较每对数的约数和，看是否满足条件，如果满足则输出。
代码：
#include
#include

//计算x约数的和
int yinzisum(int x)
{
int i=1,sum=0;
if(x == 1) return 0;
while(i y){
max=x;
min=y;
}else{
max=y;
min=x;
}
int* array=(int*)malloc(sizeof(int)*(max-min+1));
for(i=0;i
}

2. 【问题描述】
先输入两个矩阵A和B，然后输入替换位置（左上角），编写程序将矩阵A中从替换位置开始的子矩阵（与B同样大小）替换为B，并输出替换后的矩阵。
【输入形式】
从控制台先输入矩阵A的行数和列数（行数和列数均大于等于1，小于等于20），然后在新的行上输入矩阵A的各行数字（以一个空格分隔的整数）。再以同样的方式输入矩阵B。最后输入替换位置（用一个空格分隔的两个整数表示，行数和列数都从1开始计数，因此两个整数都大于等于1）。若替换位置超出了矩阵A的行数或列数，则原样输出矩阵A。
【输出形式】
在标准输出上分行输出替换后的矩阵，每行中各数字之间以一个空格分隔。

【输入样例1】
5 6
10 2 34 -1 800 90
2 76 56 -200 23 1
35 0 0 98 8 3000
2000 100 -1 1 2 0
8 7 85 963 496 8
2 3
9 9 9
9 9 9
3 3
【输出样例1】
10 2 34 -1 800 90
2 76 56 -200 23 1
35 0 9 9 9 3000
2000 100 9 9 9 0
8 7 85 963 496 8
【样例1说明】
输入的矩阵A为5行6列，矩阵B是2行3列，替换位置为第3行的第3列，即：将A中第3行第3列开始的、行数为2列数为3的子矩阵替换为B。
【输入样例2】
3 4
10 2 34 -1
2 76 56 -200
35 0 0 98
2 3
9 9 9
9 9 9
2 3
【输出样例2】
10 2 34 -1
2 76 9 9
35 0 9 9
【样例2说明】
输入的矩阵A为3行4列，矩阵B是2行3列，替换位置为第2行的第3列，即：将A中第2行第3列开始的、行数为2列数为3的子矩阵替换为B。但该子矩阵超出了A的范围，所以只实现了部分替换。
【评分标准】
该题要求输出替换后的矩阵，共有5个测试点，提交程序文件名为example2.c或example2.cpp。
解题思路：
很简单,略。
代码：
#include
#include

void main ()
{
int x0,y0,i,j,x1,y1,x2,y2;

printf("输入矩阵行列数[行,列]:");
scanf("%d%d",&x0,&y0);
int** array0=(int**)malloc(sizeof(int*)*x0);
for(i=0;i)
scanf("%d",&array0[i][j]);

printf("输入矩阵行列数[行,列]:");
scanf("%d%d",&x1,&y1);
int** array1=(int**)malloc(sizeof(int*)*x1);
for(i=0;icanf("%d%d",&x2,&y2);
for(i=0;i只处理[a-z]、[A-Z]、[0-9]范围内的字符扩展，即只有当扩展符前后的字符同时是小写字母、大写字母或数字时才进行扩展，其它情况不进行扩展，原样输出。例如：a-R、D-e、0-b、4-B等字符串都不进行扩展。
【输入形式】
从键盘输入包含扩展符的字符串
【输出形式】
输出扩展后的字符串
【输入样例1】
ADEa-g-m02
【输出样例1】
ADEabcdefghijklm02
【输入样例2】
cdeT-bcd
【输出样例2】
cdeT-bcd
【样例说明】
将样例1的输入ADEa-g-m02扩展为：ADEabcdefghijklm02；样例2的输入cdeT-bcd中，扩展符前的字符为大写字母，扩展符后的字符为小写字母，不在同一范围内，所以不进行扩展。
【评分标准】
结果完全正确得15分，共5个测试点，每个测试点3分，提交程序文件expand.c或expand.cpp。

解题思路：
很简单，略。
代码：
#include
#include

int getindex(char ch)
{
int index=-1;
if(ch>='a' && ch<='z')
index=0;
else if(ch>='0' && ch<='9')
index=1;
else if(ch>='A' && ch<='Z')
index=2;
return index;
}

int main()
{
char str[300],ch;
ch=getchar();
int i=0,j;
while(ch!='\n')
{
str[i]=ch;
ch=getchar();
i++;
}
str[i]='\0';
for(i=0;str[i]!='\0';i++)
if(str[i]=='-')
{
if(getindex(str[i-1])==getindex(str[i+1]) && getindex(str[i-1])!=-1)
{
ch=str[i-1]+1;
while(ch重复字符（数据结构上做过N遍的Merge函数）
#include
#include

void main()
{
char str0[200],str1[200],str[400],ch;
ch=getchar();
int i=0,j,k;
while(ch!='\n')
{
str0[i]=ch;
ch=getchar();
i++;
}
str0[i]='\0';
i=0;
ch=getchar();
while(ch!='\n')
{
str1[i]=ch;
ch=getchar();
i++;
}
str1[i]='\0';
i=j=k=0;
while(str0[i]!='\0' && str1[j]!='\0')
{
if(str0[i]str1[j])
if(str1[j]==str[k-1])
j++;
else
{
str[k]=str1[j];
j++;
k++;
}
else
if(str0[i]==str[k-1])
{
i++;
j++;
}
else
{
str[k]=str0[i];
i++;
j++;
k++;
}
}
if(str0[i]=='\0'){
while(str1[j]!='\0'){
if(str1[j]!=str[k-1])
str[k++]=str1[j++];
else
j+
}

}
else{
while(str0[i]!='\0')
if(str0[i]!=str[k-1])
str[k++]=str0[i++];
else
i++;
}

int length = strlen(str);
for(i=0;i
#include ib.h>

void main()
{
int n,i,ii,j,k,l;
scanf("%d",&n);
int* array0=(int*)malloc(sizeof(int)*n);
for(i=0;irray0[i]==array0[ii])
j++;
for(k=0;k输入x n。
输出：
迭代n次后的立方根，double精度,保留小数点后面六位。
样例输入：
3000000 28
样例输出：
144.224957
代码：
#include
#include

int buaa_func_091()
{
double x,y;
int i,n;
while(scanf("%lf%d",&x,&n) != EOF)
{
y=x;
for(i=1;i<=n;i++)
y=y*2/3+x/(3*y*y);
printf("%.6f\n",y);
}
return 0;
}

2、数组排序
输入一个数组的值,求出各个值从小到大排序后的次序。
输入:输入的第一个数为数组的长度,后面的数为数组中的值,以空格分割
输出:各输入的值按从小到大排列的次序。
sample
input:
4
-3 75 12 -3
output:
1 3 2 1
代码：
#include
# define N 10000
int del(int a[],int n);
int bubblesort(int a[],int n);
int locate(int a[],int b,int n);
int main()
{
int a[N],b[N],i,j,n,num,z;
while(scanf("%d",&n)!=EOF)
{
for(i=0;iort(a,n);
num=del(a,n);
for(z=0;zj }
i++;
j=i;
n=n-k;
}
}
if(a[n-2]==a[n-1])
n--;
return n;
}
int bubblesort(int a[],int n)
{
int i,j,temp;
for(i=0;ia[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
return 0;
}
int locate(int a[],int b,int n)
{
int i,j,k;
for(i=0;i