历年复试上机题
2000年北理复试上机题
2001年北理复试上机题(A)
4、N 个人围成一圈顺序编号，从 1 号开始按 1、2、 3 顺序报数，报 3 者退出圈外，其余的人再从 1、2、 3 开始报数，报 3 的人再退出圈外，依次类推。请按退出顺序输出每个退出人的原序号。要求使用环形链表编程。
#include <iostream>
using namespace std;
// 定义一个结构体 p，用于构建链表节点
struct p
{
int num; // 存储一个数字
p *next; // 指向下一个节点的指针
};
int main()
{
p *head, *h, *t; // 定义链表头指针 head，当前节点指针 h，尾节点指针 t
int i, n;
cin >> n; // 从标准输入读取一个整数 n
h = new p; // 创建第一个节点，并将其地址赋给 h
h->num = 1; // 设置第一个节点的 num 为 1
head = h; // 将链表头指针指向第一个节点
h->next = NULL; // 将第一个节点的下一个节点指针设置为 NULL
// 创建链表的其余部分，包括数字从 2 到 n 的节点
for (i = 2; i <= n; i++)
{
t = new p; // 创建一个新的节点
t->num = i; // 设置新节点的 num 为当前数字 i
h->next = t; // 将当前节点的下一个节点指针指向新节点
h = t; // 将当前节点指针移动到新节点
h->next = NULL; // 将新节点的下一个节点指针设置为 NULL
}
// 将链表首尾相连，形成一个循环链表
h->next = head;
h = head;
i = 2; // 初始化计数器 i 为 2
h = h->next; // 将当前节点指针 h 移动到下一个节点
cout << "出队序列为：" << endl;
// 循环处理链表中的节点，直到链表为空
while (n != 0)
{
if (i % 3 == 0) // 每隔三个节点执行一次操作
{
cout << h->num << " "; // 输出当前节点的数字
head->next = h->next; // 调整链表，将当前节点从链表中删除
h = head->next; // 将当前节点指针移动到下一个节点
n--; // 减少剩余节点数量
i = 1; // 重置计数器为 1
}
i++; // 增加计数器
head = h; // 更新链表头指针
h = h->next; // 将当前节点指针移动到下一个节点
}
cout << endl;
return 0;
}
2001年北理复试上机题(B)
2002年北理复试上机题(A)
2、输入 n 值，使用递归函数，求杨辉三角形中各个位置上的值，按照如下形式打印输出图形。例如：当n=6 时。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
#include<iostream>
using namespace std;
int fun(int i,int j){
if(j==0||j==i)
return 1;
else
return fun(i-1,j-1)+fun(i-1,j);
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
for(int k=0;k<n-i-1;k++)
cout<<" ";
for(int j=0;j<=i;j++){
cout<<fun(i,j)<<" ";
}
cout<<endl;
}
return 0;
}
3、打印所有不超过 n（n<256）的，其平方具有对称性质的数。如 11*11=121。
#include<iostream>
using namespace std;
int main()
{
int n,i,num,temp,m;
n=256;
for(i=1;i<256;i++)
{
num=i*i;
m=0;
while(num>0)
{
temp=num%10; //取最后一位
m=temp+m*10;
num=num/10;
}
if(m==i*i)
{
cout<<i<<" ";
}
}
return 0;
}
4、编写一个求菲波那奇数列的递归函数，输入 n值，使用该递归函数，输出如下图形。例如：当n=6时
0
0 1 1
0 1 1 2 3
0 1 1 2 3 5 8
0 1 1 2 3 5 8 13 21
0 1 1 2 3 5 8 13 21 34 55
#include <iostream>
using namespace std;
int fib(int n) {
if(n == 0) return 0;
else if(n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
int main() {
int n;
while(cin >> n) {
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
cout << " ";
}
for(int j = 0; j < 2 * i + 1; j++) {
cout << fib(j) << " ";
}
cout << endl;
}
}
return 0;
}
2002年北理复试上机题(B)
2003年北理复试上机题
3、输入年月日，计算该天是本年的第几天。例如1990 年 9 月 20 日是 1990 年的第 263 天，2000年 5 月 1 日是 2000 年第 122 天。
（闰年：能被 400整除，或能被 4 整除但不能被 100 整除。每年 1、3、5、7、8、10 为大月）
#include <iostream>
using namespace std;
int main() {
int year, month, day;
cout << "请输入年月日，空格隔开：" << endl;
while(cin >> year >> month >> day) {
int sum = 0;
if(year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) {
switch (month) {
case 1 : sum += 0;break;
case 2 : sum += 31;break;
case 3 : sum += 60;break;
case 4 : sum += 91;break;
case 5 : sum += 121;break;
case 6 : sum += 152;break;
case 7 : sum += 182;break;
case 8 : sum += 213;break;
case 9 : sum += 244;break;
case 10 : sum += 274;break;
case 11 : sum += 305;break;
case 12 : sum += 335;break;
}
sum += day;
}
else {
switch (month) {
case 1 : sum += 0;break;
case 2 : sum += 31;break;
case 3 : sum += 59;break;
case 4 : sum += 90;break;
case 5 : sum += 120;break;
case 6 : sum += 151;break;
case 7 : sum += 181;break;
case 8 : sum += 212;break;
case 9 : sum += 243;break;
case 10 : sum += 273;break;
case 11 : sum += 304;break;
case 12 : sum += 334;break;
}
sum += day;
}
cout << year << "年" << month << "月" << day << "日是" << year << "年的第" << sum << "天" << endl;
}
return 0;
}
2004年北理复试上机题
3、实现一个多项式的类（a+b_x+c_x2+d*x3+...+），要求输入该多项式的系数和x的值后打印出这个多项式的值。
输入:
第一行为多项式最高项次数n，接下来n+1个整数表示每项系数，最后一个整数x，n不超过10。
输出:
多项式代入x后的值。
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
class formula
{
public:
vector<double> v;
int n;
double x;
double fun(int n, int N, double x, vector<double> v) {
if(n == 0) {
return v[N];
}
else {
return fun(n - 1, N, x, v) * x + v[N-n];
}
}
void show(){
cout << fun(n, n, x, v) << endl;
}
};
int main() {
int n;
while (cin >> n) {
vector<double> v(n + 1);
double x;
for(int i = 0; i <= n; i++) cin >> v[i];
cin >> x;
formula f;
f.n = n;
f.v = v;
f.x = x;
f.show();
}
return 0;
}
2005年北理复试上机题
2、编写一个日期类，要求按xxxx-xx-xx 的格式输出日期，实现加一天的操作。
输入: 3个用空格隔开的整数，分别表示年月日。测试数据不会有闰年。
输出: 按xxxx-xx-xx的格式输出，表示输入日期的后一天的日期。
#include <iostream>
using namespace std;
class date
{
public:
int day, month, year;
void show() {
if(day == 28 && month == 2) {
day = 1;
month++;
}
else if(day == 30 && (month == 4 || month == 6 || month == 9 || month == 11)) {
day = 1;
month++;
}
else if(day == 31 && (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12)) {
day = 1;
month++;
}
else day++;
if(month == 13) {
month = 1;
year++;
}
cout << year << "-" << month << "-" << day << endl;
}
};
int main() {
int y, m, d;
while(cin >> y >> m >> d) {
date dd;
dd.year = y;
dd.month = m;
dd.day = d;
dd.show();
}
return 0;
}
2006年北理复试上机题
2007年北理复试上机题
2008年北理复试上机题
2、输入文件名及路径创建该文件，并把从键盘输入的内容保存到该文件，最后将该文件的路径、该文件名及文件中的内容输出到屏幕。
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main()
{
string filename,add,address;
char text[100];
cout<<"请输入文件名"<<endl;
cin>>filename;
cout<<"请输入文件路径"<<endl;
cin>>add;
getchar();
address+=add;
address+="/";
address+=filename;
FILE *fp;
if(!(fp=fopen(address.c_str(),"w")))
cout<<"打开失败"<<endl;
cout<<"请输入内容"<<endl;
while(1)
{
gets(text);
if(strcmp(text,"#")==0)
break;
fprintf(fp,text);
fprintf(fp,"\n");
}
fclose(fp);
cout<<"文件地址："<<add<<" 文件名"<<filename<<endl;
cout<<"文件内容:"<<endl;
if(!(fp=fopen(address.c_str(),"r")))
cout<<"打开失败"<<endl;
while(fgets(text,200,fp)!=NULL)
{
cout<<text;
}
fclose(fp);
return 0;
}
fopen(address.c_str(), "w")
fopen(address.c_str(), "w") 是 C/C++ 标准库中的函数调用，用于打开一个文件以供写入。这个函数通常用于创建一个新文件或清空已存在的文件，并将数据写入到文件中。
让我们分解这个函数调用：
address.c_str()：address是一个 C++ 的std::string对象，表示文件的路径和名称。.c_str()是std::string类的成员函数，用于将std::string对象转换为 C 风格的字符串（以 null 结尾的字符数组），以便传递给fopen函数。"w"：这是fopen函数的第二个参数，表示文件的打开模式。在这里，使用 "w" 模式表示以写入方式打开文件。如果文件不存在，它会尝试创建文件；如果文件已经存在，它会截断（清空）文件内容，并允许写入新数据。
3、设计捕获两种不同类型的异常，一个是被0除，另一个是数组越界。
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
cout<<"请输入除数和被除数\n"<<endl;
int a,b;
cin>>a>>b;
try
{
if(b==0)
throw "除数为空\n";
else
{
cout<<a/b<<endl;
}
cout<<"\n请输入数组长度\n";
int n;
cin>>n;
cout<<"请输入要访问的数组下标\n"<<endl;
cin>>a;
if(a>=n||a<0)
throw "非法访问\n";
}
catch(char *e)
{
cout<<e<<endl;
}
}
4、设计一个程序能计算日期的间隔，如输入两个日期分别为2008-2-3和2008-3-9计算相隔多少天，或2008-2-3加上100天后的日期是多少。
#include <cstdio>
#include <algorithm>
using namespace std;
bool IsRunnian(int year)
{
if(year%4==0 && year%100!=0|| year%400==0)
return true;
return false;
}
typedef struct
{
int year;
int month;
int day;
}date;
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int judge(date d1,date d2) //d1大返回1，相等返回0，d2大返回-1
{
if(d1.year>d2.year)
return 1;
if(d1.year<d2.year)
return -1;
if(d1.month>d2.month)
return 1;
if(d1.month<d2.month)
return -1;
if(d1.day>d2.day)
return 1;
if(d1.day<d2.day)
return -1;
return 0;
}
int getday(date d1,date d2)
{
int day=0;
if(judge(d1,d2)==1)
swap(d1,d2);
for(;d1.year!=d2.year;d1.year++)
{
if(IsRunnian(d1.year)&& d1.month<=3)
day+=366;
else
day+=365;
}
if(IsRunnian(d1.year))
month[2]=29;
else
month[2]=28;
if(d1.month>d2.month)
{
for(;d2.month!=d1.month;d2.month++)
{
day-=month[d2.month];
}
}
if(d1.month<d2.month)
{
for(;d1.month!=d2.month;d1.month++)
{
day+=month[d1.month];
}
}
day+=(d2.day-d1.day);
return day;
}
void getday(date &d1,int d)
{
if(IsRunnian(d1.year))
month[2]=29;
else
month[2]=28;
while(d>0)
{
if(d>=month[d1.month])
{
d-=month[d1.month];
d1.month++;
if(d1.month>12)
{
d1.month=1;
d1.year++;
if(IsRunnian(d1.year))
month[2]=29;
else
month[2]=28;
}
if(d1.day>month[d1.month])
{
d+=(d1.day-month[d1.month]);
d1.day=month[d1.month];
}
}
else
{
d--;
d1.day++;
if(d1.day>month[d1.month])
{
d1.month++;
d1.day=1;
}
if(d1.month>12)
{
d1.year++;
d1.month=1;
}
}
}
}
int main()
{
int choose;
date d1,d2;
while(1)
{
printf("1,计算间隔。2、计算日期。3、退出\n");
scanf("%d",&choose);
if(choose==1)
{
printf("请输入两个日期\n");
scanf("%d-%d-%d",&d1.year,&d1.month,&d1.day);
scanf("%d-%d-%d",&d2.year,&d2.month,&d2.day);
printf("%d\n",getday(d1,d2));
}
if(choose==2)
{
printf("请输入时间和间隔日期,例如2018-1-1+100\n");
int d;
char c;
scanf("%d-%d-%d%c%d",&d1.year,&d1.month,&d1.day,&c,&d);
getday(d1,d);
printf("%d-%d-%d\n",d1.year,d1.month,d1.day);
}
}
}
#include<bits/stdc++.h>
#include<algorithm>
# define ISRUN(x) ((x % 400 == 0)||(x % 100 != 0 && x % 4 == 0))? 1 : 0
using namespace std;
int mons[13][2] ={
0,0,
31,31,
28,29,
31,31,
30,30,
31,31,
30,30,
31,31,
31,31,
30,30,
31,31,
30,30,
31,31
};
struct Date{
int year;
int month;
int day;
Date addDate(Date date){
Date d1 = date;
if(date.day == mons[date.month][ISRUN(date.year)]){
if(date.month == 12){
d1.year++;
d1.month = 1;
}else{
d1.month++;
}
d1.day = 1;
}else{
d1.day++;
}
return d1;
};
};
int jisuanjiange(Date date){
Date d0;
d0.year = 0;
d0.month = 1;
d0.day = 1;
int jsq = 0;
while(d0.year != date.year || d0.month != date.month || d0.day != date.day){
jsq++;
d0 = d0.addDate(d0);
}
return jsq;
}
Date getday(Date date, int days){
for(int i = 0; i < days; i++){
date = date.addDate(date);
}
return date;
}
int main(){
int choose;
Date d1, d2;
while(1){
printf("1,计算间隔。2、计算日期。3、退出\n");
scanf("%d",&choose);
if(choose==1)
{
printf("请输入两个日期\n");
scanf("%d-%d-%d",&d1.year,&d1.month,&d1.day);
scanf("%d-%d-%d",&d2.year,&d2.month,&d2.day);
printf("%d\n", abs(jisuanjiange(d1)- jisuanjiange(d2)));
}
if(choose==2)
{
printf("请输入时间和间隔日期,例如2018-1-1+100\n");
int d;
char c;
scanf("%d-%d-%d%c%d",&d1.year,&d1.month,&d1.day,&c,&d);
d1 = getday(d1,d);
printf("%d-%d-%d\n",d1.year,d1.month,d1.day);
}
if(choose==3){
break;
}
}
return 0;
}
2009年北理复试上机题
1、请输入字符串，最多输入4 个字符串，要求后输入的字符串排在前面，例如
输入：EricZ
输出：1=EricZ
输入：David
输出：1=David 2=EricZ
输入：Peter
输出：1=Peter 2=David 3=EricZ
输入：Alan
输出：1=Alan 2=Peter 3=David 4=EricZ
输入：Jane
输出：1=Jane 2=Alan 3=Peter 4=David
2、把上述最后结果保存到Name.txt中;
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main() {
vector<string> v;
string s;
ofstream outfile;
outfile.open("Name.txt");
while(cin >> s) {
outfile << s << endl;
v.push_back(s);
if(v.size() > 4) v.erase(v.begin());
int num = 1;
for(int i = v.size() - 1; i >= 0; i--) {
cout << num++ << "=" << v[i] << " ";
outfile << num - 1 << "=" << v[i] << " ";
}
cout << endl;
outfile << endl;
}
outfile.close();
return 0;
}
4、输入一个英文句子，把句子中的单词按出现次数按从多到少把单词和次数在屏幕上输出来，要求能识别英文句号和逗号，暂不要求识别其他符号。
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
map<string, int> mm;
bool cmp(string s1, string s2) {
return mm[s1] > mm[s2];
}
int main() {
string s;
while (getline(cin, s)) {
string str;
vector<string> v;
for (int i = 0; i <= s.length(); i++) {
if (i == s.length() || s[i] == ' ' || s[i] == ',' || s[i] == '.') {
if (str != "") {
mm[str]++;
v.push_back(str);
str = "";
}
}
else
str += tolower(s[i]);
}
sort(v.begin(), v.end(), cmp);
map<string, int> op;
for (auto it = v.begin(); it != v.end(); it++) {
op[*it]++;
if(op[*it] > 1) continue;
cout << *it << " " << mm[*it] << endl;
}
}
return 0;
}
2010年北理复试上机题
1．输入一串整数，输入命令排序！
输入 a t 在这串整数后面添加整数 t，
输入 c\m\n 有 n 替换 m，
输入 d t 删除 t，
输入 s 排序。
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
// int tonum(string s, int l) {
// int n = 1, sum = 0;
// for(int i = l - 1; i > 1; i--) {
// sum += (s[i] - '0') * n;
// n *= 10;
// }
// return sum;
// }
int main() {
int n;
vector<int> v;
while(cin >> n) {
v.push_back(n);
if(getchar() == '\n') {
string s;
while (getline(cin, s)) {
if (s[0] == 'a') {
s = s.erase(0, 1);
v.push_back(atoi(s.c_str()));
for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
cout << endl;
}
if (s[0] == 'c') {
string s1, s2;
int cnt = 0, num1, num2, temp;
for(int k = 0; k < s.length(); k++) {
if(s[k] == '\\') cnt++;
if(cnt == 2) {
s1 = s.substr(0, k);
s2 = s.substr(k - 1, s.length() - k + 1);//这里比较麻烦 为了前面的统一化转数字
break;
}
}
s1 = s1.erase(0, 2);
s2 = s2.erase(0, 2);
num1 = atoi(s1.c_str());
num2 = atoi(s2.c_str());
for (int i = 0; i < v.size(); i++)
{
if(v[i] == num1) {
temp = v[i];
v.erase(v.begin() + i);
v.insert(v.begin() + i, num2);
}
}
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
if (s[0] == 's') {
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
}
if (s[0] == 'd') {
s = s.erase(0,1);
int num = atoi(s.c_str());
for (int i = 0; i < v.size(); i++) {
if(v[i] == num) v.erase(v.begin() + i);
}
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
}
}
}
}
return 0;
}
vector也可以insert
2、输入表达式，输出值。分两种情况：中缀表达式和后缀表达式。
中缀表达式求值：先将中缀表达式建立二叉树转后缀表达式（应该不会严格要求建树解决），然后再求值。
input:
1+2-1*((3+4)/5-6)+7
12+134+5/6-*-7+
result: 14.6
#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;
string toSuf(string s) {
map<char, int> isp, icp; //isp--in stack preority icp--in coming preority
isp['('] = 1; isp['*'] = 5; isp['/'] = 5; isp['+'] = 3; isp['-'] = 3; isp[')'] = 6;
icp['('] = 6; icp['*'] = 4; icp['/'] = 4; icp['+'] = 2; icp['-'] = 2; icp[')'] = 1;
string sufstr;
stack<char> opt;//operator
for (int i = 0; i < s.length(); i++) {
if (isalpha(s[i]) || (s[i] >= '0' && s[i] <= '9')) {
sufstr += s[i];
}
else if (opt.empty() || icp[s[i]] > isp[opt.top()]) {
opt.push(s[i]);
}
else
{
if(s[i] == ')') {
while(opt.top() != '(') {
sufstr += opt.top();
opt.pop();
}
opt.pop();
}
else {
while(!opt.empty() && isp[opt.top()] >= icp[s[i]]) {
sufstr += opt.top();
opt.pop();
}
opt.push(s[i]);
}
}
}
while(!opt.empty()) {
sufstr += opt.top();
opt.pop();
}
return sufstr;
}
double calSuf(string s) {
stack<double> opd;//operand
for(int i = 0; i < s.length(); i++) {
if(s[i] >= '0' && s[i] <= '9') {
opd.push(s[i] - '0');
}
else {
double opd2 = opd.top();
opd.pop();
double opd1 = opd.top();
opd.pop();
switch (s[i]) {
case '+': opd.push(opd1 + opd2); break;
case '-': opd.push(opd1 - opd2); break;
case '*': opd.push(opd1 * opd2); break;
case '/': opd.push(opd1 / opd2); break;
}
}
}
return opd.top();
}
int main() {
int sum1, sum2;
string s1, s2, sufs;
cout << "请输入中缀表达式: ";
cin >> s1;
sufs = toSuf(s1);
cout << "后缀表达式为: " << sufs << endl;
cout<< "结果为: " << calSuf(sufs) << endl;
cout << "请输入后缀表达式: ";
cin >> s2;
cout << "结果为: " << calSuf(s2) << endl;
return 0;
}
2011年北理复试上机题
1、输入一组单词(区分大小写),统计首字母相同的单词的个数，相
同的单词不累加，输出格式:“字母，个数”
input: I am a boy,you are a boy.
output:
I,1
a,3
b,1
y,1
#include <iostream>
#include <map>
#include <set>
using namespace std;
int main() {
string s;
while(getline(cin, s)) {
map<char, int> mmp;
set<string> ss;
string str;
for(int i = 0; i < s.length(); i++) {
if(isalpha(s[i])) str += s[i];
if(s[i] == ' ' || s[i] == ',' || s[i] == '.' || i == s.length() - 1) {
if(str != "") {
ss.insert(str);
str = "";
}
}
}
for(auto i = ss.begin(); i != ss.end(); i++) {
string word = *i;
mmp[word[0]]++;
}
for(auto i = mmp.begin(); i != mmp.end(); i++) {
cout << i ->first << "," << i -> second << endl;
}
}
return 0;
}
3、给一个字符串(aaaa(bbbb(cccc,dddd),eeee(ffff)))该字符串
表明的是各个人的层次关系。
比如aaaa是bbbb和eeee的领导，bbbb是cccc和dddd的领导。
现输入一个名称，比如ffff,要求输出其领导关系
input: (aaaa(bbbb(cccc,dddd),eeee(ffff)))
output: aaaa>eeee>ffff
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
string s,name;
while(1){
vector<string> ss;
int flag=0;
cin>>s>>name;
ss.push_back(name);
int i=s.find(name);
int j=i;
while(--i){
if(s[i]==')'){
flag--;
}
else if(s[i]=='('){
flag++;
}
if(flag>0){
i--;
j=i;
while(s[j]!='('&&s[j]!=')'&&s[j]!=','){
j--;
}
string temp=s.substr(j+1,i-j);
ss.push_back(temp);
i=j+1;
flag=0;
}
}
vector<string>::iterator it;
it=ss.begin();
cout<<*it;
it++;
for(;it!=ss.end();it++){
cout<<">"<<*it;
}
cout<<endl;
}
}
2012年北理复试上机题
（还有优化空间）
2、学生有(学号，姓名，性别，年龄)，初始化三个学生的信息
(10, wes, f, 23) (20, ert, f, 45) (30, str, t, 89) ,然后对学生信息进行插入和删
除处理
例如: I12,rt, f, 67表示插入12,rt, f, 67
D10表示删除学号为10的学生的信息
每次操作完成以后输出所有学生的信息按学号从大到小排序
输入: I12,rt,f,67
输出: (30,str,t,89),(20,erf,f,45),(12,rt,f,67),(10,wes,f,23)
输入: D10
输出: (30,str,t,89),(20,erf,f,45),(12,rt,f,67)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct student
{
int age, id;
string name, gender;
};
bool cmp(student t1, student t2)
{
if (t1.id != t2.id)
return t1.id > t2.id;
}
int main()
{
int a, i, j;
string s;
student stu;
vector<student> v;
student st[3];
st[0].id = 10; st[0].name = "wes"; st[0].gender = "f"; st[0].age = 23;
st[1].id = 20; st[1].name = "erf"; st[1].gender = "f"; st[1].age = 45;
st[2].id = 30; st[2].name = "str"; st[2].gender = "t"; st[2].age = 89;
v.push_back(st[0]);
v.push_back(st[1]);
v.push_back(st[2]);
while (getline(cin, s)) {
string str[4];
if (s[0] == 'I') {
int n = (s[1] - '0') * 10 + (s[2] - '0');
stu.id = n;
n = s[s.length() - 1] - '0' + (s[s.length() - 2] - '0') * 10;
stu.age = n;
string ss = "";
for (i = 4; i < s.length(); i++) {
if (s[i] == ',') {
stu.name = ss;
ss = "";
break;
}
ss += s[i];
}
for (j = i + 1; j < s.length(); j++) {
if (s[j] == ',') {
stu.gender = ss;
break;
}
ss += s[j];
}
v.push_back(stu);
sort(v.begin(), v.end(), cmp);
for (i = 0; i < v.size(); i++) {
cout << "(" << v[i].id << "," << v[i].name << "," << v[i].gender << "," << v[i].age << ")";
if (i < v.size() - 1)
cout << ",";
}
}
if (s[0] == 'D') {
int n = (s[1] - '0') * 10 + (s[2] - '0');
for (i = 0; i < v.size(); i++) {
if (v[i].id == n)
{
v.erase(v.begin() + i);
break;
}
}
sort(v.begin(), v.end(), cmp);
for (i = 0; i < v.size(); i++) {
cout << "(" << v[i].id << "," << v[i].name << "," << v[i].gender << "," << v[i].age << ")";
if (i < v.size() - 1)
cout << ",";
}
}
}
return 0;
}
3、利用后序和中序确定前序遍历结果
示例:
输入(按后序、中序): CHBEDA CBHADE
输出: ABCHDE
https://blog.csdn.net/m0_51961114/article/details/126891944
#include<iostream>
#include<string>
using namespace std;
int getPos(char c, string inStr)
{
int pos;
for (pos = 0; pos < inStr.size(); pos++)
{
if (inStr[pos] == c)
break;
}
return pos;
}
void func(int inlidx, int inridx, int postlidx, int postridx, string inStr, string postStr, string& ans)
{
int pos = getPos(postStr[postridx], inStr);
ans.push_back(postStr[postridx]);
int tmpl = pos - inlidx;
int tmpr = inridx - pos;
if (pos > inlidx)
func(inlidx, pos - 1, postlidx, postridx - tmpr - 1, inStr, postStr, ans);
if (pos < inridx)
func(pos + 1, inridx, postlidx + tmpl, postridx - 1, inStr, postStr, ans);
}
string preorderString(string inorderString, string postorderString)
{
int sz = inorderString.size();
string ans;
func(0, sz - 1, 0, sz - 1, inorderString, postorderString, ans);
return ans;
}
int main()
{
string inStr = "EBFADC";
string postStr = "EFBDCA";
string ans = preorderString(inStr, postStr);
cout << "前序遍历：";
cout << ans << endl;
return 0;
}
利用后序和中序确定前序遍历结果
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
string s, t;
string c;
int n;
// 定义递归函数，参数包括当前处理的字符串范围 [l, r] 和目标字符串范围 [l1, r1]
void dfs(int l, int r, int l1, int r1) {
if (l > r) return; // 递归终止条件，处理空字符串范围
if (l == r) {
c += s[l]; // 如果字符串范围只有一个字符，直接添加到结果中
return;
}
char rt = t[r1]; // 取目标字符串的最后一个字符
int fen = l;
// 在当前字符串范围中查找目标字符串最后一个字符的位置
for (int i = l; i <= r; i++) {
if (s[i] == rt) {
fen = i;
break;
}
}
c += rt; // 将目标字符串最后一个字符添加到结果中
// 递归处理左子树和右子树
dfs(l, fen - 1, l1, l1 + fen - 1 - l);
dfs(fen + 1, r, l1 + fen - 1 + 1, r1 - 1);
}
int main() {
cin >> s >> t;
n = s.length();
// 调用递归函数处理字符串
dfs(0, n - 1, 0, n - 1);
cout << c << endl; // 输出结果字符串
}
2013年北理复试上机题
2、输入一组英文单词，按字典顺序(大写与小写字母具有相同大小写)
排序输出.
示例:
输入: Information Info Inform info Suite suite suit
输出: Info info Inform Information suit Suite suite
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream> // 用于分割输入字符串
#include <cctype> // 用于大小写转换
using namespace std;
// 自定义比较函数，用于忽略大小写比较
bool caseInsensitiveCompare(const string& str1, const string& str2) {
string s1 = str1;
string s2 = str2;
// 将字符串转换为小写
transform(s1.begin(), s1.end(), s1.begin(), ::tolower);
transform(s2.begin(), s2.end(), s2.begin(), ::tolower);
return s1 < s2;
}
int main() {
vector<string> words;
string input;
cout << "请输入一组英文单词，以空格分隔：" << endl;
// 读取输入的单词并存储在vector中
getline(cin, input);
istringstream iss(input);
string word;
while (iss >> word) {
words.push_back(word);
}
// 使用自定义比较函数对单词进行排序
sort(words.begin(), words.end(), caseInsensitiveCompare);
cout << "按字典顺序排序后的单词：" << endl;
// 输出排序后的单词
for (const string& w : words) {
cout << w << " ";
}
cout << endl;
return 0;
}
transform(s1.begin(), s1.end(), s1.begin(), ::tolower);
transform()是一个 C++ 标准库函数，用于对一个范围内的元素进行转换操作。在这里，它被用于操作字符串s1。s1.begin()和s1.end()：这是字符串s1的迭代器，表示要操作的范围，从字符串的开头到结尾。s1.begin()：这是目标范围的起始位置，表示我们要从字符串的开头开始操作。::tolower：这是 C++ 标准库中的一个函数，用于将字符转换为小写形式。::用于指定这是全局作用域中的tolower函数。
综合起来，这一行代码的作用是将字符串 s1 中的所有字母字符都转换为小写形式，而不改变其他字符（如数字、标点符号等），并将结果存储回 s1 中。
istringstream iss(input);
getline(cin, input);：这行代码使用getline()函数从标准输入cin中读取一行文本，并将其存储在名为input的字符串中。getline()函数会一直读取字符，直到遇到换行符\n为止，将整行文本存储在input中。istringstream iss(input);：接下来，代码创建了一个名为iss的字符串流对象istringstream，并将之前读取的input字符串传递给它。这将允许我们通过字符串流逐个提取单词。string word;：这是一个用于存储每个单词的字符串变量。while (iss >> word)：这是一个while循环，它的条件是尝试从字符串流iss中提取一个单词，并将提取的单词存储在word变量中。如果提取成功（即如果还有更多的单词可供提取），则进入循环体。
这段代码的目标是将输入的文本分割为单词，以空格为分隔符。例如，如果输入是 "Hello world"，那么在循环结束后，words 向量将包含两个元素，分别是 "Hello" 和 "world"。
3、编写程序:输入表达式，输出相应二叉树的先序遍历结果（干脆中缀转前缀 后缀都给出了 ，有示例）
https://blog.csdn.net/Zy1_6_2/article/details/119488299
不过是JAVA代码
用宝子写的代码
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
string s; //中缀字符串
struct Node{
struct Node *left; //左孩子节点
struct Node *right; //右孩子节点
int l; int r; //这个节点是中缀表达式哪一段子字符串(从s[l]到s[r])
Node():left(NULL),right(NULL) {}
};
bool Judge(int l,int r){ //判断子串是不是一个数字（比如a，23这种）
for(int i=l;i<=r;i++){
if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='('||s[i]==')'||s[i]=='^') return false;
}
return true;
}
void dfs(Node *root,int l,int r){
if(s[l]=='(') {
int flag = 1,Ji=0;
for(int i=l;i<=r;i++) {
if(s[i]==')') Ji--; if(s[i]=='(') Ji++;
if(i<r&&!Ji) flag=0;
}
if(flag) l++,r--;
}
if(Judge(l,r)) {
root->l=l,root->r=r; return; //假如都是数字或者字母，说明到底了，赋值后返回；
}
int pos=-1,Ji=0;
//先找最外面的+，-
for(int i=r;i>=l;i--){
if(s[i]=='(') Ji--; if(s[i]==')') Ji++;
if((s[i]=='-'||s[i]=='+')&&!Ji) { pos=i; break; }
}
//找不到再找*,/
Ji=0;
if(pos==-1){
for(int i=r;i>=l;i--){
if(s[i]=='(') Ji--; if(s[i]==')') Ji++;
if((s[i]=='*'||s[i]=='/')&&!Ji) { pos=i; break; }
}
}
Ji = 0;
if(pos==-1){
for(int i=l;i<=r;i++){
if(s[i]=='(') Ji--; if(s[i]==')') Ji++;
if((s[i]=='^'&&!Ji)) { pos=i; break; }
}
}
//找到了，可以递归了！
root->l=root->r=pos;
root->left = new Node(), root->right= new Node();
dfs(root->left,l,pos-1); dfs(root->right,pos+1,r);
}
//前序遍历
void QianXu(Node *rt){
if(rt==NULL) return;
for(int i=rt->l;i<=rt->r;i++) cout<<s[i];
QianXu(rt->left); QianXu(rt->right);
}
//后序遍历
void HouXu(Node *rt){
if(rt==NULL) return;
HouXu(rt->left); HouXu(rt->right);
for(int i=rt->l;i<=rt->r;i++) cout<<s[i];
}
int main(){
int m; cin>>m;
while(m--){
cin>>s;
int l=0,r=s.length()-1;
Node *rt = new Node();
dfs(rt,l,r);
HouXu(rt);
cout<<endl;
}
}
2014年北理复试上机题
2015年北理复试上机题
4、求字符串1与字符串2的最大公共子串的长度及此长度最大公共子串的个数。
输入: abcdefg Eebcdfg (最大公共子串:bcd)
输出: 3 1
输入: abcdefg abcddefg (最大公共子串为：abcd defg)
输出: 4 2
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main() {
string a, b;
while(cin >> a >> b) {
int la = a.length();
int lb = b.length();
int maxn = 0, num = 0;
map<int, vector<string> > mmp;
string str;
for(int i = 0; i < la; i++) {
for(int j = 0; j < lb; j++) {
if(a[i] == b[j]) {
int pi = i, pj = j;
while(a[pi] == b[pj] && pj < lb && pi < la) {
num++;
str += a[pi];
pj++;
pi++;
}
if(num >= maxn) maxn = num;
mmp[num].push_back(str);
str = "";
num = 0;
}
}
}
cout << maxn << " " << mmp[maxn].size() << endl;
}
return 0;
}
2016年北理复试上机题
2、输入字符串，输出字符串中包含的数字，比如 2.3ABC0-2.3 输出 2.3 0 -2.3。
注意一些特殊的情况如+004.500值为+4.5。
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str,s[105];
getline(cin,str);
int i,j,k,n=0,flag=0,st=-1,dot=0;
// 还整了个终止符啊
str[str.length()]='A';
for(i=0; i<str.length()+1; i++)
{
if(flag==0)//没开始存数
{
if(str[i]=='.')
{
flag=1; // 开始存数
dot=1; // 有小数点了
st=i; // 开始位置
}
else if(str[i]=='+'||str[i]=='-'||(str[i]>='0'&&str[i]<='9'))
{
flag=1;
st=i;
}
}
else if(flag==1)
{
if(str[i]=='.')
{
// 若已经有过点了，因为还可以分割出来一个类似于.99的东西，所以i--还可以让它重新认识这个点
if(dot==1)
{
s[n++]=str.substr(st,i-st);
flag=0;
dot=0;
st=-1;
i--;
}
else
dot=1;
}
else if(str[i]=='+'||str[i]=='-')
{
// 开始了一个新数字，重新认识这个数字
s[n++]=str.substr(st,i-st);
flag=0;
st=-1;
dot=0;
i--;
}
else if((str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z')||str[i]==' ')
{
s[n++]=str.substr(st,i-st);
flag=0;
st=-1;
dot=0;
}
}
}
for(i=0; i<n; i++)//处理提取出来的字符串
{
st=0;
str=s[i];
if(str[0]=='+'||str[0]=='-')//若第一个字符为符号则从第二个开始分析
{
cout<<str[0];
st=1;
}
int t;
for(j=st; j<str.length(); j++)//找到第一个不为0的数字或小数点
{
if((str[j]>='1'&&str[j]<='9')||str[j]=='.')
{
t=j;
break;
}
}
if(str[t]=='.')//第一个为小数点
{
cout<<"0.";
for(j=str.length()-1; j>=0; j--)
if(str[j]>='1'&&str[j]<='9')
break;
for(k=t+1; k<=j; k++)
cout<<str[k];
cout<<endl;
}
else//第一个为数字1--9
{
for(j=str.length()-1; j>=0; j--)
if(str[j]>='1'&&str[j]<='9')
break;
for(k=t; k<=j; k++)
cout<<str[k];
cout<<endl;
}
}
cout<<endl;
return 0;
}
2017年北理复试上机题
2、显示出如下数组中的所有元素，并使用二分查找法在数组中查找元素。
int a[]={-90,-32,12,16,24,36,45,59,98,120};
输入:
-90 -32 12 16 24 36 45 59 98 120
输出:
-90 -32 12 16 24 36 45 59 98 120
请输入所要查找的元素: 24
第5个元素为24,比较次数为1
请输入所要查找的元素: 120
第10个元素为120,比较次数为4
请输入所要查找的元素: 6
查找失败,比较次数为3
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> a;
int n;
while (cin >> n) {
a.push_back(n);
if(getchar() == '\n') break;
}
for(int i = 0; i < a.size(); i++) {
cout << a[i] << " ";
}
cout << endl << "请输入所要查找的元素: ";
int cx;
while(cin >> cx) {
int low = 0;
int high = a.size() - 1;
int mid, cnt = 0;
while(low <= high) {
cnt++;
mid = (low + high) / 2;
if(a[mid] == cx) {
cout << "第" << mid + 1 << "个元素为" << cx << ",比较次数为" << cnt << endl;
break;
}
else if(a[mid] > cx) high = mid - 1;
else low = mid + 1;
}
if(low > high) cout << "查找失败,比较次数为" << cnt << endl;
cout << "请输入所要查找的元素: ";
}
return 0;
}
2018年北理复试上机题
1、输入一个只含有英文字母的字符串，输出最大回文子串的长度及此长度回文子串的个数（回文不区分大小写）。
样例：输入aBaAb (最大回文子串为BaAb)
输出4 1
输入aBcbBb (最大回文子串为Bcb和bBb)
输出 3 2
实际测试样例：
输入:a B
输出: 1 2
暴力解：
#include<bits/stdc++.h>
using namespace std;
//判断是否为回文串
bool judge(string str){
for(int i = 0;i < str.length() / 2;i++){
if(str[i] != str[str.length() - 1 - i])
return false;
}
return true;
}
int main(){
string str;
cin>>str;
for(int i = 0;i < str.length();i++)
str[i] = toupper(str[i]);
int maxl = 0; //记录最长的回文子串的长度
int sum = 0; //记录总数
for(int i = 0;i < str.length();i++){
for(int j = i + 1;j <= str.length();j++){
string temp = str.substr(i, j - i);
if(!judge(temp)){ //不是回文串，跳过
continue;
} else {
int len = temp.length(); //得到回文串的长度
if(maxl < len){ //长度大于最长，更新maxl和sum
maxl = len;
sum = 1;
} else if(maxl == len){ //长度等于最长，sum加上这个串出现的次数
sum += 1;
}
}
}
}
cout<<maxl<<" "<<sum<<endl;
}
2、哥德巴赫猜想
任何一个大于2的偶数均可表示为两个素数之和。输入m, n(6<=m<=n<=50),则把[m, n]内的所有偶数表示成两个素数之和的形式。输出这些素数及其出线的次数，输出次序按照素数出现的次数从多到少输出；若出线次数相同，按照素数从大到小输出；若偶数有多种素数相加形式，则把所有的情况都输出，每种情况占一行。
输入：8 9 输出：5 1 3 1
输入：9 10 输出：5 2
7 1 3 1
#include<bits/stdc++.h>
using namespace std;
vector<int> primenum;
bool mark[51] = {0};
void init(){
for (int i = 2; i < 50; i++){
if(mark[i] == 0){
primenum.push_back(i);
for(int j = i*i; j < 50; j+=i){
mark[j] = true;
}
}
}
sort(primenum.begin(), primenum.end());
}
bool comp(pair<int, int > &a, pair<int, int > &b){
if(a.second != b.second){
return a.second > b.second;
}else{
return a.first > b.first;
}
}
int main(){
init();
int a, b;
map <int , int> res;
cin>>a>>b;
for(int i = 0; i < primenum.size(); i++){
res[primenum[i]] = 0;
}
for(;a <= b; a++) {
if(a%2 == 0){
for (int i = 0; i < 51; i++) {
mark[i] = false;
}
for(int i = 0; i < primenum.size(); i++){
if(find(primenum.begin(), primenum.end(), primenum[i]) != primenum.end() && find(primenum.begin(), primenum.end(), a - primenum[i]) != primenum.end()){
if(mark[a - primenum[i]])
break;
else{
mark[a - primenum[i]] = true;
mark[primenum[i]] = true;
res[primenum[i]]++;
res[a - primenum[i]]++;
}
}
}
}
}
vector<pair<int , int>> result;
for (const auto &item : res) {
if (item.second != 0)
result.emplace_back(item);
}
sort(result.begin(), result.end(), comp);
for(const auto &item : result){
cout << item.first << " " << item.second << endl;
}
return 0;
}
str.substr(i, j - i);
str.substr(i, j - i)：这是 substr() 函数的调用。它接受两个参数：
第一个参数 i 表示子字符串的起始位置。
第二个参数 j - i 表示子字符串的长度。
str[i] = toupper(str[i]);
toupper()：这是一个 C++ 标准库中的函数，用于将一个字符转换为大写形式。它接受一个字符作为参数，返回相应的大写字符。
2019年北理复试上机题
1、碎片字符串
形如aabbaaacaa的字符串，可分为五个相同连续字母组成的碎片：'aa','bb','aaa','c','aa'，其中每个碎片只出现一次，即该字符串包含'aa','bb','aaa','c'四个碎片，且输出时按字典序排序。
#include<bits/stdc++.h>
using namespace std;
int main(){
string str;
cin>>str;
set<string> s;
for(int i = 0;i < str.length();i++){
string temp = "";
temp += str[i];
while(str[i] == str[i + 1]){
temp += str[i++];
}
s.insert(temp);
}
for(set<string>::iterator iter = s.begin();iter != s.end();iter++){
cout<<*iter<<endl;
}
}
2、哈夫曼树
输入n,以及n个数（用,隔开）,构造哈夫曼树（不用真的用树来写代码）,输出其最小带权路径长度
eg:输入 4
2,4,5,7
输出：35
输入：4
1,1,1,1
输出：8
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, sum = 0;
string str;
cin>>n>>str;
vector<int> vect; //存储数字
//处理字符串，提取数字放入vect
char *t = (char *)str.data();
char *temp = strtok(t, ",");
while(temp != NULL){
int i = atoi(temp);
vect.push_back(i);
temp = strtok(NULL, ",");
}
//主要思想：哈夫曼树的带权路径和=非叶子结点的和
//每次排序后， vect[i + 1] += vect[i]; vect[i + 1]中存储着这一非叶子结点的路径，并在下次排序时剔除了vect[i]
for(int i = 0;i < n - 1;i++){
sort(vect.begin() + i, vect.end());
vect[i + 1] += vect[i];
sum += vect[i + 1];
}
cout<<sum;
}
使用优先级队列（自动排序）
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, sum = 0;
string str;
cin>>n>>str;
priority_queue<int, vector<int>, greater<int> >q; //优先级队列存储数字
//处理字符串，提取数字放入q
char *t = (char *)str.data();
char *temp = strtok(t, ",");
while(temp != NULL){
int i = atoi(temp);
q.push(i);
temp = strtok(NULL, ",");
}
//主要思想：哈夫曼树的带权路径和=非叶子结点的和
//出队最小的两个值，加和入队，同时加入sum
for(int i = 0;i < n - 1;i++){
int a = q.top();q.pop();
int b = q.top();q.pop();
q.push(a + b);
sum += a + b;
}
cout<<sum;
}
char *t = (char *)str.data();
这行代码是将一个 C++ 标准库的 std::string 对象中的字符串数据转换为一个 C 风格字符串（字符数组）的指针。
让我们分解这行代码：
str：这是一个std::string对象，它包含了字符串数据。str.data()：std::string类有一个成员函数data()，它返回一个指向字符串数据的指针（即 C 风格字符串的指针）。这个指针指向字符串的第一个字符。(char *)：这是一个类型转换操作，它将str.data()返回的指针转换为char*类型的指针。这是因为**str.data()**返回的指针类型通常是**const char***，但在某些情况下，你可能需要将其转换为可修改的**char***类型，以便修改字符串的内容。需要注意的是，这种类型转换可能会引入潜在的安全问题，因此在进行此类转换时要小心。char *t：这是声明了一个名为t的字符指针，用于存储转换后的字符串数据的指针。
char *temp = strtok(t, ",");
这行代码使用了 C 语言标准库中的 strtok 函数，对一个以逗号分隔的字符串进行分割。
让我们分解这行代码：
t：这是一个char*类型的指针，指向一个以逗号分隔的字符串。通常，这个字符串是在之前的代码中从std::string对象中提取出来并转换为 C 风格字符串的。","：这是一个字符串字面值，表示分隔符。strtok函数将会使用这个分隔符来切割字符串。strtok(t, ",")：这是调用strtok函数的语法，它接受两个参数：- 第一个参数是要分割的字符串，即指向待分割字符串的指针。在这里，我们传递了
t，它指向以逗号分隔的字符串。 - 第二个参数是分隔符字符串，用于指定如何分割原始字符串。在这里，我们传递了逗号
","作为分隔符。
- 第一个参数是要分割的字符串，即指向待分割字符串的指针。在这里，我们传递了
strtok 函数的作用是将字符串切割成多个子字符串，每个子字符串以分隔符分隔。在第一次调用 strtok 时，它会返回第一个子字符串的指针，并将原始字符串中的分隔符替换为 null 终止符，以便将子字符串视为一个 C 风格字符串。
在你的代码中，char *temp = strtok(t, ",") 的作用是将 t 中的第一个以逗号分隔的子字符串提取出来，并将其指针存储在 temp 变量中。以后，你可以使用 temp 来访问这个子字符串的内容。
需要注意的是，strtok 函数是一个有状态的函数，它会记住上一次分割的位置。因此，如果你想继续分割原始字符串的下一个子字符串，可以再次调用 strtok，但不要传递原始字符串，只需传递 NULL 作为第一个参数即可。例如：
char *temp2 = strtok(NULL, ",");
这将返回原始字符串中的下一个以逗号分隔的子字符串，以及后续的子字符串，以此类推。
char *temp = strtok(t, ",");
while(temp != NULL){
int i = atoi(temp);
q.push(i);
temp = strtok(NULL, ",");
}
priority_queue<int, vectorint>, >q;
这行代码定义了一个 C++ 中的优先队列（Priority Queue），其中使用 greater<int> 作为比较函数，以便实现小顶堆（Min Heap）的行为。
让我们分解这行代码：
priority_queue<int, vector<int>, greater<int> > q;：这是一个变量声明语句，定义了一个名为q的优先队列对象。priority_queue：这部分指定了要创建的数据结构类型，即优先队列。<int>：这是优先队列中元素的数据类型，即队列中存储的是整数类型的元素。<vector<int>>：这部分指定了底层容器的类型。优先队列通常使用向量（vector）作为底层容器，用于存储元素。这表示队列将使用vector<int>作为底层容器。<greater<int>>：这是一个可选的参数，指定了比较函数。在这里，使用greater<int>，它是 C++ 标准库中定义的一个函数对象，表示将元素按照递增的顺序进行排列，即创建了一个小顶堆。这意味着队列中的元素将按照从小到大的顺序排列，队头元素是最小值。
这行代码创建了一个小顶堆的优先队列 q，允许你将整数元素插入队列，并自动维护队列的顺序，确保队头元素是最小的元素。
你可以使用 q.push() 来插入元素，使用 q.top() 来访问队头元素，使用 q.pop() 来移除队头元素，以及使用其他成员函数来执行常见的队列操作。这样的小顶堆通常在需要按照一定顺序处理元素的情况下非常有用，例如实现优先级队列或解决一些优化问题。
如果你想创建一个大顶堆（Max Heap）的优先队列，即队列中的元素按照从大到小的顺序排列，你可以使用 less<int> 作为比较函数，或者不指定比较函数，因为默认情况下，priority_queue 创建的是大顶堆。
2020年北理复试上机题
1、题目：给你一个 m*n 大小的矩阵，每个点有 0，1，2 三种取值；0 代表障碍物，1代表白纸，2 代表墨滴。每一秒墨滴可以向其上下左右扩散，将四周的白纸染色，被染色之后的白纸可以继续向四周扩散，以此类推。问经过几秒，矩阵中所有的白纸都被染色。
如果可以，则输出扩散时间；
如果不可以，则输出FALSE。
输入: m n 的大小以及矩阵每个点的值
输出: 扩散时间 或 FALSE
例如：
3 3
0 1 0
1 2 1
0 1 0
输出: 1
3 3
0 1 0
1 2 1
0 1 1
输出: 2
2 3
1 0 0
0 0 2
输出: False
#include <iostream>
#include <queue>
using namespace std;
int main() {
int m, n;
while (cin >> m >> n) {
int arr[m][n];
int temp = 0;
// 墨滴队列
queue<int> qx, qy;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
if(arr[i][j] == 2) {
qx.push(i);
qy.push(j);
}
if(arr[i][j] == 1) temp++;
}
}
int sec = 0;
while(!qx.empty() && temp) {
int size = qx.size();
int dir[5] = {1, 0, -1, 0, 1};
while(size--) {
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
for(int i = 0; i < 4; i++) {
int dx = x + dir[i];
int dy = y + dir[i + 1];
if(dx < 0 || dx >= m || dy < 0 || dy >= n || arr[dx][dy] != 1) continue;
else {
arr[dx][dy] = 2;
temp--;
qx.push(dx);
qy.push(dy);
}
}
}
sec++;
}
if (temp) cout << "False" << endl;
else cout << sec << endl;
}
return 0;
}
2、输入三个字符串，问第三个字符串能否由前两个字符串多次重复组合形成。如果能，则输出前两个字符串各自的使用次数；如果不能，则输出 FALSE。
输入：三个字符串
输出：前两个字符串各自的次数 或 FALSE
输入: aa bb bbaaaabbaa
输出: 3 2
输入: ab ba abbaaabaab
输出: FALSE
(注意特殊用例: aa aab aabaa 故递归)
#include <iostream>
#include <string>
using namespace std;
// 函数用于检查str3是否可以由str1和str2多次重复组合而成
bool isRepeating(string str1, string str2, string str3, int count1, int count2) {
int len1 = str1.length();
int len2 = str2.length();
int len3 = str3.length();
if (len3 == 0) {
// 如果str3为空字符串，表示可以由str1和str2重复组合而成
cout << count1 << " " << count2 << endl;
return true;
}
if (len3 < len1 && len3 < len2) {
// 如果str3的长度小于str1和str2中的最小长度，无法匹配，返回FALSE
return false;
}
if (str3.substr(0, len1) == str1) {
// 如果str3以str1开头，尝试从str3中去掉str1，并增加str1的使用次数
bool success1 = isRepeating(str1, str2, str3.substr(len1), count1 + 1, count2);
if(success1) {return true;}
}
if (str3.substr(0, len2) == str2) {
// 如果str3以str2开头，尝试从str3中去掉str2，并增加str2的使用次数
return isRepeating(str1, str2, str3.substr(len2), count1, count2 + 1);
}
// 如果无法匹配，返回FALSE
return false;
}
int main() {
string str1, str2, str3;
cin >> str1 >> str2 >> str3;
if (isRepeating(str1, str2, str3, 0, 0)) {
// 如果可以由str1和str2多次重复组合而成，由isRepeating函数输出结果
} else {
cout << "FALSE" << endl;
}
return 0;
}
2022年北理复试上机题
问题一
#include<iostream> // 包含输入输出流标准库
#include<math.h> // 包含数学函数库
using namespace std;
// 定义一个函数，用于将字符往后移动指定的步数
char set_letter(char l, int step) {
l = l + step;
if (l > 'z') {
l = l - 26; // 如果字符超过 'z'，则回到 'a' 开始
}
else if ((l > 'Z') && (l < 'a')) {
l = l - 26; // 如果字符超过 'Z' 且小于 'a'，也回到 'A' 开始
}
return l;
}
int main() {
char letter; // 存储输入的字符
int n; // 存储输入的整数
cin >> letter; // 从标准输入读取字符
cin >> n; // 从标准输入读取整数
// 检查输入的整数是否在合法范围内
if ((n < 1) || (n > 9)) {
cout << "请输入在1到9之间的值。" << endl;
return 0; // 退出程序
}
// 创建一个二维字符数组，用于存储输出的字符图案
char mtrx[2 * n - 1][2 * n - 1];
// 填充字符图案数组
for (int i = 0; i < 2 * n - 1; i++) {
for (int j = 0; j < 2 * n - 1; j++) {
if ((i == j) || ((i + j) == (2 * n - 2))) {
// 如果在主对角线上或副对角线上，则调用set_letter函数设置字符
mtrx[i][j] = set_letter(letter, abs(i - n + 1));
}
else {
mtrx[i][j] = ' '; // 否则，将字符设置为空字符
}
}
}
// 在字符图案中心放置输入的字符
mtrx[n - 1][n - 1] = letter;
// 打印字符图案
for (int i = 0; i < 2 * n - 1; i++) {
for (int j = 0; j < 2 * n - 1; j++) {
cout << mtrx[i][j]; // 输出字符
}
cout << endl; // 输出换行符
}
return 0; // 程序正常结束
}
输入与输出：
T
9
B B
A A
Z Z
Y Y
X X
W W
V V
U U
T
U U
V V
W W
X X
Y Y
Z Z
A A
B B
问题二
#include <iostream>
#include <string>
using namespace std;
int main(){
// 声明一个字符串S，用于存储用户输入的字符串
string S;
cin >> S;
// 声明并初始化用于存储每个连续字符序列起始和结束位置的数组
int begins[100] = {0};
int ends[100] = {0};
// 计数器，用于跟踪连续字符序列的数量
int count = 0;
// 用于存储每个连续字符序列的长度
int length[100] = {0};
// 循环遍历输入的字符串
for(int i = 0; i < S.length(); i++){
// 检查当前字符与下一个字符是否相等
if(S[i] != S[i + 1]){
// 如果不相等，表示找到一个字符序列的结束
ends[count] = i;
// 计算字符序列的长度
length[count] = ends[count] - begins[count] + 1;
// 更新下一个字符序列的起始位置
begins[count + 1] = i + 1;
// 增加计数器以跟踪下一个字符序列
count++;
}
}
// 声明并初始化用于存储最大长度的变量
int max_length = 1;
// 循环遍历每个字符序列的长度，找到最大的长度
for(int i = 0; i < count; i++){
if(max_length < length[i])
max_length = length[i];
}
// 输出找到的最大长度
cout << max_length << endl;
// 循环遍历字符序列，找到具有最大长度的序列并输出
for(int i = 0; i < count; i++){
if(length[i] == max_length){
for(int j = begins[i]; j <= ends[i]; j++){
cout << S[j];
}
cout << endl;
}
}
return 0;
}
#include <iostream>
#include <string>
#include <set>
using namespace std;
// 结果结构体
struct Result
{
set<char> keys; // 存储出现最多次数的字符
int count; // 出现的最大次数
};
int main(){
string s;
cin >> s;
Result result; // 存储结果的结构体
result.count = 0;
int count = 1; // 当前字符的出现次数
if(s.size() == 1){ // 如果字符串只有一个字符
result.keys.insert(s[0]); // 将该字符插入结果的字符集合中
result.count = 1; // 结果的最大次数为1
cout << result.count << endl; // 输出最大次数
cout << s << endl; // 输出字符
return 0;
}
for(int i = 1; i < s.size(); i++){ // 遍历字符串
if(s[i] == s[i - 1]){ // 如果当前字符与前一个字符相同
count++; // 增加当前字符的出现次数
}
if(s[i]!= s[i - 1] || i == s.size()-1){ // 如果当前字符与前一个字符不同，或者已经到达字符串末尾
if(count > result.count){ // 如果当前字符的出现次数大于结果的最大次数
result.count = count; // 更新结果的最大次数
result.keys.clear(); // 清空结果的字符集合
result.keys.insert(s[i - 1]); // 将当前字符插入结果的字符集合中
}else if(count == result.count){ // 如果当前字符的出现次数等于结果的最大次数
result.keys.insert(s[i - 1]); // 将当前字符插入结果的字符集合中
}
count = 1; // 重置当前字符的出现次数
if(s[i]!= s[i - 1] && i == s.size()-1){ // 如果当前字符与前一个字符不同，并且已经到达字符串末尾
if(count == result.count){ // 如果当前字符的出现次数等于结果的最大次数
result.keys.insert(s[i]); // 将当前字符插入结果的字符集合中
}
}
}
}
cout << result.count << endl; // 输出结果的最大次数
for(auto key : result.keys){ // 遍历结果的字符集合
for(auto i = 0; i < result.count; i++) // 输出字符对应的最大次数次数
{
cout << key;
}
cout << endl;
}
return 0;
}
输入与输出：
aacbb
2
aa
bb
问题三
#include <iostream>
using namespace std;
// 定义一个递归函数 an_algo，用于执行特定算法并输出一系列整数
int an_algo(int a, int count){
// 如果 a 大于 0，输出当前值并添加空格
if(a>0) cout<<a<<" ";
// 如果 a 等于 1，输出 1 并返回 count+1
if(a==1){
cout<<1<<endl;
return count+1;
}
// 如果 a 为偶数，递归调用 an_algo 函数，传递 a/2 和 count+1 作为参数
if(a%2 == 0){
return an_algo(a/2, count+1);
}
// 如果 a 为奇数，递归调用 an_algo 函数，传递 3*a+1 和 count+1 作为参数
else{
return an_algo(3*a+1, count+1);
}
}
int main(){
int a;
// 从用户输入读取整数 a
cin>>a;
// 调用 an_algo 函数，并将 a 和初始计数器值 0 作为参数
cout<<an_algo(a,0);
return 0;
}
问题四
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct Student{
string sno;
string cno;
float score;
};
bool mycmp(Student a, Student b){
if(a.cno[2] != b.cno[2]) return a.cno[2] < b.cno[2];
return a.score > b.score;
}
int main(int argc, char *argv[])
{
Student s;
string str;
vector<Student> students;
int i = 0;
while(cin >> str){
if(str == "\\"){ break;}
if(i%3 == 0){
s.sno = str;
}
else if(i%3 == 1){
s.cno = str;
}
else if(i%3 == 2){
s.score = atof(str.c_str());
students.push_back(s);
}
i++;
}
sort(students.begin(), students.end(), mycmp);
cout << " cno sno score" << endl;
for(int i = 0; i < students.size(); i++){
cout << " " << students[i].cno << " " << students[i].sno << " " << students[i].score << endl;
}
return 0;
}
2023年北理复试上机题
参考
https://blog.csdn.net/srg1011/article/details/88604093
https://www.cnblogs.com/ache/category/1674290.html
https://codeantenna.com/a/hmnddx1J1g
C语言文件操作
https://blog.csdn.net/qq_41785863/article/details/83988329