选择题

1、关于java的异常处理机制，以下说法正确的是：

当某个线程抛出OutOfMemoryError时，其他线程有可能不受影响
当大量抛出RuntimeException时，不会影响系统的吞吐量
java.lang.Exception是java.lang.Error的父类
finally块代码一定会被执行

finally块代码并不一定会执行，不是很懂java的try、catch、finally。

2、错误原因：512+256+128+...+1=1023，不要算错

3、关于mysql，下面说法不正确的是：

mysql中的utf8类型最大只支持3个bytes
desc关键字可以作为table的字段名
filesort是通过读取磁盘文件进行排序，会极大降低查询性能
smallint占用2个bytes的存储空间

utf8类型最大只支持3个bytes，utf8mb4类型最大只支持4个bytes。
filesort并非是对磁盘文件进行排序。好像是先对每个缓冲块进行快速排序，然后对各个块进行归并排序。

5、查找表结构用以下哪一项？

DESC

mysql中，查询表结构用DESC，可以显示各列名以及各列的限制（是否主码，是否非空）。

6、如何强制垃圾回收器立即回收一个对象？

调用System.gc()方法
调用Runtime.gc()方法
将对象赋值null
无法强制垃圾回收器立即执行

System.gc()只是提醒垃圾回收器执行，不是强制其执行。

7、关于sleep()和wait()，以下描述错误的一项是？

sleep是Thread类的方法，wait是Object类的方法；
sleep不释放对象锁，wait放弃对象锁；
sleep暂停线程、但监控状态仍然保持，结束后会自动恢复；
wait后进入等待锁定池，只有针对此对象发出notify方法后获得对象锁进入运行状态。

notifyAll方法也可以。

参考资料：sleep()和wait()的区别及wait方法的一点注意事项 - shiki0921 - 博客园

sleep是Thread类的方法，导致此线程暂停执行指定时间，给其他线程执行机会，但是依然保持着监控状态，过了指定时间会自动恢复，调用sleep方法不会释放锁对象。

当调用sleep方法后，当前线程进入阻塞状态。目的是让出CPU给其他线程运行的机会。但是由于sleep方法不会释放锁对象，所以在一个同步代码块中调用这个方法后，线程虽然休眠了，但其他线程无法访问它的锁对象。这是因为sleep方法拥有CPU的执行权，它可以自动醒来无需唤醒。而当sleep结束指定休眠时间后，这个线程不一定立即执行，因为此时其他线程可能正在运行。

wait方法是Object类里的方法，当一个线程执行到wait方法时，它就进入到一个和该对象相关的等待池中，同时释放了锁对象，等待期间可以调用里面的同步方法，其他线程可以访问，等待时不拥有CPU的执行权，否则其他线程无法获取执行权。当一个线程执行了wait方法后，必须调用notify或者notifyAll方法才能唤醒，而且是随机唤醒，若是被其他线程抢到了CPU执行权，该线程会继续进入等待状态。由于锁对象可以是任意对象，所以wait方法必须定义在Object类中，因为Obeject类是所有类的基类。

8、下列协议中，将MAC地址转为IP地址的协议是：

RARP

ARP（Address Resolution Protocol）地址解析协议，是根据IP地址获取物理地址的一个TCP/IP协议。
RARP（Reverse Address Resolution Protocol）是反向地址解析协议。

10、在TCP/IP体系结构中，直接为ICMP提供服务的协议是：

IP

不过啥是ICMP呀。

11、下列关于进程和线程的叙述中，正确的是：

不管系统是否支持线程，进程都是资源分配的基本单位
线程是资源分配的基本单位，进程是调度的基本单位
系统级线程和用户级线程的切换都需要内核的支持
同一进程中的各个线程拥有各自不同的地址空间

B选项：明显线程是用来调度的，进程才是资源分配的。D选项：同一进程的线程贡献这个进程的资源。

12、若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是：

在进程结束时能进行处理机调度
创建新进程后能进行处理机调度
在进程处于临界区时不能进行处理机调度
在系统调用完成并返回用户态时能进行处理机调度

好像是这么理解：B选项：假如一开始没有进程，那么创建新进程完成后就会进行处理机调度。C选项：有时，临界区是类似进程访问打印机之类的外设，在等待外设的过程中造成的。这个时候是可以进行处理机调度的。其他情况不清楚是否可以。

13、关于TCP协议的描述，以下错误的是？

面向连接
可提供多播服务
可靠交付
报文头部长，传输开销大

TCP是连接的、可靠的，UDP是无连接的，不可靠的。（TCP是一个虚拟连接，握手的过程就是为了建立虚拟连接，发送还需要对方进行确认，拥有拥塞控制。UDP是无连接的，只顾自己发送，一直尽力去做好，在一些需要实时性的传输中，UDP可以没这么卡）
TCP仅支持单播，不能提供多播与广播，每次是只面向连接的两台设备的。
TCP加了很多东西，UDP只是简单加了报文头表示这个是UDP协议。

