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

一、单项选择题

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、下面关于B+树的叙述中，错误的是（ ）
A、是多路平衡树
B、可用于文件的索引结构
C、可进行顺序查找
D、关键字指向实际数据块
3、在一个C类地址段内，需要将网络划分为 7个子网，每个子网有15个主机，则将使用哪个子网掩码（ ）
A、255.255.255.224
B、255.255.224
C、255.255.255.240
D、都不是
4、下面输入输出流中面向字符的流是（ ）
A、BufferedWriter
B、FileInputStream
C、ObjectOutputStream
D、OutputStreamWriter
5、以下注解中哪一个表示类或方法已过时（ ）
A、@Override
B、@Overtime
C、@Deprecated
D、@Retention
6、Java中实现Runnable的类的线程执行体应写在什么方法中（ ）
A、重写start()
B、重写run()
C、定义任意方法
D、重写begin()
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、Linux系统下,用什么命令来查看系统进程（ ）
A、df
B、ifconfig
C、netstat
D、ps

二、编程题

1、有一种有趣的字符串价值计算方式:统计字符串中每种字符出现的次数,然后求所有字符次数的平方和作为字符串的价值
例如: 字符串"abacaba",里面包括4个'a',2个'b',1个'c',于是这个字符串的价值为4 * 4 + 2 * 2 + 1 * 1 = 21
牛牛有一个字符串s,并且允许你从s中移除最多k个字符,你的目标是让得到的字符串的价值最小。
2、牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。
最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。
3、牛牛和羊羊非常无聊.他们有n + m个共同朋友,他们中有n个是无聊的,m个是不无聊的。每个小时牛牛和羊羊随机选择两个不同的朋友A和B.(如果存在多种可能的pair(A, B),任意一个被选到的概率相同。),然后牛牛会和朋友A进行交谈,羊羊会和朋友B进行交谈。在交谈之后,如果被选择的朋友之前不是无聊会变得无聊。现在你需要计算让所有朋友变得无聊所需要的时间的期望值。

参考答案

一、
1~5：CDADC
6~10：BCBDD
二、
1、

#include<iostream>
#include<cstdio>
#define LEN (50 + 5)
using namespace std;
int cnt[26];
 
int main()
{
    char str[LEN];
    int len;
    int ans = 0;
    scanf("%s", str);
    for(int i=0; str[i]!=0; i++)
    {
        cnt[str[i] - 'a']++;
    }
    scanf("%d", &len);
    while(len > 0)
    {
        int maxIndex = 0;
        int index = 0;
        for(int i=0; i<26; i++)
        {
            if(cnt[maxIndex] < cnt[i])
                maxIndex = i;
        }
        if(index == maxIndex)
            index++;
        for(int i=0; i<26; i++)
        {
            if(cnt[index] < cnt[i] && maxIndex!=i)
                index = i;
        }
        int cha = cnt[maxIndex] - cnt[index];
        if(cha == 0)
            cha = 1;
        if(len < cha)
            cha = len;
        len -= cha;
        cnt[maxIndex] -= cha;
    }
    for(int i=0; i<26; i++)
        ans += cnt[i] * cnt[i];
    printf("%d\n", ans);
    return 0;
}

2、

#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");
}

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;
}