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

一、单项选择题

1、当分配给一个进程的页面数增加时，页故障数可能增大也可能变小，下述算法符合这种情况的是（ ）
A、FIFO算法
B、LRU算法
C、Clock算法
D、LFU算法
2、在Linux系统中哪个程序是特定的时间上安排特定的作业或者程序的运行（ ）
A、vi
B、Outlook
C、Scheduler
D、cron
3、下面代码的输出结果是什么（ ）

#include <iostream>
using namespace std;
class A
{   
    public: void virtual f() 
    {      
        cout << "A" << " ";
    }
};
class B : public A
{   
    public: void virtual f()
    {      
        cout << "B" << " ";
    }
};
int main(){
    A *pa = new A();
    pa->f();
    B *pb=(B *)pa;
    pb->f();    
    delete pa, pb;
    pa=new B();
    pa->f();
    pb=(B *)pa;
    pb->f();
    return 0;
}

A、A A B A
B、A B B A
C、A A B B
D、A A A B
4、一个提供NAT服务的路由器在转发一个源IP地址为10.0.0.1、目的IP地址为131.12.1.1的IP分组时，可能重写的IP分组首部字段是（ ）
Ⅰ.TTL
Ⅱ.片偏移量
Ⅲ.源IP地址
Ⅳ.目的IP地址
A、仅Ⅰ
B、仅I、Ⅱ
C、仅Ⅰ、Ⅱ、III
D、Ⅰ、Ⅱ、Ⅲ、Ⅳ
5、sql中，可以用来替换DISTINCT的语句是（ ）
A、ORDER BY
B、GROUP BY
C、DESC
D、HAVING
6、在32位计算机中，下面输出是多少（ ）

#include <iostream>
using namespace std;
typedef enum
{
    Char ,
    Short,
    Int,
    Double,
    Float,
}TEST_TYPE;
int main() {
    TEST_TYPE val;
    cout<< sizeof(val)<<endl;
        return 0;
}

A、5
B、4
C、8
D、12
7、以下程序中，当输入6个字符后，容器的当前大小(size)是多少（ ）

int main()
{
    vector<char> vec;
    vec.reserve(1024);
    string tmp;
    cin >> tmp;
    string::iterator it = tmp.begin();
    for(; it!=tmp.end(); it++)
    {
    vec.push_back(*it);
    }
    vec.resize(vec.size() +vec.size()/2);
    return 0;
}

A、6
B、9
C、1024
D、1536
8、对于字符串"ABCDADA"的二进制哈夫曼编码有多少位（ ）
A、11
B、12
C、13
D、14
9、下面关于选择排序说法正确的是（ ）
A、每扫描一遍数组，需要多次交换
B、选择排序是稳定的排序方法,因为时间复杂度是固定的O（n^2）
C、选择排序排序速度一般要比冒泡排序快
D、空间复杂度为O（1）
10、设置tcp的哪个socket参数会影响了 nagle算法（ ）
A、TCP_MAXSEG
B、TCP_KEEPALIVE
C、TCP_SYNCNT
D、TCP_NODELAY

二、编程题

1、牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。牛牛想知道他最少需要涂染几个正方形。
如样例所示: s = RGRGR
我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案。
2、牛牛养了n只奶牛,牛牛想给每只奶牛编号,这样就可以轻而易举地分辨它们了。 每个奶牛对于数字都有自己的喜好,第i只奶牛想要一个1和x[i]之间的整数(其中包含1和x[i])。
牛牛需要满足所有奶牛的喜好,请帮助牛牛计算牛牛有多少种给奶牛编号的方法,输出符合要求的编号方法总数。
3、如果一个数字满足以下条件,我们就称它为奇异数:
(1)、这个数字至少有两位
(2)、这个数的最低两位是相同的
比如: 1488是一个奇异数,而3、112不是。
牛牛现在给出一个一个区间[L,R],让你计算出在区间内有多少个奇异数

参考答案

一、
1~5：ADCCB
6~10：BBCDD
二、
1、

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    while (cin >> str) {
        int n = str.size();
        vector<int> R(n + 2, 0), G(R);
        for (int i = 1; i <= n; i++)
            G[i] = G[i - 1] + (str[i - 1] == 'G');
        for (int i = n; i > 0; i--)
            R[i] = R[i + 1] + (str[i - 1] == 'R');
        int ans = n;
        for (int i = 0; i <= n; i++)
            ans = min(ans, G[i] + R[i + 1]);
        cout << ans << endl;
    }
    return 0;
}

2、

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(){
    int n;
    long long sum=1;
    cin>>n;
    vector<int> vec(n,0);
    for(int i=0;i<n;++i){
        cin>>vec[i];
    }
    sort(vec.begin(),vec.end());
    int cnt=0;
    for(int i=0;i<n;++i){
        sum=(sum*(vec[i]-cnt))%1000000007;
        ++cnt;
    }
    cout<<sum<<endl;
     
    return 0;
}

3、

#include <iostream>
using namespace std;
int main()
{
    long L, R;
    long res = 0;
    cin >> L >> R;
    if (L > R)
        return 0;
    long tmpl = (L / 10 + 1) * 10;
    long tmpr = (R / 10 ) * 10;
    long num = (tmpr - tmpl)/10;
    res += num;
    if ((L % 10) <= (L / 10 % 10))
        res += 1;
    if ((R % 10) >= (R / 10 % 10))
        res += 1;
 
    cout << res << endl;
    return 0;
}