北航保研机试真题（模拟完整版）及详细答案解析

北航保研机试真题（模拟完整版）及详细答案解析本次试题适配北京航空航天大学计算机、软工、人工智能、网安等专业保研机考真实题型难度，总分100分，考试时长120分钟，包含基础填空编程、算法编程大题，贴合历年机考高频考点，代码可直接编译运行，解析通俗易懂、贴合考场解题思路。考试环境：C/C++（主流考场编译器GCC）考点范围：基础语法、字符串处理、数组模拟、贪心算法、动态规划、递归与搜索一、代码填空题（共2题，每题15分，共30分）题目1：整数逆序输出（基础语法）输入一个非负整数，将其数字逆序输出，忽略前导0。例如输入1230，输出321；输入0，输出0。补全下方代码空缺部分，实现功能。cpp

#include<iostream>

usingnamespacestd;

intmain(){

intn;

cin>>n;

intres=0;

while(n>0){

//填空1：拼接逆序数字

res=__________;

//填空2：去掉末尾数字

n=__________;

}

cout<<res<<endl;

return0;

}详细答案与解析填空1答案：res*10+n%10填空2答案：n/10解题思路：这是北航机考必考基础题型，核心是逐位拆解数字。n%10可以取出当前数字的最后一位，res*10是为了给新取出的数字腾出个位位置，实现逆序拼接；n/10整数除法舍去末尾已处理的数字，循环直至所有数字处理完毕。天然规避前导0问题，符合题目要求。完整可运行代码：cpp

#include<iostream>

usingnamespacestd;

intmain(){

intn;

cin>>n;

intres=0;

while(n>0){

res=res*10+n%10;

n=n/10;

}

cout<<res<<endl;

return0;

}题目2：字符串单词统计（字符串处理）输入一行英文句子，单词以空格分隔，统计句子中单词的个数。补全代码，实现该功能（句子无首尾多余空格，无连续空格）。cpp

#include<iostream>

#include<string>

usingnamespacestd;

intmain(){

strings;

//填空1：读取带空格的整行输入

__________;

intcnt=1;

for(inti=0;i<s.size();i++){

//填空2：判断空格，统计单词分隔

if(__________){

cnt++;

}

}

cout<<cnt<<endl;

return0;

}详细答案与解析填空1答案：getline(cin,s)填空2答案：s[i]==''解题思路：cin读取字符串会自动截断空格，因此必须用getline读取整行含空格的输入。题目保证无首尾空格，最少存在1个单词，初始计数设为1，遍历字符串每遇到一个空格，代表新增一个单词，计数累加即可。完整可运行代码：cpp

#include<iostream>

#include<string>

usingnamespacestd;

intmain(){

strings;

getline(cin,s);

intcnt=1;

for(inti=0;i<s.size();i++){

if(s[i]==''){

cnt++;

}

}

cout<<cnt<<endl;

return0;

}二、基础编程大题（共1题，20分）题目：素数筛选统计输入一个正整数N（2≤N≤10000），统计2~N之间所有素数的个数，并从小到大输出所有素数。输入样例：20输出样例：8235711131719详细解题思路采用埃氏筛法解题，效率远高于暴力遍历，是北航机考素数题型的最优解法。核心逻辑：1、初始化标记数组，默认所有数为素数；2、从2开始遍历，将每个素数的所有倍数标记为非素数；3、遍历结束后，未被标记的数即为素数，统计个数并输出。完整AC代码cpp

#include<iostream>

#include<cstring>

usingnamespacestd;

constintMAXN=10005;

boolis_prime[MAXN];

intmain(){

intn;

cin>>n;

//初始化所有数为素数

memset(is_prime,true,sizeof(is_prime));

is_prime[0]=is_prime[1]=false;

//埃氏筛核心逻辑

for(inti=2;i*i<=n;i++){

if(is_prime[i]){

for(intj=i*i;j<=n;j+=i){

is_prime[j]=false;

}

}

}

//统计并输出

intcnt=0;

for(inti=2;i<=n;i++){

if(is_prime[i]){

cnt++;

}

}

cout<<cnt<<endl;

for(inti=2;i<=n;i++){

if(is_prime[i]){

cout<<i<<"";

}

}

cout<<endl;

return0;

}易错点说明（考场重点）1、不要暴力判断每个数是否为素数，N取10000时会超时，不符合机考时间限制；2、必须将0和1手动标记为非素数，避免统计错误；3、筛法遍历起点为i*i，可大幅减少循环次数，优化效率。三、进阶算法大题（共2题，每题25分，共50分）题目1：区间最大子段和（动态规划经典题）给定一个整数数组（包含正数、负数、0），找出其中和最大的连续子数组，输出该最大和。输入描述：第一行输入数组长度n，第二行输入n个整数；输出描述：输出最大子段和；输入样例：9-21-34-121-54输出样例：6解释：最优子段为[4,-1,2,1]，和为6。解题思路采用动态规划经典解法，定义dp[i]为以第i个元素结尾的最大子段和。状态转移方程：dp[i]=max(nums[i],dp[i-1]+nums[i])。即判断是单独取当前元素更大，还是和前面的子段拼接更大。全程记录最大值，最终得到答案。时间复杂度O(n)，完全满足机考数据范围。完整AC代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

constintINF=0x3f3f3f3f;

intmain(){

intn;

cin>>n;

intdp,max_sum=-INF,num;

for(inti=0;i<n;i++){

cin>>num;

if(i==0){

dp=num;

}else{

dp=max(num,dp+num);

}

max_sum=max(max_sum,dp);

}

cout<<max_sum<<endl;

return0;

}考场优化技巧无需开辟完整dp数组，仅用单个变量滚动更新，节省内存空间，代码更简洁高效，是考场得分最优写法，适配所有数据范围。题目2：跳跃游戏（贪心算法）给定一个非负整数数组，数组每个元素代表当前位置可以跳跃的最大长度。初始在数组第一个位置，判断是否能够跳到数组最后一个位置，能则输出Yes，否则输出No。输入样例1：523114输出样例1：Yes输入样例2：532104输出样例2：No解题思路贪心核心：全程维护当前能到达的最远位置。遍历数组每一个位置，若当前位置超出最远可达位置，说明无法到达，直接判定失败；否则更新最远可达位置。遍历过程中若最远位置已经覆盖数组末尾，可提前终止循环，提升效率。完整AC代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

intmain(){

intn;

cin>>n;

intnums[10005];

for(inti=0;i<n;i++){

cin>>nums[i];

}

intmax_reach=0;

for(inti=0;i<n;i++){

//当前位置无法到达，直接退出

if(i>max_reach){

cout<<"No"<<endl;

return0;

}

//更新最远可达位置

max_reach=max(max_reach,i+nums[i]);

//已经可以到达末尾，提前成功

if(max_reach>=n-1){

cout<<"Yes"<<endl;

return0;

}

}

cout<<"No"<<endl;

return0;

}题目考点总结贪心算法是北航保研机考高频考点，相较于搜索、动态规划，代码量更小、运行效率更高，本题重点考察考生对局部最优推全局最优的思维理解，几乎每年机考都会出现同类变形题。四、整套试题评分标准（考场原版）1、代码填空题：逻辑完全正确得满分，语法错误、逻辑错误酌情