爱奇艺秋季校招算法工程师（第二场）-2018年

一、单项选择题

1、下面关于B+树的叙述中，错误的是（ ）

A、是多路平衡树

B、可用于文件的索引结构

C、可进行顺序查找

D、关键字指向实际数据块

2、以下关于贝叶斯网络和马尔科夫网络说法正确的是（ ）

A、贝叶斯网络是有向图， 而马尔科夫网络是无向图

B、贝叶斯网络和马尔科夫网络都是无向图， 只是网络结构差别

C、贝叶斯网络和马尔科夫网络都是有向图， 只是网络结构差别

D、贝叶斯网络为无向图， 而马尔科夫网络是有向图

3、在设计模式中，应该优先使用_____关系从而实现复用（ ）

A、委派

B、继承

C、创建

D、都不对

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

A、255.255.255.224

B、255.255.224

C、255.255.255.240

D、都不是

5、以下哪个方法不是用于模型选择的（ ）

A、交叉验证

B、AIC

C、BIC

D、维特比算法

6、关于以下目标函数说法错误的是（ ）

A、当λ为无穷大的时候， f(x)为线性函数

B、当λ为0， 则f(x)为任意能完全拟合样本点的函数

C、对于一般的λ而言，存在最优解，最优解为自然三次样条曲线（natural cubic spline）

D、对于一般的λ而言， 存在最优解， f(x)为线性函数

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

A、ping

B、ifconfig

C、telnet

D、netstat

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

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

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

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

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

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

A、O(n^3)

B、O(nlogn)

C、O(n)

D、O(n^2)

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

A、23

B、24

C、25

D、26

二、编程题

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

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

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

3、牛牛得到一个长度为n的整数序列V,牛牛定义一段连续子序列的幸运值为这段子序列中最大值和次大值的异或值(次大值是严格的次大)。牛牛现在需要求出序列V的所有连续子序列中幸运值最大是多少。请你帮帮牛牛吧。

参考答案

一、

1~5：DAAAD

6~10：DCBDC

二、

1、

#include<stdio.h>
int dp[10],n,x,i,j;
int main(){
    for(i=1;i<10;i++){
        int flag=0;
        for(j=1;j<=i;j*=4)
            if(dp[i-j]==0) flag=1;
        dp[i]=flag;
    }
    for(scanf("%d",&n),i=0;i<n;i++)
        scanf("%d",&x),printf("%s\n",dp[x%10]?"niu":"yang");
}

2、

#include<stdio.h>
double f[100];
int main()
{
    int yes,no,all;
    scanf("%d%d",&yes,&no);
    all=yes+no;
    double pos=(double)all*(all-1)/2;
    for(int i=1;i<=no;i++)
    {
        int n=i,y=all-i;
        double c1=((double)y*(y-1)/2)/pos;
        double c2=(double)y*n/pos;
        double c3=((double)n*(n-1)/2)/pos;
        f[i]+=c2*(f[i-1]+1);
        if(i>=2) f[i]+=c3*(f[i-2]+1);
        f[i]+=c1;
        f[i]=f[i]/(1-c1);
    }
    printf("%.1lf",f[no]);
    return 0;
}

3、

#include<stdio.h>
#include<stack>
#include<algorithm>
using namespace std;
int main(){
    int n,i,res=0,x;
    stack<int> s;
    for(scanf("%d",&n),i=0;i<n;i++){
        scanf("%d",&x);
        while(s.size()&&s.top()<=x)
            res=max(res,x^s.top()),s.pop();
        if(s.size()) res=max(res,x^s.top());
        s.push(x);
    }
    printf("%d\n",res);
}