[数据结构与算法]复试上机题-数据结构

源于《2013年王道论坛计算机考研机试指南》与牛客网计算机考研复试上机题

1.栈的应用

#include<stack>
#include<string.h>
#include<iostream>
using namespace std;
stack<char>S;
char str[101];
int flag[101];
int main(){
    scanf("%s",str);
    int i;
    for(i=0;i<strlen(str);i++){
        if(str[i]=='(')S.push(str[i]);
        if(str[i]==')'&&!S.empty())S.pop();
        else if(str[i]==')'&&S.empty())flag[i]=1;
    }
    if(!S.empty())flag[i-1]=2;
    for(int i=0;i<strlen(str);i++){
        if(flag[i]==1)printf("?");
        else if(flag[i]==2)printf("$");
        else printf(" ");
    }
    return 0;
}

better:

#include<stack>
#include<string.h>
#include<iostream>
using namespace std;
stack<char>S;
char str[101];
char flag[101];
int main(){
    scanf("%s",str);
    int i;
    for(i=0;i<strlen(str);i++){
        if(str[i]=='('){
            S.push(i);
            flag[i]=' ';
        }else if(str[i]==')'){
            if(!S.empty()){
                S.pop();
                flag[i]=' ';
            }else{
                flag[i]='?';
            }
        }else{
            flag[i]=' ';
        }
    }
    while(!S.empty()){
        flag[S.top()]='$';
        S.pop();
    }
    printf("%s",flag);
    return 0;
}

KY129 简单计算器

★★KY102 计算表达式

#include<stack>
#include<string.h>
#include<iostream>
using namespace std;
stack<float>number;
stack<char>op;
int getlevel(char op){
    if(op=='*'||op=='/'){
        return 3;
    }else if(op=='+'||op=='-'){
        return 2;
    }else if(op=='$'){
        return 1;
    }else return 0;
}
float cal(float a,float b,char op){
    if(op=='+')return a+b;
    else if(op=='-')return b-a;
    else if(op=='*')return a*b;
    else if(op=='/')return b/a;
}
int main(){
    string str;

    cin>>str;
    op.push('#');
    str+='$';
    for(int i=0;i<str.size();){
        if(str[i]>='0'&&str[i]<='9'){
            float num=0;
            while(str[i]>='0'&&str[i]<='9'){
                num=num*10+str[i]-'0';
                i++;
            }
            number.push(num);
        }else{
            if(getlevel(op.top())<getlevel(str[i]))op.push(str[i++]);
            else{
                char ope=op.top();
                op.pop();
                float a=number.top();
                number.pop();
                float b=number.top();
                number.pop();
                number.push(cal(a,b,ope));
            }
        }
    }
    printf("%.0f\n",number.top());
    number.pop();
    return 0;
}

KY180 堆栈的使用

2.哈夫曼树

KY188 哈夫曼树

#include<iostream>
#include<algorithm>
using namespace std;
int num[1001];
int main(){
    int n,sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&num[i]);
    }
    sort(num,num+n);
    for(int i=1;i<n;i++){
        num[i]=num[i]+num[i-1];
        sum+=num[i];
        sort(num+i,num+n);
    }
    printf("%d\n",sum);
}

better:

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> >Q;
int main(){
    int n,sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        Q.push(x);
    }
    while(Q.size()>1){
        int a=Q.top();
        Q.pop();
        int b=Q.top();
        Q.pop();
        Q.push(a+b);
        sum+=a+b;
    }
    printf("%d\n",sum);
}

KY179 搬水果

同上

3.二叉树

★★KY212 二叉树遍历

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
struct Node{
    Node *lchild;
    Node *rchild;
    char c;
}Tree[50];
int loc=0;
char str1[30],str2[30];
Node* create(){
    Tree[loc].lchild=Tree[loc].rchild=NULL;
    return &Tree[loc++];
}
Node* build(int s1,int e1,int s2,int e2){
    Node* tmp=create();
    tmp->c=str1[s1];
    int root=0;
    for(int i=s2;i<=e2;i++){
        if(str1[s1]==str2[i]){
            root=i;
            break;
        }
    }
    if(root!=s2){
        tmp->lchild=build(s1+1,s1+(root-s2),s2,root-1);
    }
    if(root!=e2){
        tmp->rchild=build(s1+(root-s2)+1,e1,root+1,e2);
    }
    return tmp;
}
void postOrder(Node *tmp){
    if(tmp->lchild!=NULL)postOrder(tmp->lchild);
    if(tmp->rchild!=NULL)postOrder(tmp->rchild);
    printf("%c",tmp->c);
}
int main(){
    while(scanf("%s",&str1)!=EOF){
        scanf("%s",&str2);
        int len1=strlen(str1);
        int len2=strlen(str2);
        postOrder(build(0,len1-1,0,len2-1));
        printf("\n");
    }
    return 0;
}

KY85 二叉树

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int tree[1010];
int cal(int m,int n){
    if(m<=n)return 1+cal(m*2,n)+cal(m*2+1,n);
    else return 0;
}
int main(){
    int m,n;
    while(scanf("%d %d",&m,&n)!=EOF){
        int sum=0,pos=0;
        if(m==0&&n==0)break;
        printf("%d",cal(m,n));
    }
    return 0;
}

KY194 树查找

