@TOC

前言

准备的有点晚，操作系统和计网还没怎么看，题基本都写了，代码也AC一道，另一道久一点。但是感觉选择题很多都是模棱两可的写的。

把笔试题大概的按照印象记录一下好了。

选择题还是挺麻烦的。蛮多都不确定的。

一、笔试题须知

选择题 22道；编程题2道；时间一个半小时。

开摄像头、录屏、***控；

二、选择题

选择题主要包括了计网、操作系统（RTOS挺多的）、git(晕了）、编译原理（应格是）、语言基础、数据结构问题

1、操作系统问题

主要是RTOS，还有些其他os 问题。

例如：

1. ready ->suspend、ready->run、run->ready、suspend->ready，哪个是不被允许的。

2. 存储系统、页中断问题。

3. cache size 、路数、 block size 、地址空间给定，问要多少tag问题。

还有 IRQ 中断相关问题、中断向量；进程 mutex为1的时候，临界区什么的，记不太清了。

2、计网问题

1. ip地址范围问题。

3、字节对齐问题：我记的有两道

大概是：

struct temp {
    char a1;
    double a2;
    int a3;

};
    cout << sizeof(temp) << endl;

这个考的是对齐double 8字节。

#pragma pack(1)
struct temp {
    int a1:24;
    double a2;
    int a3;
    long long d[0];
};
    cout << sizeof(temp) << endl;

1. 这个考了一个字节对齐、位域、结构体中定义空数组用作缓冲区。

2. 有一道题是给了字节对齐的pack。有一道题没给。然后有个题的int 标明了位域。

3. 规定了一个字节对齐，那就按一个字节对齐来。

结构体中定义空数组用作缓冲区：这样用的

typedef struct buffer_s {
    int    buf_len;
    unsigned char data[0];
} buffer_t;

buffer_t *buf = (buffer_t *)malloc(sizeof(buffer_t) + buf_len);
buf->buf_len = buf_len;

4、数据结构问题

1. 给定二叉树的中序遍历和后序遍历，问哪个是前序遍历。这个简单的。

2. 给定数据入栈，问哪个不能是出栈顺序。画一下就知道 。

5、 语言问题

1. m =5000，n=100；
   外循环m i++ 内循环 n j++ 或者外循环n，内循环m次；然后内部是*2 或者<<1 ;
   问四种组合哪种快。

2. loop 还有哪些，问：生成汇编的问题（不会）；

3. 还有个题返回了局部变量的指针，我选了输出不确定。

4. char * 、const问题

6、 其他

问到了git 的merge 、fetch命令好像。

三、编程题

1、topk；

题目大概是道路绿化。

我理解的题目是：一个城区的绿化问题，每条街道原本绿化水平和居民数不同。n个街道、每条街道都能绿化水平改到m、可以改善k个街道绿化水平；

问：最大居民满意度；

题目意思其实就是每个街道能得到的居民满意度是这个街道的居民数 乘以 绿化增加水平（绿化到m 减去原来绿化水平）；

大概是这么个数据，具体数据不记得了。

下面这个就是一共6个街道、要绿化的都能绿化到10、最多可以绿化3条街。

6 10 3
3 5
1 4
4 6
4 7
5 5
3 7

其实就是topK 问题；数据读进来的时候，把每条街能转到的居民满意度存到k个最大堆中。最后就是堆里的元素相加。

其实简单的就是存起来，排个序，加一下。

2、动归；

题目是动归的题；是<kbd>300. 最长递增子序列</kbd>类问题；抽象成子上升子序列问题；

有点像<kbd>354. 俄罗斯套娃信封问题 </kbd>

我理解的题目是：一条河的南北有n个码头。每个码头都和对岸的一个码头连着。n个航线，然后现在要去掉交叉的航线；

问：剩余航线的最大吞吐量。

给的数据首先是n，然后是n个航线，每条航线带着一个吞吐量。

大概是这么个数据。具体数据不记得了

4
1 3 5
2 1 4
2 4 6
1 4 7

就是找不相交最大吞吐量；还是简单的，想清楚了上升子序列问题就行；

3、总结

编程题一大难点是题目解析。。。我两道题看懂题都花了快十分钟了。题目还蛮长的，也有各种无用信息。需要看题看例子一起理解。