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

求两个数的最大公约数

可以直接__gcd(a,b)或者用欧几里得

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

int gcd(int a,int b){
    return a%b?gcd(b,a%b):b;
    //(a,b)表示a和b的最大公约数
    //(a,b)=(b,a%b)
}

signed main(){
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b)<<endl;
    return 0;
}

英文单词排序

输出一组英文单词，按字典顺序(大写与小写字母具有相同大小写),排序输出。
示例:
输入: Information Info Inform info Suite suite suit
输出: Info info Inform Information suit Suite suite 

模拟即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N =1e5+100;
string s;
int cnt;
struct node{
    string data;
    int num;
} p[N];

bool cmp(node a,node b){
    string sa =a.data,sb=b.data;
    int na =a.num,nb=b.num;
    for(int i=0;sa[i];i++) sa[i]=tolower(sa[i]);
    for(int i=0;sb[i];i++) sb[i]=tolower(sb[i]);
    if(sa!=sb){
        return sa<sb;
    }
    return na<nb;//sa==sb的话 按下标排序
}
signed main(){
  while(cin>>s){
      p[++cnt].data=s;
      p[cnt].num=cnt;
  }
  sort(p+1,p+cnt+1,cmp);
  for(int i=1;i<=cnt;i++){
      cout<<p[i].data<<" ";
  }
}

中序转前序

其中10年考了中缀转后缀 13年考了中缀转前缀

3、编写程序:输入表达式，输出相应二叉树的先序遍历结果
输入: a+b*(c-d)-e/f
输出: -+a*b-cd/ef

这个题没见过基本不会
思路是这样的

• 初始化一个栈
• 从右向左扫描(依次存放字符)
• 遇到操作数,直接加入前缀表达式
• 遇到界限符。遇到)直接入栈,遇到(则一次弹出栈内运算符并假如前缀表达式
• 遇到运算符，依次弹出栈中优先级高于当前运算符的所有运算符，并加入前缀表达式。若碰到)或栈空则停止。之后再把当前运算符入栈
• 处理完所有字符后，将栈中剩余运算符依次弹出，并加入前缀表达式

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

int getPriority(char op){
    if(op=='+'||op=='-') return 0;
    return 1;
}
string intopre(string in){
    string s1,s2;
    int i=in.length()-1;
    while(i>=0){
        if(isalnum(in[i])) s2=s2+in[i],i--;//操作数放s1栈
        else if(in[i]==')') s1=s1+in[i],i--;//右括号放s2栈
        else if(in[i]=='+'||in[i]=='-'||in[i]=='*'||in[i]=='/'){//碰到运算符
            if(s1.size()==0||s1.back()==')'||getPriority(s1.back())<=getPriority(in[i])) s1=s1+in[i],--i;
            //运算符入栈s2的时机是 栈空 栈顶为) 栈顶元素优先级小于等于当前运算符
            else{//否则s1出栈
                s2=s2+s1.back();
                s1.pop_back();
            }
        }
        if(in[i]=='('){//遇到左括号
            while(s1.back()!=')'){
                s2=s2+s1.back();
                s1.pop_back();
            }
            s1.pop_back();
            --i;
        }
    }
    while(s1.size()){//弹出剩余运算符
        s2=s2+s1.back();
        s1.pop_back();
    }

    reverse(s2.begin(),s2.end());//翻转一下
    return s2;
}
string intopos(string in){
    string s1,s2;
    int i=0;
    while(i<in.length()){
        if(isalnum(in[i])) s2=s2+in[i],i++;//存放数字or字母
        else if(in[i]=='(') s1=s1+in[i],i++;//左括号特判
        else if(in[i]=='+'||in[i]=='-'||in[i]=='*'||in[i]=='/'){
            if(s1.size()==0||s1.back()=='('||getPriority(s1.back())<getPriority(in[i])) s1=s1+in[i],++i;
            else{
                s2=s2+s1.back();
                s1.pop_back();
            }
        }
        if(in[i]==')'){
            while(s1.back()!='('){
                s2=s2+s1.back();
                s1.pop_back();
            }
            s1.pop_back();
            ++i;
        }

    }
    while(s1.size()){
        s2=s2+s1.back();
        s1.pop_back();
    }
    return s2;    
}
char * string_char(string p){
    char *tmp=new char[p.length()+1];
    for(int i=0;p[i];i++) tmp[i]=p[i];
    return tmp;
}
int getPost(string pos){//求后缀表达式
    stack<int>s;
    for(int i=0;pos[i];i++){
        if(isdigit(pos[i])) s.push(pos[i]-'0');
        else{
            int a=s.top();
            s.pop();
            int b=s.top();
            s.pop();
            if(pos[i]=='+') s.push(a+b);
            else if(pos[i]=='*') s.push(a*b);
            else if(pos[i]=='-') s.push(b-a);
            else if(pos[i]=='/') s.push(b/a);
        }
    }
    return s.top();
}
signed main(){
    string in;
    cin>>in;
    cout<<intopre(in)<<endl;//中缀转前缀
    cout<<intopos(in)<<endl;//中缀转后缀
    cout<<getPost(intopos(in))<<endl;//算中缀表达式值
}