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

一、单项选择题

1、若图G采用邻接表存储，邻接表中有奇数个表结点，下列选项正确的是（ ）

A、G中有奇数个顶点

B、G中有偶数个顶点

C、G为无向图

D、G为有向图

2、SVM模型通过最大化边界实现线性分类， 以下哪个可以使得SVM实现非线性分类（ ）

A、kernel

B、松弛变量

C、对偶空间求解

D、SMO算法

3、以下关于过拟合和欠拟合说法正确的是（ ）

A、过拟合一般表现为偏差较大

B、欠拟合一般表现为方差较大

C、过拟合可以通过减少变量来缓解

D、欠拟合可以通过正则化来解决

4、以下算法属于有监督算法的是（ ）

A、LDA（latent dirichlet allocation）

B、PLSA（probabilistic latent semantic analysis）

C、knn

D、SOM(Self-Organizing Maps)

5、某文件系统采用链接存储方式，文件A在磁盘中存放的情况如图所示。

若该文件所在的目录文件已经在内存中，要读取文件块2，需要访问磁盘的次数为（ ）

A、1次

B、2次

C、3次

D、4次

6、以下哪种排序算法在最坏情况下的时间复杂度最小（ ）

A、冒泡排序

B、选择排序

C、归并排序

D、插入排序

7、两台主机A和B已建立了TCP连接，A始终以MSS=1KB大小的段发送数据，并一直有数据发送；B每收到一个数据段都会发出一个接收窗口为9KB的确认段。

若A在T时刻发生超时时拥塞窗口为8KB，则从T时刻起，不再发生超时的情况下，经过10个RTT后，A的发送窗口是（ ）

A、8KB

B、9KB

C、10KB

D、11KB

8、设栈S初始状态为空。元素1,2,3,4,5,6依次通过栈S，若出栈的顺序为4,6,5,3,2,1，则栈S的容量至少应该为（ ）

A、3

B、4

C、5

D、6

9、在Linux系统中，因为某些原因造成了一些进程变成孤儿进程，那么这些孤儿进程会被以下哪一个系统进程接管（ ）

A、sshd

B、init

C、top

D、syslogd

10、在软件开发中，经典的模型就是瀑布模型，下列关于瀑布模型的说法正确的是（ ）

A、瀑布模型具由于良好的灵活性

B、瀑布模型采用结构化的分析与设计方法，将逻辑实现与物理实现分开

C、瀑布模型的核心是按照软件开发的时间顺序将问题简化

D、利用瀑布模型，如果发现问题则修改的代价很低

二、编程题

1、一个完整的括号字符串定义规则如下:

(1)、空字符串是完整的。

(2)、如果s是完整的字符串，那么(s)也是完整的。

(3)、如果s和t是完整的字符串，将它们连接起来形成的st也是完整的。

例如，"(()())", ""和"(())()"是完整的括号字符串，"())(", "()(" 和 ")"是不完整的括号字符串。

牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。

2、牛牛选择了一个正整数X,然后把它写在黑板上。然后每一天他会擦掉当前数字的最后一位,直到他擦掉所有数位。 在整个过程中,牛牛会把所有在黑板上出现过的数字记录下来,然后求出他们的总和sum.

例如X = 509, 在黑板上出现过的数字依次是509, 50, 5, 他们的和就是564.

牛牛现在给出一个sum,牛牛想让你求出一个正整数X经过上述过程的结果是sum.

3、牛牛学习了冒泡排序,并写下以下冒泡排序的伪代码,注意牛牛排序的数组a是从下标0开始的。

BubbleSort(a):
   Repeat length(a)-1 times:
       For every i from 0 to length(a) - 2:
           If a[i] > a[i+1] then:
                Swap a[i] and a[i+1]

牛牛现在要使用上述算法对一个数组A排序。

在排序前牛牛允许执行最多k次特定操作(可以不使用完),每次特定操作选择一个连续子数组,然后对其进行翻转,并且k次特定操作选择的子数组不相交。

例如A = {1, 2, 3, 4, 5, 6, 7}, k = 1,如果牛牛选择的子数组是[2,4](注意下标从0开始),那么翻转之后的数组变为A = {1, 2, 5, 4, 3, 6, 7}。

牛牛知道冒泡排序的效率一定程度上取决于Swap操作次数,牛牛想知道对于一个数组A在进行k次特定操作之后,再进行上述冒泡排序最少的Swap操作次数是多少?

参考答案

一、

1~5：DACCC

6~10：CBCBB

二、

1、

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
char s[100];
int dp[100][100],i,j,n,k;
int main(){
    scanf("%s",s),n=strlen(s);
    for(i=n-1;i>=0;i--)
        for(j=i;j<n;j++)
            if(i==j) dp[i][j]=1;
            else if(i+1==j){
                if(s[i]=='('&&s[j]==')') dp[i][j]=0;
                else dp[i][j]=2;
            }else{
                dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
                if(s[i]=='('&&s[j]==')')
                    dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
                for(k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
    printf("%d\n",dp[0][n-1]);
}

2、

#include<stdio.h>
long long getSum(long long);
int main(){
    long long sum,l,r,mid;
    //freopen("input.txt","r",stdin);
    scanf("%lld",&sum);
    for(l=0,r=sum;l+1<r;){
        mid=l+(r-l)/2;
        if(getSum(mid)==sum){
            printf("%lld",mid);
            return 0;
        }else if(getSum(mid)<sum) l=mid;
        else r=mid;
    }
    if(getSum(l)==sum) printf("%lld",l);
    else if(getSum(r)==sum) printf("%lld",r);
    else printf("-1");
}
long long getSum(long long x){
    long long sum=0;
    while(x!=0) sum+=x,x/=(long long)10;
    return sum;    
}

3、

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=55;
int getCnt(vector<int> A,int x){
    int n=A.size(),cnt=0;
    for(int i=x;i<n;i++)
        for(int j=0;j<i;j++)
            if(A[j]>A[i]) cnt++;
    return cnt;
}
int n,dp[maxn][maxn],k,K,i,j;
int main(){
    scanf("%d%d",&n,&K);
    vector<int> A(n);
    for(i=0;i<n;i++) scanf("%d",&A[i]);
    for(i=n-1;i>=0;i--)
        for(k=0;k<=K;k++){
            vector<int> tmp1(A.begin(),A.begin()+i+1);
            dp[i][k]=getCnt(tmp1,i)+dp[i+1][k];
            if(k>=1){
                for(j=i+1;j<n;j++){
                    vector<int> tmp2(A.begin(),A.begin()+j+1);
                    reverse(tmp2.begin()+i,tmp2.begin()+j+1);
                    dp[i][k]=min(dp[i][k],getCnt(tmp2,i)+dp[j+1][k-1]);
                }
            }
        }
    printf("%d",dp[0][K]);
}