吉林大学考研复试题目（牛客网）

Kindear

发布于 2019-09-29 14:40:02

1.2K0

发布于 2019-09-29 14:40:02

文章被收录于专栏：算法与数据结构算法与数据结构

吉林大学考研复试题目（牛客网）

1.字符串的反码

题目描述

一个二进制数，将其每一位取反，称之为这个数的反码。下面我们定义一个字符的反码。如果这是一个小写字符，则它和字符'a’的距离与它的反码和字符'z’的距离相同；如果是一个大写字符，则它和字符'A’的距离与它的反码和字符'Z’的距离相同；如果不是上面两种情况，它的反码就是它自身。举几个例子，'a’的反码是'z’；'c’的反码是'x’；'W’的反码是'D’；'1’的反码还是'1’；'

('的反码还是')

'。一个字符串的反码定义为其所有字符的反码。我们的任务就是计算出给定字符串的反码。

输入描述:

    输入每行都是一个字符串，字符串长度不超过 80 个字符。如果输入只有!，表示输入结束，不需要处理。

输出描述:

对于输入的每个字符串，输出其反码，每个数据占一行。

示例1

输入

复制

Hello 
JLU-CCST-2011 
!

输出

复制

Svool 
QOF-XXHG-2011

分析：简单的数位运算

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s;
    while(cin>>s){
        if(s[0]=='!'){
            break;
        }
        else{
            //正常输入
            int len = s.length();
            string ansstr="";
            for(int i = 0; i < len;i++ ){
                if(s[i]>='a'&&s[i]<='z'){
                    ansstr += 'z' - (s[i]-'a');

                }else if(s[i]>='A'&&s[i]<='Z')
                {
                    ansstr += 'Z' - (s[i]-'A');
                }
                else{
                    ansstr+=s[i];
                }
            }
            cout<<ansstr<<endl;
        }
    }
}

2.三角形的边

题目描述

给定三个已知长度的边，确定是否能够构成一个三角形，这是一个简单的几何问题。我们都知道，这要求两边之和大于第三边。实际上，并不需要检验所有三种可能，只需要计算最短的两个边长之和是否大于最大那个就可以了。这次的问题就是：给出三个正整数，计算最小的数加上次小的数与最大的数之差。

输入描述:

每一行包括三个数据a, b, c，并且都是正整数，均小于10000。

输出描述:

对于输入的每一行，在单独一行内输出结果s。s=min(a,b,c)+mid(a,b,c)-max(a,b,c)。上式中，min为最小值，mid为中间值，max为最大值。

示例1

输入

复制

1 2 3

输出

复制

题目分析：简单排序

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int> num;
    int a,b,c;
    while(cin>>a>>b>>c){
        //输入
        num.push_back(a);
        num.push_back(b);
        num.push_back(c);
        sort(num.begin(),num.end());
        int ans = num[0] + num[1] - num[2];
        cout<<ans<<endl;
        num.clear();
    }
}

3.怪异的洗牌

题目描述

对于一副扑克牌，我们有多种不同的洗牌方式。一种方法是从中间某个位置分成两半，然后相交换，我们称之为移位（shift）。比如原来的次序是123456，从第4个位置交换，结果就是561234。这个方式其实就是数组的循环移位，为了多次进行这个操作，必须使用一种尽可能快的方法来编程实现。在本题目中，还引入另外一种洗牌方式，就是把前一半（如果总数是奇数，就是(n-1)/2）牌翻转过来，这种操作称之为翻转（flip）。在前面shift操作的结果上进行flip，结果就是165234。当然，如果是实际的扑克牌，直接翻转会造成正反面混在一起的，我们就不管那么多了。给定n张牌，初始次序为从1到n，经过若干次的shift和flip操作后，结果会是什么样？

输入描述:

输入包括多组测试数据，每组数据的第一行包括两个数 n和k。n表示牌的数目，1<n<1000，k表示下面要进行的操作数量。随后的k行，每行一个整数x，1<=x<=n，表示从第几个位置开始移位。在每一次shift操作后都接一个flip操作。

输出描述:

对于输入的每组数据，计算经过给定的k次shift和flip操作后，各个位置的数值。并按次序在一行上输出所有牌张的值，每个数值（不包括最后一个）后面有一个空格。