参考资料：
TCP的可靠传输机制_网络_sinat_28557957的博客-CSDN博客
TCP/IP详解之：广播和多播 - 墨城烟雨 - 博客园
怎么理解TCP的面向连接和UDP的无连接（不面向连接）？_网络_infi-CSDN博客
主要看这个：一文搞懂TCP与UDP的区别 - Fundebug - 博客园

15、有关C++程序运行时的函数地址，下列说法正确的是：

每个函数的地址都是固定的，同一个程序重复运行多次，每次函数地址都一样
每个函数的地址是不固定的，但在操作系统版本、硬件版本不变的情况下是固定的，同一个程序重复在相同软硬件环境下运行多次，每次函数地址都一样
地址是否固定要看系统配置和编译选项，如果开启了地址随机化，那地址是每次都变的，如果没开启，那么地址每次都一样
每个函数的地址都是不定的，同一个程序重复运行多次，每次地址都不同

好像地址随机化是为了对抗反汇编的。默认是没有的。

17、关于TCP协议状态描述正确的是

只有执行主动关闭端才会出现TIME_WAIT
当接受到FIN报文时，会进入CLOSING状态
数据传输完成后发送FIN报文后进入TIME_WAIT状态
client和server端最终都会经历TIME_WAIT状态

参考上面的TCP的解除连接的四次挥手。

开始：双方是建立连接状态。

1、客户端发送FIN，自己进入FIN_WAIT状态。并停止自己发送新的数据。

2、服务端接收FIN，自己进入CLOSE_WAIT状态，告诉应用层客户端到服务端的连接已经停止，返回一个ACK。服务端若还有数据发送，客户端依然需要接收。

3、客户端接收ACK，然后还要等待服务端发送剩余的数据。

4、服务端发送数据完毕，发送FIN，自己进入LAST_ACK状态，等待客户端的ACK。

5、客户端接收FIN，返回ACK，进入CLOSE_WAIT状态，然后等待超时（2MSL，两倍最长报文寿命），若没有收到服务器继续发送的FIN（意味着自己返回的ACK丢失了，要重发ACK），则关闭连接。

6、直到服务端收到ACK，关闭连接，否则持续发送FIN。

所以服务器关闭连接会早一点。

【问题1】为什么连接的时候是三次握手，关闭的时候却是四次握手？

答：因为当Server端收到Client端的SYN连接请求报文后，可以直接发送SYN+ACK报文。其中ACK报文是用来应答的，SYN报文是用来同步的。但是关闭连接时，当Server端收到FIN报文时，很可能并不会立即关闭SOCKET，所以只能先回复一个ACK报文，告诉Client端，"你发的FIN报文我收到了"。只有等到我Server端所有的报文都发送完了，才能发送FIN报文，因此不能一起发送。故需要四次握手。

【问题2】为什么TIME_WAIT状态需要经过2MSL(最大报文段生存时间)才能返回到CLOSE状态？

答：虽然按道理，四个报文都发送完毕，可以直接进入CLOSE状态了，但是必须假想网络是不可靠的，有可能最后一个ACK丢失。所以TIME_WAIT状态就是用来重发可能丢失的ACK报文。在Client发送出最后的ACK回复，但该ACK可能丢失。Server如果没有收到ACK，将不断重复发送FIN片段。所以Client不能立即关闭，它必须确认Server接收到了该ACK。Client会在发送出ACK之后进入到TIME_WAIT状态。Client会设置一个计时器，等待2MSL的时间。如果在该时间内再次收到FIN，那么Client会重发ACK并再次等待2MSL。所谓的2MSL是两倍的MSL(Maximum Segment Lifetime)。MSL指一个片段在网络中最大的存活时间，2MSL就是一个发送和一个回复所需的最大时间。如果直到2MSL，Client都没有再次收到FIN，那么Client推断ACK已经被成功接收，则结束TCP连接。

参考资料：(5条消息)TCP的三次握手与四次挥手理解及面试题（很全面）_网络_lucky_jun-CSDN博客

18、关于epoll和select的区别，哪个说法是错误的？

epoll和select都是I/O多路复用的技术，都可以实现同时监听多个I/O事件的状态。
epoll相比select效率更高，主要是基于其操作系统支持的I/O事件通知机制，而select是基于轮询机制。
epoll支持水平触发和边沿触发两种模式。
select能并行支持I/O比较小，且无法修改。

完全不懂这是什么。

编程题

21、尺取/二分

小明最近在做病毒自动检测，他发现，在某些library 的代码段的二进制表示中，如果包含子串并且恰好有k个1，就有可能有潜在的病毒。library的二进制表示可能很大，并且子串可能很多，人工分析不可能，于是他想写个程序来先算算到底有多少个子串满足条件。如果子串内容相同，但是开始或者结束位置不一样，则被认为是不同的子串。

