笔试时间：2022年8月7日

1 单选

1）OSI七层模型中，在哪一层设置校验点，可以在通信失效后恢复通信？

2）线程的六种状态：就绪、备用、运行、等待、转换、终止（六种状态之间如何转换的）

3）多路复用技术（介质、信道什么的）

4）多版本读的一致性问题（没听说过）

5）FCB文件控制块中有哪些信息

6）char[]的strlen和sizeof

char s[] = "123456\0abcdef"
strlen(s)  // 6  返回的是123456的长度，因为字符串从\0被截断了
sizeof(s)  // 14  返回的是数组的size，包括字符串最后没有显式表示的\0

7）

int fun(int x, int y)
{
    static int t = 5;
    t += (++x) + y;
    return t;
}

int main()
{
    int x = 3;
    int y = 4;
    cout << fun(x, y) << x;
    cout << fun(x, y) << x;
    return 0;
}

2 多选

1）SQL语句

2）进线程区别

3）广播式网络特点

4）虚电路和数据报（分组交换）

5）加密与访问控制

6）磁盘调度与磁盘分配

3 编程题

1）计算队列中史莱姆的种类个数

史莱姆有六种，a b c d e f

3中操作：

1 字母：入队已知种类为该字母的史莱姆

2：队头出队一只史莱姆

3：输出当前队列中史莱姆的种类个数

输入：

操作次数

操作*操作次数

输出：

每当有操作3时进行输出

输入用例1：

8
3
1 a
3
1 b
3
2
1 c
3
1 b
3

输出用例1：

0
1
2
2
2

我的AC代码：

#include <iostream>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;

queue<char> theQueue;
unordered_map<char, int> theMap;
int ans = 0;

int main()
{
    int q;  // 操作次数
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        char str;
        cin >> str;
        if (str == '1')
        {
            char tmp;
            cin >> tmp;
            theQueue.push(tmp);
            if (theMap.count(tmp) == 0)  // 目前还没有记录过当前种类史莱姆
            {
                theMap[tmp] = 1;
                ans++;
            }
            else  // 记录过当前种类史莱姆
            {
                if (theMap[tmp] == 0)
                    ans++;
                theMap[tmp]++;
            }

        }
        else if (str == '2')
        {
            char current = theQueue.front();
            theQueue.pop();
            theMap[current]--;
            if (theMap[current] == 0)
                ans--;
        }
        else  // str[0] == 3
        {
            cout << ans << endl;
        }
    }
    return 0;
}

2）跳石头

从0号开始按序号1、2、3……n跳石头，每跳一步加30分，跳不了或者跳到最后一个石头则终止，输出得分。最开始处在0号石头上

跳不了的情况：石头间的距离超过了最大跳跃距离、当前跳跃距离的使用次数不足

输入：

石头个数 最大跳跃距离

i 和 i-1 号石头之间的距离（例如1 2 3代表从0到1号石头距离1，从1到2号石头距离2，从2号到3号石头距离3）

每一种跳跃距离最多的使用次数（例如3 2 1代表跳跃距离为1的跳跃只能跳3次，跳跃距离为2的跳跃只能跳2次，跳跃距离为3的跳跃只能跳1次）

输出：

得分

输入用例1：

5 1
1 1 1 1 1
3

输出用例1：

90

用例1说明：

从0号跳到1号石头，可以跳，跳跃距离为1的次数使用1次，小于等于3次的限制，得分+30

从1号跳到2号石头，可以跳，跳跃距离为1的次数使用2次，小于等于3次的限制，得分+30

从2号跳到3号石头，可以跳，跳跃距离为1的次数使用3次，小于等于3次的限制，得分+30

从3号跳到4号石头，跳跃距离为1的次数使用4次，大于3次的限制，跳不了，游戏结束，最终得分90

输入用例2：

6 6
1 1 4 5 1 4
8 1 0 9 7 5

输出用例2：

180

用例2说明：

从0号跳到1号石头，可以跳，跳跃距离为1的次数使用1次，小于等于8次的限制，得分+30

从1号跳到2号石头，可以跳，跳跃距离为1的次数使用2次，小于等于8次的限制，得分+30

从2号跳到3号石头，可以跳，跳跃距离为4的次数使用1次，小于等于9次的限制，得分+30

从3号跳到4号石头，可以跳，跳跃距离为5的次数使用1次，小于等于7次的限制，得分+30

从4号跳到5号石头，可以跳，跳跃距离为1的次数使用3次，小于等于8次的限制，得分+30

从5号跳到6号石头，可以跳，跳跃距离为4的次数使用2次，小于等于9次的限制，得分+30，到达最后一个石头，游戏结束，最终得分180

我的AC代码：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

unordered_map<int, int> restCountOfDiffSteps;

int main()
{
    int countOfStones;
    int maxStep;
    cin >> countOfStones >> maxStep;
    vector<int> distanceOfStones;
    for (int i = 0; i < countOfStones; i++)
    {
        int currentDistance;
        cin >> currentDistance;
        distanceOfStones.push_back(currentDistance);
    }
    for (int i = 1; i <= maxStep; i++)
    {
        int maxCountOfCurrentStep;
        cin >> maxCountOfCurrentStep;
        restCountOfDiffSteps[i] = maxCountOfCurrentStep;
    }


    int ans = 0;
    for (int i = 0; i < distanceOfStones.size(); i++)
    {
        int currentTargetDistance = distanceOfStones[i];
        if (currentTargetDistance > maxStep)  // 如果跳不到下一个目标
        {
            cout << ans << endl;
            break;
        }
        else
        {
            if (restCountOfDiffSteps[currentTargetDistance] <= 0)  // 剩余可跳跃次数不足
            {
                cout << ans << endl;
                break;
            }
            else
            {
                restCountOfDiffSteps[currentTargetDistance]--;
                ans += 30;
                if (i == distanceOfStones.size() - 1)
                {
                    cout << ans << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

3）寻找abb模式的路径

在一个树中寻找abb模式的路径的个数，即连通的三个结点中，1号结点和2号结点字母值不同，2号结点和3号结点字母值相同。结点之间由无向边连接

输入：

结点个数

字母序列

相互连接的结点*n对

输出：

abb模式的路径个数

输入用例1：

5
aabba
1 2
2 3
3 4
3 5

输出用例1：

3

说明：

       (1)a
       /
     (2)a
     /
   (3)b
  /    \
(4)b  (5)a

3-2-1 baa

2-3-4 abb

5-3-4 abb

————————
后续：已寄