#include<iostream>
#include<cmath>
#include<string.h>
using namespace std;
int pos[1010];
int main(){
    int n,d,st,len;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        pos[i]=x;
    }
    scanf("%d",&d);
    st=exp2(d-1)-1;
    len=exp2(d-1)<n?exp2(d-1):n;
    if(st>n){
        printf("EMPTY");
    }else{
        for(int i=st;i<st+len-1;i++){
            printf("%d ",pos[i]);
        }
        printf("%d",pos[st+len-1]);
    }
    return 0;
}

4.二叉排序树

★KY223 二叉排序树

#include<iostream>
#include<algorithm>
using namespace std;
struct Node{
    Node* lchild;
    Node* rchild;
    int id;
}Tree[110];
int loc=0,cur=0;
Node* create(){
    Tree[loc].lchild=Tree[loc].rchild=NULL;
    return &Tree[loc++];
}
Node* build(Node* tmp,int x){
    if(tmp==NULL){
        tmp=create();
        tmp->id=x;
        return tmp;
    }else if(x<tmp->id){
        tmp->lchild=build(tmp->lchild,x);
    }else if(x>tmp->id){
        tmp->rchild=build(tmp->rchild,x);
    }
    return tmp;
}
void inOrder(Node* tmp){
    if(tmp==NULL)return;
    if(cur--){
        printf("%d ",tmp->id);
    }else{
        printf("%d",tmp->id);
    }
    if(tmp->lchild!=NULL)inOrder(tmp->lchild);
    if(tmp->rchild!=NULL)inOrder(tmp->rchild);
}
void midOrder(Node* tmp){
    if(tmp==NULL)return;
    if(tmp->lchild!=NULL)midOrder(tmp->lchild);
    if(cur--){
        printf("%d ",tmp->id);
    }else{
        printf("%d",tmp->id);
    }
    if(tmp->rchild!=NULL)midOrder(tmp->rchild);
}
void postOrder(Node* tmp){
    if(tmp==NULL)return;
    if(tmp->lchild!=NULL)postOrder(tmp->lchild);
    if(tmp->rchild!=NULL)postOrder(tmp->rchild);
    if(cur--){
        printf("%d ",tmp->id);
    }else{
        printf("%d",tmp->id);
    }
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        Node* root=NULL;
        loc=0;
        for(int i=0;i<n;i++){
            int x;
            scanf("%d",&x);
            root=build(root,x);
        }
        cur=n-1;
        inOrder(Tree);
        printf("\n");
        cur=n-1;
        midOrder(Tree);
        printf("\n");
        cur=n-1;
        postOrder(Tree);
        printf("\n");
    }
    return 0;
}

★KY207 二叉排序树

#include<iostream>
#include<algorithm>
using namespace std;
struct Node{
    Node* lchild;
    Node* rchild;
    int id;
}Tree[110];
int loc=0;
Node* create(){
    Tree[loc].lchild=Tree[loc].rchild=NULL;
    return &Tree[loc++];
}
Node* build(Node* tmp,int x,int father){
    if(tmp==NULL){
        tmp=create();
        tmp->id=x;
        printf("%d\n",father);
        return tmp;
    }else if(x<tmp->id){
        tmp->lchild=build(tmp->lchild,x,tmp->id);
    }else if(x>tmp->id){
        tmp->rchild=build(tmp->rchild,x,tmp->id);
    }
    return tmp;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        Node* root=NULL;
        loc=0;
        for(int i=0;i<n;i++){
            int x;
            scanf("%d",&x);
            root=build(root,x,-1);
        }
    }
    return 0;
}

★★KY124 二叉搜索树

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
struct Node{
    Node* lchild;
    Node* rchild;
    int id;
}Tree[110];
int loc=0,len1=0,len2=0;
char str[25],s1[25],s2[25];
char* st;
int* len;
Node* create(){
    Tree[loc].lchild=Tree[loc].rchild=NULL;
    return &Tree[loc++];
}
Node* build(Node* tmp,int x){
    if(tmp==NULL){
        tmp=create();
        tmp->id=x;
        return tmp;
    }else if(x<tmp->id){
        tmp->lchild=build(tmp->lchild,x);
    }else if(x>tmp->id){
        tmp->rchild=build(tmp->rchild,x);
    }
    return tmp;
}
void inOrder(Node* tmp){
    if(tmp==NULL)return;
    st[(*len)++]=tmp->id+'0';
    if(tmp->lchild!=NULL)inOrder(tmp->lchild);
    if(tmp->rchild!=NULL)inOrder(tmp->rchild);
}
void midOrder(Node* tmp){
    if(tmp==NULL)return;
    if(tmp->lchild!=NULL)midOrder(tmp->lchild);
    st[(*len)++]=tmp->id+'0';
    if(tmp->rchild!=NULL)midOrder(tmp->rchild);
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        scanf("%s",&str);
        Node* root=NULL;
        loc=0;
        for(int i=0;i<strlen(str);i++){
            root=build(root,str[i]-'0');
        }
        st=s1;
        len1=0;
        len=&len1;
        inOrder(root);
        midOrder(root);
        for(int i=0;i<n;i++){
            scanf("%s",&str);
            Node* tmp=NULL;
            loc=0;
            for(int i=0;i<strlen(str);i++){
                tmp=build(tmp,str[i]-'0');
            }
            st=s2;
            len2=0;
            len=&len2;
            inOrder(tmp);
            midOrder(tmp);
            if(strcmp(s1,s2)==0)printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}