2010年机试真题
1．输入一串整数，输入命令排序！
输入a t在这串整数后面添加整数t，
输入c\m\n有n替换m，
输入d t删除t，
输入s排序。
#include
#include
#include
#include
using namespace std;
int main(){
vector data;
vector::iterator i;
string t;
cout<
cin>>t;
while(t!=”#”){
int r=0,j=0;
while(t[j]!=’\0′){
r=r*10+t[j]-‘0’;
j++;
}
data.push_back(r);
cin>>t;
}
//操作
cout<
while(cin>>t){
//添加的情况
if(t[0]==’a’){
int num;
cin>>num;
//在末尾添加数字
data.push_back(num);
}
//修改的情况
else if(t[0]==’c’){
int j=2,num1=0,num2=0;
//提取数字
while(t[j]!=’\\’){
num1=num1*10+t[j++]-‘0’;
}
j++;
while(t[j]!=’\0′){
num2=num2*10+t[j++]-‘0’;
}
//替换
for(i=data.begin();i!=data.end();i++)
if(*i==num1){
data.erase(i);
data.insert(i,num2);
}
}
//删除的情况
else if(t[0]==’d’){
int num;
cin>>num;
for(i=data.begin();i!=data.end();i++)
if(*i==num)
data.erase(i);
}
//排序的情况
else if(t[0]==’s’){
sort(data.begin(),data.end());
}
else{
cout<
}
//输出
for(i=data.begin();i!=data.end();i++)
cout<
cout<
}
return 0;
}
2.输入表达式，输出值。
即中缀表达式求值：先将中缀表达式转化为后缀表达式，然后再求值。
#include
#include
#include
#include
using namespace std;
/**
*输入中缀表达式，转化为计算机可以计算的后缀表达式，即逆波兰表达式。
*定义运算符的优先级次序依次是+、-、*、/、(、)，权值越大，优先级越高
*在栈顶时的优先级别
* int op_pri_s[6]={1,1,2,2,0,0};
*在字符串中的优先级别
* int op_pri_q[6]={1,1,2,2,3,0};
*/
/**
* ()输入是英文的符号，记得调好输入法，我因为这个调了半个小时bug
*/
//判定栈顶优先级权值的函数
int psta(string opt){
char op[6]={‘+’,’-‘,’*’,’/’,'(‘,’)’};
int op_pri_s[6]={1,1,2,2,0,0};
for(int i=0;i<6;i++)
if(opt[0]==op[i])
return op_pri_s[i];
}
//判定字符串中优先级权值的函数
int pstr(char opt){
char op[6]={‘+’,’-‘,’*’,’/’,'(‘,’)’};
int op_pri_q[6]={1,1,2,2,3,0};
for(int i=0;i<6;i++)
if(opt==op[i])
return op_pri_q[i];
}
int main(){
stack s;
queue q;
string data;
cin>>data;
//转后缀表达式
int i=0;
while(data[i]!=’\0′){
string t=””;
//如果是运算符时
if(data[i]==’+’||data[i]==’-‘||data[i]==’*’||data[i]==’/’||data[i]=='(‘||data[i]==’)’){
//栈空，直接压栈
if(s.empty()){
t+=data[i++];
s.push(t);
t=””;
}
//栈顶运算符优先级较高
else if(psta(s.top())>=pstr(data[i])){
// ***可能多次弹栈，直到字符串的运算符，优先级较高
while(psta(s.top())>=pstr(data[i])){
if((data[i]==’)’&&s.top()==”(“))
break;
q.push(s.top());
s.pop();
//防止栈空，造成空指针异常
if(s.empty())
break;
}
//括号匹配的情况，!s.empty()防止栈空，造成空指针异常
if(!s.empty()&&data[i]==’)’&&s.top()==”(“){
i++;
s.pop();
}
else{
t+=data[i++];
s.push(t);
t=””;
}
}
//字符串运算符优先级较高
else{
t+=data[i++];
s.push(t);
t=””;
}
}
//如果是数字
else
{
//提取数字
while(data[i]!=’+’&&data[i]!=’-‘&&data[i]!=’*’&&data[i]!=’/’&&data[i]!='(‘&&data[i]!=’)’&&data[i]!=’\0′){
t+=data[i++];
}
//直接入队
q.push(t);
t=””;
}
}
//把栈弹空
while(!s.empty()){
q.push(s.top());
s.pop();
}
//测试输出后缀表达式
/*while(!q.empty()){
cout<
q.pop();
}
cout<
//计算，还得用到栈。遇到数字压栈，遇到运算符弹出栈顶两个数字，进行计算。
double a=0,b=0;
stack st;
while(!q.empty()){
string d=q.front();
q.pop();
if(d==”+”){
b=st.top();
st.pop();
a=st.top();
st.pop();
st.push(a+b);
}
else if(d==”-“){
b=st.top();
st.pop();
a=st.top();
st.pop();
st.push(a-b);
}
else if(d==”*”){
b=st.top();
st.pop();
a=st.top();
st.pop();
st.push(a*b);
}
else if(d==”/”){
b=st.top();
st.pop();
a=st.top();
st.pop();
st.push(a/b);
}
else{
double temp=0;
int k=0,
flag=0; //小数部分的标志
//提取数字
while(d[k]!=’\0′){
if(d[k]==’.’){
k++;
flag=10;
continue;
}
if(flag){
temp=temp+(d[k++]-‘0’)/(flag/1.0);
flag*=10;
}
else{
temp=temp*10+d[k++]-‘0’;
}
}
st.push(temp);
}
}
cout<
return 0;
}
2011年机试真题
1.输入一组单词(区分大小写)，统计首字母相同的单词个数，相同的单词不累加，输出格式：“字母，个数”
#include
#include
#include
using namespace std;
int main()
{
set s;
map m;
string str;
while(cin>>str)
{
s.insert(str);
}
set::iterator it;
for(it=s.begin(); it!=s.end(); it++)
{
++m[(*it)[0]];
}
map::iterator mit;
for(mit=m.begin(); mit!=m.end(); mit++)
{
cout<first<second<
}
return 0;
}
2.输入一组单词(区分大小写)，输出其字典排序
#include
#include
#include
using namespace std;
int main()
{
int n=0;
string a[105],s;
while(cin>>s)
{
if(s==”0″)
break;
else
a[n++]=s;
}
sort(a,a+n);
for(int i=0;i
cout<
return 0;
}
3．给一个字符串(aaaa(bbbb(cccc，dddd)，eeee(ffff)))该字符串表明的是各个人的层次关系。比如aaaa是bbbb和eeee的领导，bbbb是cccc和dddd的领导。先输入一个名称，比如ffff，要求输出其领导关系，输出aaaa>eeee>ffff。
#include
#include
using namespace std;
int main()
{
//(aaaa(bbbb(cccc,dddd),eeee(ffff)))
int n=0;
string s,str[105],t;//str为字符串栈
cin>>s>>t;
for(int i=0; i
{
if(s[i]=='(‘)
{
str[n++]=s[i];
}
else if(s[i]==’,’)//遇到逗号时将逗号和前一个左括号之间的内容删除
{
for(int k=n-1; k>=0; k–)
{
if(str[k]!=”(“)
n–;
else if(str[k]==”(“)
{
break;
}
}
}
else if(s[i]==’)’)//遇到右括号将右括号和前一个左括号之间的内容和左括号删除
{
for(int k=n-1; k>=0; k–)
{
if(str[k]!=”(“)
n–;
else if(str[k]==”(“)
{
n–;
break;
}
}
}
else//字母或数字
{
int j;
string tt=””;
for(j=i; j
{
if((s[j]>=’a’&&s[j]<=’z’)||(s[j]>=’A’&&s[j]<=’Z’))
tt+=s[j];
else
{
str[n++]=tt;
break;
}
}
if(tt==t)//找到目标字符串则退出循环
break;
i=j-1;
}
}
for(int i=0; i
{
if(str[i]!=”(“)
{
if(str[i]!=t)
cout<“;
else
cout<
}
}
cout<
return 0;
}