保研计算机复试机试真题（含详细答案解析）

保研计算机复试机试真题（含详细答案解析）这套机试题适配985/211计算机、软工、网安专业保研复试考核难度，共4道编程题，涵盖保研机试高频考点：基础模拟、贪心算法、动态规划、字符串处理。题目难度梯度合理，贴合高校真实复试出题风格，代码可直接编译运行，解析通俗易懂，适合复试刷题复盘。考试说明：编程语言不限（本题统一使用C++），无输入输出格式错误、代码运行通过所有测试点即为满分。第一题：整数数位求和（基础模拟·15分）题目描述输入一个不超过10^9的正整数，计算该整数每一位数字的累加和。例如输入123，输出6（1+2+3=6）。输入格式一行一个正整数n输出格式一行一个整数，表示数位累加和样例输入1234样例输出10解题思路本题为基础模拟题，核心思路是逐位拆解数字。通过循环每次取数字的个位（对10取余），将数值累加，再将数字除以10去掉个位，重复操作直至数字变为0，最后输出累加结果。该方法时间复杂度为O(logn)，效率极高，可适配题目最大数据范围。完整代码cpp

#include<iostream>

usingnamespacestd;

intmain(){

intn;

cin>>n;

intsum=0;

while(n>0){

sum+=n%10;

n=n/10;

}

cout<<sum<<endl;

return0;

}答案解析以样例输入1234为例：第一次循环取个位4，sum=4，n变为123；第二次取个位3，sum=7，n变为12；第三次取个位2，sum=9，n变为1；第四次取个位1，sum=10，n变为0，循环结束。最终输出10，与样例结果一致。代码逻辑简洁，无边界问题，可处理所有合法正整数输入。第二题：区间选点问题（贪心算法·25分）题目描述给定n个闭区间[ai,bi]，请选择最少的点，使得每个区间内至少包含一个选中的点。输出最少需要选择的点数。输入格式第一行输入整数n（1≤n≤1000），表示区间个数；接下来n行，每行两个整数ai、bi，表示区间的左右端点（-10^5≤ai≤bi≤10^5）。输出格式一行一个整数，表示最少选点数量样例输入3

13

25

46样例输出2解题思路本题是保研机试经典贪心模板题。最优策略为：将所有区间按照右端点从小到大排序，每次优先选择当前区间的右端点作为选中点，后续所有包含该点的区间都可以直接覆盖，无需重复选点。以此遍历所有区间，统计选点总数即可。该贪心策略可保证局部最优推导出全局最优，是区间选点问题的标准解法。完整代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

//定义区间结构体

structInterval{

intl,r;

};

//按区间右端点升序排序

boolcmp(Intervala,Intervalb){

returna.r<b.r;

}

intmain(){

intn;

cin>>n;

Intervalarr[1005];

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

cin>>arr[i].l>>arr[i].r;

}

sort(arr,arr+n,cmp);

intres=0;

intlast=-1e9;//记录上一个选中的点

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

//当前区间不包含上一个选中的点，更新选点

if(arr[i].l>last){

res++;

last=arr[i].r;

}

}

cout<<res<<endl;

return0;

}答案解析样例三个区间排序后顺序为：[1,3]、[2,5]、[4,6]。第一次选中3，可覆盖前两个区间；第三个区间[4,6]不包含3，再次选中6，总点数为2，与样例输出一致。该解法时间复杂度由排序决定，为O(nlogn)，可轻松应对题目数据范围。第三题：最长上升子序列（动态规划·30分）题目描述给定一个长度为n的整数序列，找出其中最长的严格上升子序列的长度。子序列不要求连续，但必须保持元素相对顺序。输入格式第一行输入整数n（1≤n≤1000），第二行输入n个整数，表示序列元素。输出格式一行一个整数，表示最长严格上升子序列的长度样例输入6

132475样例输出4解题思路本题是动态规划经典必考题型。定义dp[i]表示以第i个元素结尾的最长上升子序列长度。初始状态下，每个元素自身可构成一个长度为1的子序列，因此dp数组初始值全为1。状态转移方程：遍历每个位置i，再遍历i之前的所有位置j，若序列中a[i]>a[j]，说明a[i]可以接在a[j]后形成更长的上升子序列，此时更新dp[i]=max(dp[i],dp[j]+1)。最终dp数组中的最大值即为答案。完整代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

inta[1005];

intdp[1005];

intmain(){

intn;

cin>>n;

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

cin>>a[i];

dp[i]=1;//初始化

}

intans=1;

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

for(intj=0;j<i;j++){

if(a[i]>a[j]){

dp[i]=max(dp[i],dp[j]+1);

}

}

ans=max(ans,dp[i]);

}

cout<<ans<<endl;

return0;

}答案解析样例序列为[1,3,2,4,7,5]，对应的dp数组推演结果为：dp[0]=1、dp[1]=2、dp[2]=2、dp[3]=3、dp[4]=4、dp[5]=4。最大值为4，对应的最长上升子序列为[1,3,4,7]或[1,2,4,7]，长度均为4，符合样例输出。该DP解法思路直白，适合复试基础考核，数据范围内运行稳定。第四题：单词反转（字符串处理·30分）题目描述输入一句英文句子，句子中仅包含小写字母和空格，单词之间用单个空格分隔。要求将句子中的每个单词单独反转，单词相对顺序不变，输出处理后的句子。输入格式一行字符串（长度不超过1000）输出格式一行处理后的字符串样例输入helloworld样例输出ollehdlrow解题思路核心思路：以空格为分隔符，逐个截取句子中的单词，对每个单词进行首尾反转，再将反转后的单词按原顺序拼接，单词之间保留单个空格。具体实现时，通过双指针定位每个单词的起始和结束位置，遍历交换字符完成反转，遍历整句直至所有单词处理完毕。完整代码cpp

#include<iostream>

#include<string>

#include<algorithm>

usingnamespacestd;

intmain(){

strings;

//读取整行字符串（包含空格）

getline(cin,s);

intn=s.size();

intl=0;

for(intr=0;r<=n;r++){

//遇到空格或末尾，反转当前单词

if(s[r]==''||r==n){

reverse(s.begin()+l,s.begin()+r);

l=r+1;

}

}

cout<<s<<endl;

return0;

}答案解析样例输入中第一个单词hello被反转为olleh，第二个单词world被反转为dlrow，单词顺序不变，拼接后输出结果与