复试上机真题历年回顾-2012

排序

sort

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
vector<int>v;
string str;
signed main(){
    while(getline(cin,str)){
        int j=0;
        for(int i=0;i<str.size();i++){
            if(str[i]==',') {
                v.push_back(stoi(str.substr(j,i-j)));
                j=i+1;
            }
        }
        v.push_back(stoi(str.substr(j)));
        sort(v.begin(),v.end());
        for(int i=0;i<v.size();i++ ) {
            cout<<v[i];
            if(i!=v.size()-1) cout<<",";
        }
    }

}
/*
I12,rt,f,67
D10
*/

学生信息

模拟即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N =1e5+1000;
struct stu{
  int sno;
  string sname;
  string ssex;
  int sage;
};
vector<stu> s;
bool cmp(stu a,stu b){
    return a.sno>b.sno;
}
string str;
signed main(){
    s.push_back({10,"wes","f",23});
    s.push_back({20,"ert","f",45});
    s.push_back({30,"str","t",89});
    while(getline(cin,str)){
        if(str[0]=='I'){
            int j=1,cnt=0;
            stu tmp;
            for(int i=1;i<str.size();i++){
                if(str[i]==','&&!cnt) {
                    tmp.sno=stoi(str.substr(j,i-j));
                    j=i+1;
                    ++cnt;
                }else if(str[i]==','&&cnt==1){
                    tmp.sname=str.substr(j,i-j);
                    j=i+1;
                    ++cnt;
                }else if(str[i]==','&&cnt==2){
                    tmp.ssex=str.substr(j,i-j);
                    j=i+1;
                    ++cnt;
                }
            }
            tmp.sage=stoi(str.substr(j));
            s.push_back(tmp);
        }else if(str[0]=='D'){
            if(str.empty()){
                ;
            }else{
                int sno=stoi(str.substr(1));
                for(int i=0;i<s.size();i++)
                    if(s[i].sno==sno) {
                        s.erase(s.begin()+i);
                    }
            }
        }
        sort(s.begin(),s.end(),cmp);
        for(int i=0;i<s.size();i++){
            cout<<"("<<s[i].sno<<","<<","<<s[i].sname<<","<<s[i].ssex<<","<<s[i].sage<<")";
            if(i<s.size()-1) cout<<",";
        }
        cout<<endl;
    }

}
/*
I12,rt,f,67
D10
*/

已知后序和中序求前序

每次通过后序找到中序中根的位置
遍历左子树,遍历右子树

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void pre(string &post,int root,string &in,int st,int ed){//已知后序和中序求先序
    if(st<=ed){
        int i=in.substr(st,ed-st+1).find(post[root],0)+st;//根据后序遍历,在中序中找到当前树的根的位置
        cout<<in[i];
        pre(post,root-1-ed+i,in,st,i-1);//遍历左子树
        pre(post,root-1,in,i+1,ed);//遍历右子树
    }
}
void post(string &pre,int root,string &in,int st,int ed){//已知先序和中序求后序
    if(st<=ed){
        int i=in.substr(st,ed-st+1).find(pre[root],0)+st;//根据前序遍历,在中序中找到当前树的根的位置
        cout<<in[i];
        post(pre,root+1,in,st,i-1);//遍历左子树
        post(pre,root+i-st+1,in,i+1,ed);//遍历右子树
    }
}
signed main(){
    string in,post;
    cin>>in>>post;
    pre(post,0,in,0,in.size()-1);
    return 0;
}