2018爱奇艺秋季校招C++工程师（第二场）

一、单项选择题

1、下列SQL语句用法错误的是（ ）

A、delete from table-name where null=null

B、truncate table table-name

C、alter table table-name add column id int

D、select * from table-name where 3>4

2、有如下的函数定义

int Xfun(int *a, int n){
int x=*a;
for(int *pa=a+1; pa<a+n;pa++)
    if(*pa>x) 
        x=*pa;
    return x;
}

若执行了语句

int x[5]={23,46,78,55,16};

后，通过表达式Xfun(x,5)调用该函数，则得到的返回值为（ ）

A、55

B、78

C、23

D、16

3、在一个C类地址段内，需要将网络划分为 7个子网，每个子网有15个主机，则将使用哪个子网掩码 （ ）

A、255.255.255.224

B、255.255.224

C、255.255.255.240

D、都不是

4、以下选项中可能发生隐式类型转换的是（ ）

A、long 到 int

B、int 到 float

C、int 到 char

D、unsigned int 到 int

5、以下函数调用会选择哪个重载函数（ ）

func(1,2);

A、int func(int a)

B、int func(int a, char b);

C、int func(int a, float b);

D、int func(int a, char *b);

6、Linux下哪个命令可以用于判断host1主机是否能够访问host2主机的端口（ ）

A、ping

B、ifconfig

C、telnet

D、netstat

7、以下关于操作系统，说法错误的是（ ）

A、用管程实现进程同步时，管程中的过程是不可中断的

B、多道程序的执行失去了封闭性和再现性，因此多道程序系统不需要封闭性和再现性

C、使用SPOOLING技术可以实现虚拟设备

D、当 CPU 处于管态时，它可以执行计算机系统中的全部指令

8、有一个算法的递推关系式为：T(n) = 9 T(n / 3) + n，则该算法的时间复杂度为（ ）

A、O(n^3)

B、O(nlogn)

C、O(n)

D、O(n^2)

9、由下面5个点:1,1,2,3,5构成的哈夫曼树的带权路径长度为（ ）

A、23

B、24

C、25

D、26

10、若一颗二叉树的前序遍历为a,b,c,d,后序遍历为b,c,d,a,那么它的中序遍历为（ ）

A、b a c d

B、b a d c

C、a b c d

D、a b d c

E、不确定，因为不唯一

二、编程题

1、如果一个整数只能被1和自己整除,就称这个数是素数。

如果一个数正着反着都是一样,就称为这个数是回文数。例如:6, 66, 606, 6666

如果一个数字既是素数也是回文数,就称这个数是回文素数

牛牛现在给定一个区间[L, R],希望你能求出在这个区间内有多少个回文素数。

2、牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。

最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。

3、牛牛和羊羊非常无聊.他们有n + m个共同朋友,他们中有n个是无聊的,m个是不无聊的。每个小时牛牛和羊羊随机选择两个不同的朋友A和B.(如果存在多种可能的pair(A, B),任意一个被选到的概率相同。),然后牛牛会和朋友A进行交谈,羊羊会和朋友B进行交谈。在交谈之后,如果被选择的朋友之前不是无聊会变得无聊。现在你需要计算让所有朋友变得无聊所需要的时间的期望值。

参考答案

一、

1~5：CBABB

6~10：CBDCE

二、

1、

#include <iostream>
#include <cmath>
#include <algorithm>
#include <sstream>
 
using namespace std;
 
bool f(int a){
    if(a==2)
        return false;
    bool flag=true,flag1=true;
    for(int i=2;i<=sqrt(a);++i){
        if(a%i==0){
            flag=false;
            break;
        }
    }
    string str,temp;
    stringstream ss;
    ss<<a;
    ss>>str;
    temp=str;
    reverse(str.begin(),str.end());
    if(temp!=str)
        flag1=false;
    return flag&&flag1;
}
 
int main(){
    int L,R;
    cin>>L>>R;
    int sum=0;
    for(int i=L;i<=R;++i){
        if(f(i))
            ++sum;
    }
    cout<<sum<<endl;
     
    return 0;
}

2、

#include <iostream>
using namespace std;
  
int main()
{
    int n;
    cin >> n;
    int i = n, temp = 0;
    while(i--)
    {
        cin >> temp;
        if(temp == 1)
        {
            cout << "niu"<< endl;
            continue;
        }
        int left = (temp - 1) % 5;
        switch(left)
        {
            case 1:
            case 4:
                cout << "yang"<< endl;
                break;
            default:
                cout << "niu"<< endl;
                break;
        }
    }
}

3、

#include<stack>
#include<algorithm>
#include <iostream>
#include <iomanip>
  
using namespace std;
#define maxn 55
float dp[maxn];
int n,m;
float p1(int x,float deno){
    return (n+x)*(m-x) / deno;
}
float p2(int x,float deno){
    return (m-x)*(m-x-1)/2.0f/deno;
}
float p3(int x,float deno){
    return (n+x)*(n+x-1)/2.0f/deno;
}
int main(){
  
    while(cin >> n >> m){
        float deno = (n+m)*(n+m-1) / 2.0f;
        for(int i = 0;i < maxn;i ++){
            dp[i] = 0.0f;
        }
        for(int i = m-1;i >=0;i --){
            dp[i] += (dp[i+1]+1)*p1(i,deno) + p3(i,deno);
            if(i+2 <=m){
                dp[i] += p2(i,deno) * (dp[i+2] + 1);
            }
            dp[i] /= (1-p3(i,deno));
        }
        cout << setiosflags(ios::fixed) << setprecision(1) << dp[0] << endl;
    }
    return 0;
}