示例1

输入

复制

6 1
4

输出

复制

1 6 5 2 3 4

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n,k;
vector<int> num;
void shift(int pos)
{
    reverse(num.begin(),num.begin()+pos);
    reverse(num.begin()+pos,num.end());
    reverse(num.begin(),num.end());
    //多次反转 实现移位效果
}
void filp()
{
    reverse(num.begin(),num.begin()+num.size()/2);
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        num.clear();
        for(int i=1;i<=n;i++)
        {
            num.push_back(i);
        }
        while(k--)
        {
            int pos;
            scanf("%d",&pos);
            shift(pos);
            filp();
        }
        for(int i=0;i<n;i++){
            cout<<num[i]<<" ";
        }
    }
}

4.连通图

题目描述

给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。

输入描述:

    每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。

输出描述:

    对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。

示例1

输入

复制

输出

复制

NO
YES

#include<bits/stdc++.h>//并查集解决
using namespace std;
const int maxn = 1010;
int maps[maxn][maxn];
int n,m;
int father[maxn];
int findfather(int x){
    return x==father[x]?x:findfather(father[x]);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        
            memset(maps,0,sizeof(maps));
            for(int i=1;i<=n;i++){
                father[i] = i;
            }
            while(m--){
                int a,b;
                scanf("%d%d",&a,&b);
                int fa = findfather(a);
                int fb = findfather(b);
                if(fa <= fb){
                    father[b] = fa;
                }else{
                    father[a] = fb;
                }
            }
            int counts = 0;
            for(int i=1;i<=n;i++){
                if(father[i] == i){
                    counts++;
                }
            }
            if(counts > 1){
                cout<<"NO"<<endl;
            }else{
                cout<<"YES"<<endl;
            }
        
    }
}

5.排列与二进制

题目描述

在组合数学中，我们学过排列数。从n个不同元素中取出m（m<=n）个元素的所有排列的个数，叫做从n中取m的排列数，记为p(n, m)。具体计算方法为p(n, m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)! (规定0!=1).当n和m不是很小时，这个排列数是比较大的数值，比如 p(10,5)=30240。如果用二进制表示为p(10,5)=30240=( 111011000100000)b，也就是说，最后面有5个零。我们的问题就是，给定一个排列数，算出其二进制表示的后面有多少个连续的零。

输入描述:

输入包含多组测试数据，每组测试数据一行。
每行两个整数，n和m，0<m<=n<=10000，n=0标志输入结束，该组数据不用处理。

输出描述:

对于每个输入，输出排列数p(n, m)的二进制表示后面有多少个连续的零。每个输出放在一行。

示例1

输入

复制

10 5
6 1
0 0

输出

复制

5
1

解析：

判断末尾几个连续的 0 就是判断可以连续/2的次数

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    int n,m;
    int ans = 0;
    int sum = 1;
    while(~scanf("%d%d",&n,&m)&&n!=0)
    {
        for(int i=n-m+1;i<=n;i++)
        {
            sum*=i;
            while(sum%2==0&&sum!=0)
            {
                sum/=2;
                ans++;
            }
        }
        cout<<ans<<endl;
    }
}

6.平方因子

题目描述

给定一个数n，判定它是否有一个不为1的完全平方数因子。也就是说，是否存在某个k，k>1，使得k*k能够整除n。

输入描述:

每行一个整数n，1<n<10000

输出描述:

对于每一个输入的整数，在单独的一行输出结果，如果有不为1的完全平方数因子，则输出Yes，否则输出No。请注意大小写。

示例1

输入

复制

输出

复制

No

解析：使用个数值筛

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int numShell[1010];//数值
void init()
{
    for(int i=2;i<=33;i++){
        numShell[i] = i*i;
    }
}
int main()
{
    init();
    int n;
    scanf("%d",&n);
    int i;
    for(i=2;i<=32;i++){
        if(n%numShell[i] == 0){
            cout<<"Yes"<<endl;
            break;
        }
    }
    if(i==33){
        cout<<"No"<<endl;
    }
}

7.数字之和

题目描述

