Java 笔试选择题知识点记录【aly-0910】

今日大败。

甲乙 TCP 连接

问：甲给乙的报文段中，seq=100，ack=101，问乙给甲的回复中，seq=?，ack=?

• 序列号：在建立连接时由计算机生成的随机数作为其初始值，通过 SYN 包传给接收端主机，每发送一次数据，就「累加」一次该「数据字节数」的大小。用来解决网络包乱序问题。
• 确认应答号：指下一次「期望」收到的数据的序列号，发送端收到这个确认应答以后可以认为在这个序号以前的数据都已经被正常接收。用来解决丢包的问题。

所以在回复中，ack = 100 + 1 = 101，seq= 任意。

三次握手

大致流程如下：

1. 客户端向服务器发送一个SYN=J
2. 服务器向客户端响应一个SYN=K，并对SYN J进行确认ACK=J+1
3. 客户端再想服务器发一个确认ACK=K+1

四次挥手

大致流程如下：

1. 某个应用进程首先调用close主动关闭连接，这时TCP发送一个FIN=M；
2. 另一端接收到FIN=M之后，执行被动关闭，对这个FIN进行确认。它的接收也作为文件结束符传递给应用进程，因为FIN的接收意味着应用进程在相应的连接上再也接收不到额外数据；
3. 一段时间之后，接收到文件结束符的应用进程调用close关闭它的socket。这导致它的TCP也发送一个FIN=N；
4. 接收到这个FIN的源发送端TCP对它进行确认。
5. 这样每个方向上都有一个FIN和ACK。

循环扫描调度算法

目前处于 120，朝着序号变小的地方运行。

80 100 60 140 110 => 110 100 80 60 140

例:假定某磁盘共有200个柱面，编号为0-199，如果在为访问143号柱面的请求者服务后，当前正在为访问125号柱面的请求服务，同时有若干请求者在等待服务，它们每次要访问的柱面号为 86，147，91，177，94，150，102，175，130

1、先来先服务算法（FCFS）First Come First Service

这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。

先来先服务 （125）86.147.91.177.94.150.102.175.130

2、最短寻道时间优先算法（SSTF） Shortest Seek Time First

该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。

最短寻道时间优先（125）130.147.150.175.177.102.94.91.86

3、扫描算法（SCAN）电梯调度

扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。

电梯调度（125）102.94.91.86.130.147.150.175.177

4、循环扫描算法（CSCAN）

循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。

循环扫描 （125）130.147.150.175.177.86.91.94.102

参考：https://dashen.tech/2020/02/15/%E5%9B%9B%E7%A7%8D%E5%B8%B8%E7%94%A8%E7%9A%84%E7%A3%81%E7%9B%98%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95/

哈夫曼树，已知度数为D，叶子节点数目为M，问非叶子节点数目？

D = 3, M = 62

非叶子节点数目 = (叶子节点数目 - 1) / (度数 - 1)

在这个问题中，度数为3，叶子节点数目为62，所以非叶子节点数目可以计算如下：

非叶子节点数目 = (62 - 1) / (3 - 1) = 61 / 2 = 30.5

由于哈夫曼树的非叶子节点数目必须是整数，所以需要向下取整。所以，在这个情况下，非叶子节点数目为30个。

Linux 指向目录的有？

soft link ？ hard link ？

1. 符号链接（Symbolic Links）：也称为软链接，是一种特殊的文件，它包含了对另一个文件或目录的引用。符号链接可以跨越文件系统边界，并且可以链接到任何地方。创建符号链接的命令是ln -s，例如：ln -s /source/directory /link/to/directory。
2. 硬链接（Hard Links）：硬链接是文件系统中的多个目录项，它们指向相同的文件数据块。硬链接通常不能用于目录，因为会涉及到循环引用问题。

小根堆

将 12 14 18 4 9 26 28 30 16 22 依次插入到初始为空的小根堆 H 中，H = ？

