北航保研机试真题及详细答案（历年高频原题）

北航保研机试真题及详细答案（历年高频原题）本次整理题目为北航计算机、软院保研（夏令营/预推免）历年高频机试原题，完全贴合真实考试出题风格，考试环境为C/C++，支持STL，每题包含原题题干、解题思路、完整可运行代码、样例解析，适配北航机试评分规则。机试整体特点：侧重基础模拟、字符串处理、简单数学算法、栈队列应用，无复杂高阶算法，重点考察代码熟练度、边界条件处理、细节逻辑。真题一：表达式变量求值（2019/2021年高频原题）一、题干输入一行包含变量的四则运算表达式（仅包含+、-、*、/、括号、小写字母变量），再输入一行按变量首次出现顺序对应的浮点数数值。替换表达式中所有变量并计算结果，最终结果四舍五入保留两位小数。保证表达式合法，除法无除零错误，变量仅由小写字母组成，无重复赋值。二、输入输出样例输入：(a+sb)/(a-sb)10.05.0输出：3.00解释：a=10.0，sb=5.0，代入得(10+5)/(10-5)=3.00三、解题思路1.遍历表达式字符串，提取所有变量名（连续小写字母），按首次出现顺序去重，存储变量列表；2.读取对应浮点数值，建立变量名-数值的映射关系；3.遍历原表达式，将变量逐个替换为对应浮点数，生成纯数字四则运算表达式；4.编写简易表达式求值函数，计算带括号的四则运算结果；5.结果四舍五入保留两位小数输出。核心难点：变量精准提取、表达式合法求值、浮点数精度控制。四、完整代码PlainText

#include<iostream>

#include<string>

#include<stack>

#include<map>

#include<vector>

#include<iomanip>

#include<cctype>

#include<cmath>

usingnamespacestd;

//运算符优先级

intgetPriority(charc){

if(c=='+'||c=='-')return1;

if(c=='*'||c=='/')return2;

return0;

}

//基础运算

doublecalc(doublea,doubleb,charop){

if(op=='+')returna+b;

if(op=='-')returna-b;

if(op=='*')returna*b;

if(op=='/')returna/b;

return0;

}

//表达式求值

doubleevaluate(strings){

stack<double>num;

stack<char>op;

intn=s.size();

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

if(isdigit(s[i])||s[i]=='.'){

//读取浮点数

doubleres=0;

doubledec=0.1;

while(i<n&&(isdigit(s[i])||s[i]=='.')){

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

i++;

while(i<n&&isdigit(s[i])){

res+=(s[i]-'0')*dec;

dec/=10;

i++;

}

}else{

res=res*10+s[i]-'0';

i++;

}

}

num.push(res);

i--;

}elseif(s[i]=='('){

op.push(s[i]);

}elseif(s[i]==')'){

while(op.top()!='('){

doubleb=num.top();num.pop();

doublea=num.top();num.pop();

charo=op.top();op.pop();

num.push(calc(a,b,o));

}

op.pop();

}else{

while(!op.empty()&&getPriority(op.top())>=getPriority(s[i])){

doubleb=num.top();num.pop();

doublea=num.top();num.pop();

charo=op.top();op.pop();

num.push(calc(a,b,o));

}

op.push(s[i]);

}

}

//处理剩余运算符

while(!op.empty()){

doubleb=num.top();num.pop();

doublea=num.top();num.pop();

charo=op.top();op.pop();

num.push(calc(a,b,o));

}

returnnum.top();

}

intmain(){

stringexp;

getline(cin,exp);

vector<string>vars;

map<string,double>mp;

intlen=exp.size();

//提取所有变量（连续小写字母）

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

if(islower(exp[i])){

stringtmp;

while(i<len&&islower(exp[i])){

tmp+=exp[i];

i++;

}

//去重

boolflag=true;

for(auto&s:vars){

if(s==tmp){

flag=false;

break;

}

}

if(flag)vars.push_back(tmp);

i--;

}

}