对于给定的正整数 n，计算其十进制形式下所有位置数字之和，并计算其平方的各位数字之和。

输入描述:

每行输入数据包括一个正整数n(0<n<40000)

输出描述:

对于每个输入数据，计算其各位数字之和，以及其平方值的数字之和，输出在一行中，之间用一个空格分隔，但行末不要有空格。

示例1

输入

复制

输出

复制

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    LL n;
    while(~scanf("%lld",&n)){
        int firstans = 0;
        int secondans = 0;
        LL tmp = n;
        while(tmp){
            firstans+=(tmp%10);
            tmp/=10;
        }
        LL stmp = n*n;
        while(stmp){
            secondans+=(stmp%10);
            stmp/=10;
        }
        cout<<firstans<<" "<<secondans<<endl;
    }
}

7.搬水果

题目描述

在一个果园里，小明已经将所有的水果打了下来，并按水果的不同种类分成了若干堆，小明决定把所有的水果合成一堆。每一次合并，小明可以把两堆水果合并到一起，消耗的体力等于两堆水果的重量之和。当然经过 n‐1 次合并之后，就变成一堆了。小明在合并水果时总共消耗的体力等于每次合并所耗体力之和。假定每个水果重量都为 1，并且已知水果的种类数和每种水果的数目，你的任务是设计出合并的次序方案，使小明耗费的体力最少，并输出这个最小的体力耗费值。例如有 3 种水果，数目依次为 1，2，9。可以先将 1，2 堆合并，新堆数目为3，耗费体力为 3。然后将新堆与原先的第三堆合并得到新的堆，耗费体力为 12。所以小明总共耗费体力=3+12=15，可以证明 15 为最小的体力耗费值。

输入描述:

    每组数据输入包括两行,第一行是一个整数 n(1<=n<=10000),表示水果的种类数。第二行包含 n 个整数，用空格分隔，第 i 个整数(1<=ai<=1000)是第 i 种水果的数目。

输出描述:

对于每组输入，输出一个整数并换行，这个值也就是最小的体力耗费值。输入数据保证这个值小于 2^31。

示例1

输入

复制

3
9 1 2

输出

复制

解析：本质就是huffman树

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
priority_queue<int,vector<int>,greater<int>> Q; //升序优先队列实现最小堆
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        while(!Q.empty())Q.pop();
        for(int i=0;i<n;++i)
        {
            int x;
            scanf("%d",&x);
            Q.push(x);
        }
        int ans=0;
        while(Q.size()>1){
            int a=Q.top();
            Q.pop();
            int b=Q.top();
            Q.pop();
            ans+=a+b;
            Q.push(a+b);
        }
        printf("%d\n",ans);
    }
    return 0;
}

8.堆栈的使用

分析模拟题

题目描述

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。Push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。

输入描述:

     对于每组测试数据，第一行是一个正整数 n，0<n<=10000(n=0 结束)。而后的 n 行，每行的第一个字符可能是'P’或者'O’或者'A’；如果是'P’，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是'O’，表示将栈顶的值 pop 出来，如果堆栈中没有元素时，忽略本次操作；如果是'A’，表示询问当前栈顶的值，如果当时栈为空，则输出'E'。堆栈开始为空。

输出描述:

    对于每组测试数据，根据其中的命令字符来处理堆栈；并对所有的'A’操作，输出当时栈顶的值，每个占据一行，如果当时栈为空，则输出'E’。当每组测试数据完成后，输出一个空行。

示例1

输入

复制

3
A
P 5
A
4
P 3
P 6
O 
A

输出

复制

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    int n;
    while(~scanf("%d",&n)&&n!=0){
        stack<int> tmp;
        while(!tmp.empty()) tmp.pop();
        char ch;
        for(int i=0;i<n;i++){
            cin>>ch;
            if(ch=='A'){
                if(tmp.empty()){
                    cout<<"E"<<endl;
                }else{
                    cout<<tmp.top()<<endl;
                }
            }else if(ch=='P'){
                int t;
                cin>>t;
                tmp.push(t);
            }else if(ch=='O'){
                if(!tmp.empty())
                tmp.pop();
            }
        }
        cout<<endl;
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-08-31 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度