1. 初始时，堆为空，将第一个元素（12）插入堆中。H = [12]
2. 接下来插入元素14，插入后需要维护小根堆的性质。H = [12, 14]
3. 插入元素18，同样需要维护小根堆的性质。H = [12, 14, 18]
4. 插入元素4，同样需要维护小根堆的性质。H = [4, 12, 18, 14]
5. 插入元素9，维护小根堆。H = [4, 9, 18, 14, 12]
6. 插入元素26，维护小根堆。H = [4, 9, 18, 14, 12, 26]
7. 插入元素28，维护小根堆。H = [4, 9, 18, 14, 12, 26, 28]
8. 插入元素30，维护小根堆。H = [4, 9, 18, 14, 12, 26, 28, 30]
9. 插入元素16，维护小根堆。H = [4, 9, 16, 14, 12, 26, 28, 30, 18]
10. 最后插入元素22，维护小根堆。H = [4, 9, 16, 14, 12, 26, 28, 30, 18, 22]

现在，堆H就是包含所有这些元素的小根堆，其中每个节点的值都小于或等于其子节点的值。

MySQL 的模糊查询

A name like '%cat%dog%'

B name like '%_%'

C name regexp "^.{5}$"

D name regexp "[wW]"

解释：

SQL的模式匹配允许你使用“_”匹配任何单个字符，而“%”匹配任意数目字符（包括零个字符）。在MySQL中，SQL的模式缺省是忽略大小写的。注意：在你使用SQL模式时，你不能使用=或!=；而使用LIKE或NOT LIKE比较操作符。

A. name like '%cat%dog%'：这个查询将匹配包含"cat"和"dog"之间的任意字符序列的name列的值。%表示零个或多个字符。

B. name like '%_%'：这个查询将匹配name列中包含至少一个字符的任意值，其中_表示单个字符，而%表示零个或多个字符。

C. name regexp "^.{5}$"：这个查询使用正则表达式匹配，要求name列的值必须是恰好包含5个字符的字符串。^表示字符串的开始，.{5}表示匹配任意5个字符，$表示字符串的结束。

D. name regexp "[wW]"：这个查询将匹配包含小写字母"w"或大写字母"W"的name列的值。正则表达式中的[wW]表示匹配字符"w"或"W"中的任何一个。

路由信息协议（RIP）

A 优先选择跳数少的路径

B 每个子网的子网掩码不必相同

C 网络可达的最大距离是 16

D 遇到故障可以很快收敛

RIP是一种基于距离矢量（Distance-Vector）算法的协议，它使用跳数（Hop Count）作为度量值来衡量到达目的地址的距离。在RIP网络中,RIP协议要求网络中每一台路由器都要维护从自身到每一个目的网络的路由信息。RIP协议使用跳数来衡量网络间的“距离”：从一台路由器到其直连网络的跳数定义为1，从一台路由器到其非直连网络的距离定义为每经过一个路由器则距离加1。“距离”也称为“跳数”RIP允许路由的最大跳数为15，因此，16即为不可达。可见RIP协议只适用于小型网络。

解释：RIP（Routing Information Protocol）是一种距离向量路由协议，通常用于小型网络。以下是对每个选项的解释：

• A 优先选择跳数少的路径：正确。RIP使用跳数作为度量标准，优先选择跳数最少的路径来进行路由。
• B 每个子网的子网掩码不必相同：错误。在RIP中，每个子网的子网掩码必须相同，否则可能会导致路由问题。
• C 网络可达的最大距离是 16：错误。RIP的最大跳数为15。
• D 遇到故障可以很快收敛：错误。RIP可以在遇到故障时进行路由收敛，但由于它的工作原理是周期性地广播路由更新，收敛速度相对较慢，尤其在大型网络中。其他高级路由协议如OSPF和EIGRP通常能更快地进行路由收敛。

扩充内存的方法

A. 多道程序环境下，可用覆盖与交换来扩充内存：正确。在多道程序设计环境下，覆盖和交换是两种常用的内存扩充技术。覆盖是指将部分程序加载到内存中，当需要执行其他程序时，覆盖掉先前的程序。交换是指将整个进程从内存移到外部存储（如硬盘），以便为其他进程腾出内存空间。

B. 覆盖技术下，用户空间分为固定区和覆盖区：正确。在覆盖技术中，用户程序的内存空间通常分为一个固定区和若干个覆盖区。固定区包含在内存中一直存在的程序部分，而覆盖区包含需要覆盖或替换的部分。

C. 覆盖技术下，活跃内存放在固定区：正确。将经常活跃的部分放在固定区，其余部分按调用关系分段。首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段。

