2012年机试题解及真题
1.输入是个正整数数字，从小到大排序输入：1,2,57,9，10，45,67,24,26
输出：1,2,5,7,9,10，,24,26,45,67
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[15];
for(int i=0; i<10; i++)
cin>>a[i];

sort(a,a+10);

for(int i=0; i<9; i++)
cout<<a[i]<<",";
cout<<a[9]<<endl;

return 0;
}
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
输出(10，wes,f,23), (12,rt,f, 67), (20,ert,f,45), (30, str, t, 89)
输入: D10 输出: (12,rt,f, 67)，(20,ert,f, 45), (30, str, t, 89)
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;

struct Stu
{
int num;
string name;
string sex;
int age;
};

bool cmp(Stu a,Stu b)
{
return a.num<b.num;
}

int main()
{
char op[105];
int i,num,age,n=3;
Stu stu[105];
stu[0].num=10;stu[0].name="wes";stu[0].sex="f";stu[0].age=23;
stu[1].num=20;stu[1].name="ert";stu[1].sex="f";stu[1].age=45;
stu[2].num=30;stu[2].name="str";stu[2].sex="t";stu[2].age=89;

while(1)
{
gets(op);

if(op[0]=='0')
break;
else if(op[0]=='I')//插入
{
char name[105],sex[105];
int num,age;

sscanf(op,"I%d,%[^,],%[^,],%d",&num,name,sex,&age);//sscanf用法
stu[n].num=num;
stu[n].name=name;
stu[n].sex=sex;
stu[n].age=age;
n++;

sort(stu,stu+n,cmp);

for(i=0; i<n-1; i++)
cout<<"("<<stu[i].num<<","<<stu[i].name<<","<<stu[i].sex<<","<<stu[i].age<<"),";
cout<<"("<<stu[n-1].num<<","<<stu[n-1].name<<","<<stu[n-1].sex<<","<<stu[n-1].age<<")"<<endl;
}
else if(op[0]=='D')//删除
{
int t;
sscanf(op,"D%d",&t);
for(i=0; i<n; i++)
{
if(stu[i].num==t)
{
if(i==n-1)
{
n--;
}
else
{
stu[i].num=stu[n-1].num;
stu[i].name=stu[n-1].name;
stu[i].sex=stu[n-1].sex;
stu[i].age=stu[n-1].age;
n--;
}
break;
}
}

sort(stu,stu+n,cmp);

for(i=0; i<n-1; i++)
cout<<"("<<stu[i].num<<","<<stu[i].name<<","<<stu[i].sex<<","<<stu[i].age<<"),";
cout<<"("<<stu[n-1].num<<","<<stu[n-1].name<<","<<stu[n-1].sex<<","<<stu[n-1].age<<")"<<endl;
}
}

return 0;
} 3. 利用后序和中序确定前序遍历结果
示例:
输入(按后序中序): CHBEDA
CBHADE
输出:
ABCHDE
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

char a[20],b[20];

void f(int ab,int ae,int bb,int be)
{
int i;
if(ab>ae) return;
cout<<a[ae];
for(i=bb; b[i]!=a[ae]; i++); //后序序列的最后一个为根
f(ab,ab+i-bb-1,bb,i-1);//递归求左子树先序
f(ab+i-bb,ae-1,i+1,be);//递归求右子树先序，注意ae-1
}

int main()
{
//a为后序，b为中序
while(scanf("%s%s",a,b)!=EOF)
{
int len=strlen(a);
f(0,len-1,0,len-1);
cout<<endl;
}

return 0;
}
[cpp] view plain copy
#include <iostream>
#include <string>
using namespace std;
//建树
string a,b;

struct node
{
char c;
node *l;
node *r;
};

void dfs(node *T)
{
if(T==NULL)
return ;
cout<<T->c;
dfs(T->l);
dfs(T->r);
}

//a后序 b中序
//CHBEDA CBHADE
void f(int aa,int ae,int bb,int be,node *&T)
{
if(aa>ae||bb>be)
return ;

if(T==NULL)
{
T=new node;
T->l=T->r=NULL;
}

int i;

T->c=a[ae];

for(i=0; i<b.length(); i++)
if(b[i]==a[ae])
break;
f(aa,aa+i-bb-1,bb,i-1,T->l);//左子树
f(aa+i-bb,ae-1,i+1,be,T->r);//右子树,注意ae-1
}