//读取变量数值

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

doublex;

cin>>x;

mp[vars[i]]=x;

}

//变量替换

stringnewExp;

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

if(islower(exp[i])){

stringtmp;

while(i<len&&islower(exp[i])){

tmp+=exp[i];

i++;

}

newExp+=to_string(mp[tmp]);

i--;

}else{

newExp+=exp[i];

}

}

//计算并保留两位小数

doubleans=evaluate(newExp);

cout<<fixed<<setprecision(2)<<ans<<endl;

return0;

}真题二：窗口层级模拟（2019预推免原题）一、题干电脑窗口存在层级顺序，自顶向下为显示优先级，现有四种操作：1.addx：添加编号为x的窗口，默认置于最顶层；2.delx：删除编号为x的窗口；3.activex：激活编号为x的窗口，将其移动至最顶层；4.undo：撤销上一步有效操作（仅撤销add/del/active，连续undo可多次撤销）。给定操作次数n，以及n条操作指令，输出最终自顶向下的窗口编号序列。窗口编号为整数，所有操作合法，不存在删除/激活不存在窗口的情况。二、输入输出样例输入：6add1add2active1add3undodel2输出：1解释：撤销add3操作，删除窗口2，最终仅剩窗口1，顶层为1。三、解题思路1.用vector存储当前窗口层级（首位为顶层，末尾为底层）；2.用栈记录每一步有效操作的历史状态，用于undo撤销；3.对应操作逻辑：-addx：尾部插入x，记录操作状态；-activex：删除原有x，头部插入x，记录状态；-delx：删除x，记录状态；-undo：取出栈中上一步状态，恢复窗口序列；4.遍历结束后，按顺序输出窗口序列。四、完整代码PlainText

#include<iostream>

#include<vector>

#include<stack>

#include<string>

#include<algorithm>

usingnamespacestd;

//保存每一步操作后的窗口状态

vector<int>win;

stack<vector<int>>st;

intmain(){

intn;

cin>>n;

while(n--){

stringop;

cin>>op;

if(op=="add"){

intx;

cin>>x;

st.push(win);

win.push_back(x);

}elseif(op=="del"){

intx;

cin>>x;

st.push(win);

for(autoit=win.begin();it!=win.end();it++){

if(*it==x){

win.erase(it);

break;

}

}

}elseif(op=="active"){

intx;

cin>>x;

st.push(win);

for(autoit=win.begin();it!=win.end();it++){

if(*it==x){

win.erase(it);

break;

}

}

win.insert(win.begin(),x);

}elseif(op=="undo"){

if(!st.empty()){

win=st.top();

st.pop();

}

}

}

//输出最终窗口序列

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

if(i>0)cout<<"";

cout<<win[i];

}

cout<<endl;

return0;

}真题三：整数幂次分解（2025年机试原题）一、题干给定一个正整数N（2≤N≤1e9），判断N是否可以分解为N=b若存在多种分解方式，选择k最小的一组输出；若无法分解，输出no。二、输入输出样例样例1：输入16，输出24（24样例2：输入12，输出no样例3：输入64，输出26三、解题思路1.k的取值范围：最小为2，最大为log2(N)（N最小为2，最大幂次不超过30，遍历范围极小）；2.为满足k最小优先，从k=2开始从小到大遍历；3.对每个k，二分查找整数b，使得bk4.找到第一个合法的b、k直接输出，全部遍历无结果则输出no。核心优化：幂次遍历范围小，二分查找高效，规避暴力枚举超时，同时防止整型溢出。四、完整代码PlainText

#include<iostream>

#include<cmath>

usingnamespacestd;

typedeflonglongll;

//计算b^k，溢出返回-1

llpowCheck(llb,intk,lln){

llres=1;

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

res*=b;

if(res>n)return-1;

}

re