D. 交换技术，有换入和换出两道程序：正确。交换技术涉及将进程从内存中换出到外部存储（换出），以为其他进程腾出内存空间，并将进程从外部存储加载到内存中（换入），以便执行。这是一种常见的内存管理方法，以确保系统中同时运行的进程不超出可用内存的限制。

进程调度

"剥夺式"（preemptive）和 "非剥夺式"（non-preemptive）是两种不同的调度策略，用于操作系统中管理和分配进程的执行时间。

1. 剥夺式调度（Preemptive Scheduling）：剥夺式调度允许操作系统在一个正在执行的进程还没有完成时，将CPU的控制权剥夺（取走），并分配给另一个高优先级的进程。这通常通过硬件定时器（例如，时钟中断）实现，以确保操作系统可以定期检查和重新安排进程。剥夺式调度具有更好的响应时间，可以有效地处理紧急任务。但它也可能引入一些额外的开销，因为切换进程需要保存和恢复上下文。
2. 非剥夺式调度（Non-preemptive Scheduling）：非剥夺式调度允许一个进程一旦获得CPU的控制权就一直运行，直到自愿释放CPU或完成任务。在这种情况下，操作系统不会强制中断正在运行的进程。非剥夺式调度通常用于简单的系统，其优势在于减少了上下文切换的开销。然而，如果一个进程变得不响应或进入无限循环，可能会导致其他进程无法获得CPU的机会。

选择剥夺式还是非剥夺式调度策略取决于系统的要求和性能目标。剥夺式调度更适合需要快速响应和优先级管理的系统，而非剥夺式调度可能更适用于简单的系统，其中上下文切换的开销要小得多。不同的操作系统和应用场景可能会选择不同的调度策略。

笔试

我太菜了，就做出来第二题。/(ㄒoㄒ)/~~

第一题：p数组表示排列的位置，pos 数组表示 p 数组对应的数组，a 数组是排列的子序列，问交换p的相邻数，需要多少次能使得 a 不是优秀数组？优秀数组是相邻 idx 表示的数 i -1, i，令m = pos[a[i - 1]]，n = pos[a[i]]，满足 0 < n - m <= d。

举例：p = [3,2,4,5,1]，pos = [5,2,1,3,4]，a = [3,4]，则交换p中的4 和5 即可。

参考：https://www.nowcoder.com/discuss/530410267595784192?sourceSSR=search

第二题：求相邻数的最大差值 if (a[i - 1] >= a[i]) else continue。

第三题：模拟。

法一：

import java.util.*;

public class ALiYun0910 {
    public static void main(String[] args) {
        ALiYun0910 solution = new ALiYun0910();
        System.out.println(extracted(4,4,2).equals("bbababaa"));
        System.out.println(extracted(2,6,2).equals("bbabbabb"));
        System.out.println(extracted(6,2,2).equals("aabaabaa"));
        System.out.println(extracted(3,5,2).equals("bbabbaba"));
        System.out.println(extracted(2,4,2).equals("bbabba"));
        System.out.println(extracted(1,5,2).equals("-1"));
    }

    private static String extracted(int a, int b, int k) {
        if ((a > (b + 1) * k) || (b > (a + 1) * k)) {
            System.out.println(-1);
            return "-1";
        }
        StringBuilder sb = new StringBuilder();

        String b_ka = get(1, k, 'b', 'a');
        String kb_a = get(k, 1, 'b', 'a');

        // 前缀 a
        while (a > b * k) {
            sb.append('a');
            a--;
        }

        // bba
        while (a >= 1 && b >= k && (a - 1) <= (b - k) * k) {
            b = b - k;
            a = a - 1;
            sb.append(kb_a);
        }
        // ba
        if (a / k < b) {
            sb.append('b');
            b--;
            while (a > k * b) {
                a--;
                sb.append('a');
            }
        }
        // baa
        while (a >= k && b >= 1) {
            b = b - 1;
            a = a - k;
            sb.append(b_ka);
        }
        // 后缀 b
        while (b > 0) {
            sb.append('b');
            b--;
        }
//        System.out.println(sb);
        return sb.toString();
    }

    private static String get(int a, int b, char p, char q) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < a; ++i) {
            sb.append(p);
        }
        for (int i = 0; i < b; ++i) {
            sb.append(q);
        }
        return sb.toString();
    }
}

法二：

参考：https://www.nowcoder.com/discuss/530410267595784192?sourceSSR=search