int main()
{
node *T=NULL;
cin>>a>>b;
f(0,a.length()-1,0,b.length()-1,T);
dfs(T);

return 0;
}
2013年机试真题及题解
1．求两个数的最大公约数示例: : 输入 :24,18 输出 :6
#include<iostream>
using namespace std;

/**
* 辗转相除法
*/
int gcd(int m,int n){
int t=n;
if(n>m){
n=m;
m=t;
}
while(n!=0){
t=m%n;
m=n;
n=t;
}
return m;
}

int main()
{
int x,y;
cout<<"输入:";
cin>>x>>y;
cout<<"输出:"<<gcd(x,y)<<endl;
return 0;
}
2．输入一组英文单词, , 按字典顺序( ( 大写与小写字母具有相同大小写) )排序输出. .示例: :输入:Information Info Inform info Suite suite suit输出:Info info Inform Information suit Suite suite
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

// 排序规则
bool cmp(string x,string y){
int t=0;
while(x[t]!='\0'&&y[t]!='\0'){
// 统一为小写进行比较
if(x[t]>'Z')
x[t]-=32;
if(y[t]>'Z')
y[t]-=32;
// 比较当前字母大小
if(x[t]!=y[t])
return x[t]<y[t];
// 当前位置相等，比较下一位
t++;
}
if(y[t]!='\0')
return true;
return false;
}

int main()
{
string voc[100];
int n=0;
while(cin>>voc[n++]);
n--;

sort(voc,voc+n,cmp);
for(int i=0;i<n;i++)
cout<<voc[i]<<" ";
cout<<endl;

return 0;
}
3．编写程序：输入表达式，输出相应二叉树的先序遍历结果输入： a+b*(c-d)-e/f输出： -+a*b-cd/ef
#include<iostream>
#include<string>
#include<stack>
using namespace std;

/**
* 问题转化
* 前缀表达式=前序遍历;
* 中缀表达式=中序遍历;
* 后缀表达式=后序遍历;
* 因此原问题可转化为求波兰式
*/

/**
* 求波兰式:(自己研究的方法，不知道是否主流)
* 建立两个栈，s1，s2;
* 从中缀表达式的右端开始检索，遇到非运算符直接压入栈s2;
* 遇到运算符，若栈s1为空，直接压栈s1;
* 若s1非空，比较当前运算符与栈顶运算符优先级，若栈顶运算符优先级高，s1弹栈，并立刻压入s2;若当前运算符优先级高，压入s1;
* 若已经检索完表达式，s1非空，则按顺序弹栈压入s2;
* s2弹栈即为所求。
*/

// 判断字符是否为运算符
bool isOp(char a){
if(a=='('||a=='+'||a=='-'||a=='*'||a=='/'||a==')')
return true;
return false;
}

// 表达式中运算符的优先等级
int pe(char a){
// 定义运算符的优先级分别为(+-*/)
int priority[6]={0,1,1,2,2,3};
char op[6]={'(','+','-','*','/',')'};
for(int i=0;i<6;i++){
if(op[i]==a)
return priority[i];
}
}

// 栈顶运算符的优先等级
int ps(char a){
// 定义运算符的优先级分别为(+-*/)
int priority[6]={0,1,1,2,2,0};
char op[6]={'(','+','-','*','/',')'};
for(int i=0;i<6;i++){
if(op[i]==a)
return priority[i];
}
}