注：子串一定是连续的。例如"010"有6个子串，分别是 "0, "1", "0", "01", "10", "010"。

数据范围：1<=n<=1e6, 0<=k<=1e6

题解：很明显的一个尺取的题目，尺取的步骤是用l和r框住恰好k个1，然后数向左向右的全0分别有多少个。需要注意的是k=0的时候要另外处理。搞得好像很多细节的样子，早知道直接二分就可以了，枚举每个左端点，然后在前缀和上面二分找出差分为k的一段，这一段都是可行的。或者对连续的0进行压缩，对于每个1，存放其右侧的连续的0的数量。然后特殊处理一下第一个1的左侧，每次就是k个1直接尺取，不需要太多情况。

char s[1000005];
 
void test_case() {
    int n, k;
    scanf("%d%s", &k, s + 1);
    n = strlen(s + 1);
    if(k > n) {
        puts("0");
        return;
    }
    if(k == 0) {
        ll ans = 0;
        int cnt = 0;
        for(int i = 1; i <= n; ++i) {
            if(s[i] == '0')
                ++cnt;
            else {
                ans += 1ll * cnt * (cnt + 1) / 2;
                cnt = 0;
            }
        }
        ans += 1ll * cnt * (cnt + 1) / 2;
        printf("%lld\n", ans);
        return;
    }
    int cnt = 0;
    for(int i = 1; i <= n; ++i)
        cnt += (s[i] == '1');
    if(cnt < k) {
        puts("0");
        return;
    }
    ll ans = 0;
    int l = 1, r = 0;
    cnt = 0;
    while(1) {
        while(l <= n && s[l] == '0')
            ++l;
        if(l > n)
            break;
        //printf("[%d,%d] cnt=%d\n", l, r, cnt);
        if(r == 0) {
            r = l;
            cnt = 1;
        }
        //printf("[%d,%d] cnt=%d\n", l, r, cnt);
        while(r + 1 <= n && cnt + (s[r + 1] == '1') < k) {
            ++r;
            cnt += (s[r] == '1');
        }
        if(r + 1 <= n && s[r + 1] == '1' && cnt + 1 == k) {
            ++r;
            cnt += (s[r] == '1');
        }
        //printf("[%d,%d] cnt=%d\n", l, r, cnt);
        if(cnt == k) {
            int pre0 = 0, suf0 = 0;
            int pl = l - 1, pr = r + 1;
            while(pl >= 1 && s[pl] == '0') {
                ++pre0;
                --pl;
            }
            while(pr <= n && s[pr] == '0') {
                ++suf0;
                ++pr;
            }
            ans += 1ll * (pre0 + 1) * (suf0 + 1);
            //printf("l=%d r=%d\n", pre0, suf0);
        }
        cnt -= (s[l] == '1');
        ++l;
    }
    printf("%lld\n", ans);
}

23、dp

给定一组石头，每个石头有一个正数的重量。每一轮开始的时候，选择两个石头一起碰撞，假定两个石头的重量为x，y，x<=y,碰撞结果为：

1. 如果x==y，碰撞结果为两个石头消失
2. 如果x!=y，碰撞结果两个石头消失，生成一个新的石头，新石头重量为y-x

最终最多剩下一个石头为结束。求解最小的剩余石头质量是多少。

数据范围：所有石头的重量总和不超过10000。

题解：并不是每次取出最大的两个贪心，这样会WA，正解是dp。注意到消除石头的过程，非常像是给其中小的那个加负号，大的那个加正号，然后整体作为一个结果放回去。意思就是最终只需要给这些数字定正负，然后求这个值的绝对值的最小值。可以用个滚动数组记录dp[i][j]为前i个石头是否能组合出重量j，dp完成之后，得到一个全部石头的重量sum，对于可以组合出的重量j（dp[n][j]为true），就尝试用abs(j-(sum-j))更新答案。

24、暴力

在你面前有n个蓄水池，他们组成了树形结构（由n-1条边连接）。蓄水池节点编号从1开始到n。对每个蓄水池节点来说，他的儿子蓄水池节点都摆放在他的下面，并且和它用水管相连，根据重力，水会向下流动。现在我们要在蓄水池上做一些操作：

1. 把节点v填满水。然后v的所有儿子节点水也会被填满。
2. 清空节点v的水。然后v所有的父亲节点水都会被清空。
3. 询问每个蓄水池节点是否有水。
   初始状态时候，每个节点都是空的。
   现在我们会依次进行一系列操作，我们想提前知道每次操作后的结果，你能帮忙解决吗？

数据范围：n<=1000

题解：看样例瞎猜树的根是1，然后写个dfs暴力更新。假如n变得更大，树剖的 \(O(nlog^2n)\) 肯定是可行的一种方案，但是有没有可能进行树上差分呢？感觉是不行的。