int main()
{
stack<char> s1,s2;
string exp;
cin>>exp;
// 从右向左搜索表达式
for(int i=exp.length()-1;i>=0;i--){
bool flag=true;
// 左右括号匹配抵消的情况
if(exp[i]=='('&&s1.top()==')'){
s1.pop();
continue;
}
// 非运算符直接压入s2
if(!isOp(exp[i]))
s2.push(exp[i]);
else{
// s1为空，直接压栈
if(s1.empty())
s1.push(exp[i]);
// s1非空，比较当前运算符与栈顶运算符优先级
else{
// 当前运算符优先级高，压入s1
if(pe(exp[i])>=ps(s1.top()))
s1.push(exp[i]);
// 栈顶运算符优先级高，s1弹栈，并立刻压入s2
else{
while(pe(exp[i])<ps(s1.top())){
char t=s1.top();
s2.push(t);
s1.pop();
// 防止栈空出错
if(s1.empty())
break;
// 左右括号匹配抵消的情况
if(exp[i]=='('&&s1.top()==')'){
s1.pop();
flag=false;
break;
}
}
if(flag)
s1.push(exp[i]);
}
}

}
}

// 已经检索完表达式，s1非空，则按顺序弹栈压入s2
while(!s1.empty()){
char t=s1.top();
s2.push(t);
s1.pop();
}

// 输出结果
while(!s2.empty()){
cout<<s2.top();
s2.pop();
}
cout<<endl;

return 0;
}
2014年机试真题及题解
1．系统中有最近打开文件的记录, , 现用整数表示打开的文件名,, 且只
显示最近 3 3 个打开的文件, , 输出文件序列. .示例: :输入 :1 输出 :1输入 :2 输出 :2,1输入 :3 输出 :3,2,1输入 :4 输出 :4,3,2输入 :1 输出 :1,4,3输入 :4 输出 :1,4,3输入 :3 输出:1,4,3
#include<iostream>
#include<vector>
using namespace std;

int main()
{
vector<int> v; // 定义一个向量，用于存储数据
int temp; // 记录最近打开的文件
cout<<"输入:";
while(cin>>temp){
bool ie=false;
// 如果已打开文件不足三个,直接插入数据
if(v.size()<3)
v.insert(v.begin(),temp);
// 如果已打开文件已有三个，判断输入数据是否存在
else{
for(int i=0;i<v.size();i++)
if(v.at(i)==temp)
ie=true;
// 不存在
if(!ie){
// 删除末尾数据
v.pop_back();
// 首部添加新数据
v.insert(v.begin(),temp);
}
}

// 输出
cout<<"输出:";
// 通过迭代器遍历向量
for(vector<int>::iterator j=v.begin();j!=v.end();j++)
cout<<*j<<" ";
cout<<endl;
cout<<"输入:";
}

return 0;
}
2．在第一题基础上, , 稍作改动, , 显示最新打开的文件. .示例: :输入 :1 输出 :1输入 :2 输出 :2,1输入 :3 输出 :3,2,1输入 :4 输出 :4,3,2输入 :1 输出 :1,4,3输入 :4 输出 :4,1,3输入 :3 输出 :3,4,1
#include<iostream>
#include<vector>
using namespace std;

int main()
{
vector<int> v; // 定义一个向量，用于存储数据
int temp; // 记录最近打开的文件
cout<<"输入:";
while(cin>>temp){
int pos;
bool ie=false;
// 判断输入数据是否存在
for(int i=0;i<v.size();i++){
if(v.at(i)==temp){
ie=true;
pos=i;
}
}
// 存在,将该数据放在首部
if(ie){
v.erase(v.begin()+pos);
v.insert(v.begin(),temp);
}
// 不存在
else{
// 如果已打开文件不足三个,直接插入数据
if(v.size()<3)
v.insert(v.begin(),temp);
else{
// 删除末尾数据
v.pop_back();
// 首部添加新数据
v.insert(v.begin(),temp);
}
}

// 输出
cout<<"输出:";
// 通过迭代器遍历向量
for(vector<int>::iterator j=v.begin();j!=v.end();j++)
cout<<*j<<" ";
cout<<endl;
cout<<"输入:";
}

return 0;
}
3．求广义表的深度( ( 实际就是括号匹配 ), 示例: : 输入(c,((d,e),f),h)输出：3
#include<iostream>
#include<string>
#include<stack>
using namespace std;

/**
* 实际求括号匹配中，栈的深度
*/

int main()
{
stack<int> s;
int i=0,deep=0,max_deep=0;
string list;
cin>>list;
// 只关心括号匹配问题，其他字符略过。假设左括号压栈为0
while(list[i]!='\0'){
if(list[i]=='('){
s.push(0);
if(max_deep<++deep)
max_deep=deep;
}
else if(list[i]==')'){
s.pop();
deep--;
}
i++;
}
cout<<"输出"<<max_deep<<endl;

return 0;
}