在计算机网络中，端口号的作用是什么？

在计算机网络中，端口号的作用是用来标识网络通信中的特定服务或应用程序。端口号是一个 16 位的数字（范围是 0 到 65535），每个端口号对应一个特定的网络服务或进程。

当数据包通过网络传输时，端口号帮助确定数据包应该被发送到目的主机上的哪个应用程序或服务。比如：

• 端口 80 通常用于 HTTP 协议的网络通信，因此 Web 服务器通常监听端口 80。
• 端口 443 则用于 HTTPS 协议，确保安全的 Web 通信。
• 端口 22 通常用于 SSH 服务，用于安全地远程登录到另一台计算机。

端口号分为三类：

1. 知名端口（Well-known Ports）：范围为 0 到 1023，通常分配给常见的网络服务，如 HTTP（80）、FTP（21）、SMTP（25）等。
2. 注册端口（Registered Ports）：范围为 1024 到 49151，通常分配给用户或特定的服务。
3. 动态或私有端口（Dynamic or Private Ports）：范围为 49152 到 65535，通常用于临时通信或客户机的自定义通信。

通过端口号，操作系统可以将收到的数据正确地交付到相应的应用程序，从而使网络通信得以正常进行。

在计算机网络中，端口号的作用是什么？

A 区分主机内不同进程 B 加密数据传输 C 确保数据完整性 D 控制数据流量 正确答案是 A：区分主机内不同进程。

端口号的主要作用是区分同一主机内不同的网络进程或服务，使得网络数据能够被正确地传送到对应的应用程序。

HTTPS 协议通过使用哪些机制来确保通信的安全性（）

A 加密和身份验证 B 压缩和缓存 C 路由和负载均衡 D 访问控制和权限管理

正确答案是 A：加密和身份验证。

HTTPS 协议通过使用加密和身份验证机制来确保通信的安全性。具体来说，HTTPS 使用 TLS（传输层安全协议）来加密数据，从而防止数据在传输过程中被窃听或篡改。此外，身份验证确保通信的双方是真实可信的，通常通过数字证书来实现。这些机制共同保障了 HTTPS 通信的安全性。

ETag 用于标识资源的唯一标识符，它可以用于（）

A 验证资源是否发生变化 B 控制缓存的过期时间 C 指定缓存的最大大小 D 加密缓存中的数据

正确答案是 A：验证资源是否发生变化。

ETag（实体标签）是 HTTP 协议的一部分，用于标识资源的唯一标识符。它可以帮助服务器和客户端验证资源是否发生变化，从而决定是否需要重新下载资源，优化网络带宽和缓存利用率。

在一个单道系统中，有 4 个作业 P、Q、R 和 S，执行时间分别为 2 小时、4 小时、6 小时和 8 小时，P 和 Q 同时在 0 时到达，R 和 S 在 2 小时到达，采用短作业优先算法时，平均周转时间为（）。

A 15 小时 B 12 小时 C 6 小时 D 9 小时

作业到达时间和执行时间如下：

• P: 到达时间 = 0 小时，执行时间 = 2 小时
• Q: 到达时间 = 0 小时，执行时间 = 4 小时
• R: 到达时间 = 2 小时，执行时间 = 6 小时
• S: 到达时间 = 2 小时，执行时间 = 8 小时

根据短作业优先（SJF）算法的调度顺序如下：

1. 0 小时：P 和 Q 到达。P 的执行时间较短，优先执行 P。
   • P 完成时间 = 0 + 2 = 2 小时
2. 2 小时：P 完成后，R 和 S 到达，同时 Q 还未执行。此时，Q 的执行时间较短，优先执行 Q。
   • Q 完成时间 = 2 + 4 = 6 小时
3. 6 小时：R 的执行时间较短，优先执行 R。
   • R 完成时间 = 6 + 6 = 12 小时
4. 12 小时：最后执行 S。
   • S 完成时间 = 12 + 8 = 20 小时

各作业的周转时间计算如下：

• P 的周转时间 = 2 - 0 = 2 小时
• Q 的周转时间 = 6 - 0 = 6 小时
• R 的周转时间 = 12 - 2 = 10 小时
• S 的周转时间 = 20 - 2 = 18 小时

平均周转时间 = (2 + 6 + 10 + 18) / 4 = 36 / 4 = 9 小时

所以，正确答案是 D：9 小时。

系统中现有一个任务进程在 11:30 到达系统，如果在 14:30 开始运行这个任务进程，其运行时间为 3 小时，现求这个任务进程的响应比为（）。

A 0.5 B 2 C 1 D 1.5

响应比的计算公式为：

响应比=等待时间 + 运行时间运行时间响应比 = \frac{等待时间 + 运行时间}{运行时间}响应比=运行时间等待时间 + 运行时间​

在这个问题中：

• 到达时间：11:30
• 开始运行时间：14:30
• 运行时间：3 小时

首先，计算等待时间：

• 等待时间 = 开始运行时间 - 到达时间 = 14:30 - 11:30 = 3 小时

然后，应用公式计算响应比：

响应比=等待时间 + 运行时间运行时间=3+33=63=2 响应比 = \frac{等待时间 + 运行时间}{运行时间} = \frac{3 + 3}{3} = \frac{6}{3} = 2 响应比=运行时间等待时间 + 运行时间​=33+3​=36​=2

所以，正确答案是 B：2。

在一个物流管理系统中，需要一个功能来处理不同类型的货物运输请求，如陆运、空运或海运。该系统应能够根据运输类型的不同选择不同的处理策略。哪种设计模式最合适（）

A 工厂方法模式 B 桥接模式 C 策略模式 D 适配器模式

在这种场景中，最合适的设计模式是 C：策略模式。

策略模式允许你定义一系列算法、将每个算法封装起来，并使它们可以互相替换。在物流管理系统中，不同的运输类型（如陆运、空运、海运）可以被视为不同的策略。策略模式能够让系统根据运输类型选择不同的处理策略，而不需要在代码中硬编码具体的处理逻辑。这样，系统变得更加灵活和可扩展。

工厂方法模式（Factory Method Pattern）

概念：工厂方法模式是一种创建型设计模式，它定义了一个创建对象的接口，但由子类决定要实例化的具体类是哪一个。这样，工厂方法模式让类的实例化推迟到子类中进行。

目的：工厂方法模式的主要目的是将对象的创建过程与其使用过程分离。通过这种方式，代码中的类可以独立于对象的创建方式。

使用场景：

• 当你不知道对象的具体类型，或希望让子类来决定要实例化哪一个类时。
• 需要在创建对象时增加一些额外的逻辑，比如日志记录或缓存时。
• 当你有一个超类的多种变体或派生类时，而你希望代码能够在运行时自动选择使用哪一个派生类。

示例：

abstract class Logistics {  
    // 工厂方法  
    public abstract Transport createTransport();  
​  
    public void planDelivery() {  
        Transport transport = createTransport();  
        transport.deliver();  
    }  
}  
​  
class RoadLogistics extends Logistics {  
    @Override  
    public Transport createTransport() {  
        return new Truck();  
    }  
}  
​  
class SeaLogistics extends Logistics {  
    @Override  
    public Transport createTransport() {  
        return new Ship();  
    }  
}

在这个例子中，Logistics 是抽象类，它定义了工厂方法 createTransport。RoadLogistics 和 SeaLogistics 是具体实现类，它们决定了具体的运输方式。

策略模式（Strategy Pattern）

概念：策略模式是一种行为型设计模式，它定义了一系列算法，并将每一个算法封装起来，使它们可以互相替换。策略模式让算法的变化独立于使用算法的客户端。

目的：策略模式的主要目的是通过将算法的实现与其使用分离，使得可以在运行时选择或改变算法的实现。

使用场景：

• 当你有多种算法或行为，并且这些算法可能会在运行时切换时。
• 当你希望避免使用大量的条件语句（如 if-else 或 switch-case）来选择不同的行为时。
• 当你希望能在运行时选择一种算法，而不影响使用算法的客户端代码时。

// 策略接口  
interface TransportStrategy {  
    void transport();  
}  
​  
// 具体策略  
class RoadTransport implements TransportStrategy {  
    @Override  
    public void transport() {  
        System.out.println("Transport by road");  
    }  
}  
​  
class SeaTransport implements TransportStrategy {  
    @Override  
    public void transport() {  
        System.out.println("Transport by sea");  
    }  
}  
​  
// 上下文类  
class ShippingContext {  
    private TransportStrategy strategy;  
​  
    public ShippingContext(TransportStrategy strategy) {  
        this.strategy = strategy;  
    }  
​  
    public void executeStrategy() {  
        strategy.transport();  
    }  
}

在这个例子中，TransportStrategy 是策略接口，RoadTransport 和 SeaTransport 是具体策略实现。ShippingContext 是上下文类，它使用传入的策略对象来执行相应的算法。

总结

• 工厂方法模式 关注的是如何创建对象，并将对象的创建过程与使用过程分离，常用于系统的实例化管理。
• 策略模式 关注的是行为或算法的封装和替换，使得不同的算法可以在运行时互相替换，常用于处理多种行为的选择问题。

两者的主要区别在于目的和应用场景的不同，一个用于对象的创建，一个用于算法的选择。

对关键码序列{9, 27, 18, 36, 45, 54, 63}进行堆排序，输出 2 个最大关键码后的剩余堆是（）

A {9, 18, 27, 36, 45} B {9, 18, 45, 27, 36} C {45, 9, 18, 27, 36} D {45, 36, 18, 9, 27}

堆排序是一种基于堆（通常是大顶堆或小顶堆）的排序算法。在这个问题中，我们要从序列中输出 2 个最大关键码后的剩余堆，因此我们需要构建一个大顶堆，并逐步取出最大值。

给定序列：{9, 27, 18, 36, 45, 54, 63}

1. 构建大顶堆：首先，将给定序列 {9, 27, 18, 36, 45, 54, 63} 构建为一个大顶堆。堆化过程是自底向上调整的，最后形成的堆顶元素是最大值。初始堆：markdown 复制代码 9 / \ 27 18 / \ / \ 36 45 54 63 经过堆化调整后形成大顶堆：markdown 复制代码 63 / \ 45 54 / \ / \ 36 27 18 9
2. 第一次取出最大值：取出堆顶的 63，将堆尾 9 移到堆顶，然后重新堆化。markdown 复制代码 54 / \ 45 18 / \ / 36 27 9
3. 第二次取出最大值：取出堆顶的 54，将堆尾 9 移到堆顶，然后重新堆化。markdown 复制代码 ` 45 / \ 36 18 / \ 9 27

​
现在，堆中剩下的元素为{45, 36, 18, 9, 27}，也就是答案 D：{45, 36, 18, 9, 27}。
​
---

以下哪个设计模式主要用于在不改变原始类的情况下扩展其功能（）

A 装饰器模式 B 适配器模式 C 工厂模式 D 建造者模式

正确答案是 A：装饰器模式。
​

装饰器模式 主要用于在不改变原始类的情况下扩展其功能。它通过将原始类包装在一个装饰类中，动态地添加额外的行为或职责，从而实现功能扩展。这种模式特别有用，因为它可以在不修改现有代码的情况下，灵活地增加新功能。 ​

设哈希表长 m=10，有一堆数据元素，关键字分别为{14, 25, 36, 47, 58, 69, 80}，按照哈希函数为 H(key)=key%10，如用线性探测法处理冲突，求关键字 90 填装的哈希表位置的序号是（）。

A 3 B 4 C 1 D 6

给定的哈希函数 H(key)=key%10H(key) = key \% 10H(key)=key%10 来计算每个关键字的哈希值，并按照线性探测法处理冲突。具体步骤如下：
​

1. 计算关键字 90 的初始哈希位置：  
   H(90)=90%10=0H(90) = 90 \% 10 = 0H(90)=90%10=0
2. 检查位置 0 是否已被占用：  
     先看看之前的关键字：  
           14 的哈希值：H(14)=14%10=4H(14) = 14 \% 10 = 4H(14)=14%10=4  
           25 的哈希值：H(25)=25%10=5H(25) = 25 \% 10 = 5H(25)=25%10=5  
           36 的哈希值：H(36)=36%10=6H(36) = 36 \% 10 = 6H(36)=36%10=6  
           47 的哈希值：H(47)=47%10=7H(47) = 47 \% 10 = 7H(47)=47%10=7  
           58 的哈希值：H(58)=58%10=8H(58) = 58 \% 10 = 8H(58)=58%10=8  
           69 的哈希值：H(69)=69%10=9H(69) = 69 \% 10 = 9H(69)=69%10=9  
           80 的哈希值：H(80)=80%10=0H(80) = 80 \% 10 = 0H(80)=80%10=0  
     * 位置 0 已被关键字 80 占用，因此需要进行线性探测。
3. 线性探测：  
     我们依次检查哈希表中的下一个位置（位置 1）。  
     位置 1 是空闲的，因此可以将关键字 90 放在位置 1。
   ​
   所以，关键字 90 最终填装的位置是 C：1。
   ​ ---

在编译器的目标代码生成阶段，以下哪个不是优化的主要目标是（）

A 降低程序的功耗 B 减小目标代码的体积 C 提高目标代码的执行效率 D 减少程序的编译时间

正确答案是 D：减少程序的编译时间。
​
在编译器的目标代码生成阶段，优化的主要目标包括：
​

• 降低程序的功耗（A）
• 减小目标代码的体积（B）
• 提高目标代码的执行效率（C）
  ​
  然而，减少程序的编译时间（D）并不是优化的主要目标。编译时间的减少通常与编译器的性能有关，而与目标代码的优化无关。目标代码优化通常是在编译器生成目标代码时，尽可能提高生成代码的执行效率、减少体积或降低功耗，即使这些优化可能增加编译时间。
  ​
  ​ 编译器的完整流程通常分为多个阶段，每个阶段负责不同的任务。编译器的主要任务是将源代码转换为目标代码（通常是机器代码或中间代码），以便在目标平台上执行。以下是编译器的主要阶段及其功能的详细说明：

1. 词法分析（Lexical Analysis）

​

• 目的：将源代码转换为一系列的词法单元（Token）。词法单元是代码中的基本语法元素，比如关键字、标识符、运算符、常量等。
• 输入：源代码（字符流）
• 输出：词法单元序列
• 工作方式：词法分析器会扫描源代码，识别并提取有意义的符号，如int、x、=, 10, ; 等。在这个阶段，还会处理标识符、数字、字符串等，并丢弃不必要的内容，比如注释和空白字符。

2. 语法分析（Syntax Analysis）

​

• 目的：将词法单元序列组织成一个语法树（Parse Tree 或 Syntax Tree），该树反映了源代码的语法结构。
• 输入：词法单元序列
• 输出：语法树
• 工作方式：语法分析器根据编程语言的语法规则，检查词法单元序列是否符合语言的语法规范，并生成语法树。语法树是代码的层次结构表示，显示了各个语法元素之间的关系。

3. 语义分析（Semantic Analysis）

​

• 目的：检查语法树的语义正确性，并执行类型检查、变量声明检查等。
• 输入：语法树
• 输出：注解后的语法树或中间表示
• 工作方式：语义分析器会检查代码的实际含义。例如，它会验证变量是否已经声明、类型是否匹配、函数调用参数是否正确等。语义分析阶段还可能生成符号表，用来记录变量、函数等的类型信息和作用域。

4. 中间代码生成（Intermediate Code Generation）

​

• 目的：将语法树或抽象语法树（AST）转换为一种中间表示（IR），这种表示通常是独立于具体机器的。
• 输入：语法树或 AST
• 输出：中间代码（如三地址码、控制流图等）
• 工作方式：中间代码生成器会创建一个简化的代码表示形式，这种表示通常介于源代码和目标代码之间。这一步通常是为了在后续阶段更方便地进行优化。

5. 中间代码优化（Intermediate Code Optimization）

​

• 目的：通过优化中间代码，提高程序执行的效率或减少代码的大小。
• 输入：中间代码
• 输出：优化后的中间代码
• 工作方式：优化器会进行各种代码优化，如常量折叠、死代码消除、循环优化等。这些优化是为了在保持语义不变的前提下，使得最终生成的目标代码更加高效。

6. 目标代码生成（Target Code Generation）

​

• 目的：将中间代码转换为目标代码（通常是机器代码或汇编代码），能够在特定的硬件平台上执行。
• 输入：优化后的中间代码
• 输出：目标代码
• 工作方式：目标代码生成器会把中间代码翻译成具体平台的机器指令。这一步还涉及寄存器分配、内存布局等，确保生成的代码能有效地运行在目标硬件上。

7. 目标代码优化（Target Code Optimization）

​

• 目的：对目标代码进行进一步优化，特别是那些针对特定硬件平台的优化。
• 输入：初步生成的目标代码
• 输出：优化后的目标代码
• 工作方式：这一阶段的优化通常针对硬件架构，如寄存器使用优化、指令调度、流水线优化等，目的是进一步提高代码的执行效率。

8. 汇编和链接（Assembly and Linking）

​

• 目的：将生成的目标代码汇编为可执行文件，并解决代码中的外部依赖（如库函数）。
• 输入：目标代码
• 输出：可执行文件或库文件
• 工作方式：汇编器将目标代码转换为机器指令，并打包成二进制格式。链接器会将不同的代码模块或库文件连接起来，解决符号引用，生成最终的可执行文件。

9. 加载和执行（Loading and Execution）

​

• 目的：加载可执行文件到内存中并开始执行。
• 输入：可执行文件
• 输出：程序运行结果
• 工作方式：当用户或操作系统请求执行程序时，加载器将程序加载到内存，并根据指令逐条执行。

总结

编译器的完整流程是一个复杂的过程，从源代码的输入到最终可执行文件的生成，每个阶段都有其特定的任务和挑战。词法分析、语法分析和语义分析是编译器前端的主要阶段，它们负责理解和处理源代码的语法和语义。中间代码生成和优化，以及目标代码生成和优化，则属于编译器后端，主要负责生成高效的机器代码。最终，通过汇编和链接，将代码转化为可执行文件，使得程序可以在目标平台上运行。
​

在用 KMP 算法进行模式匹配时，若是指向模式串"mnopmn"的指针在指到第 5 个字符"m"时发生失配，则指针回溯的位置为（）。注：字符串中字符从字符数据 1 号位开始存储，也即从 1 开始编号。

A 1 B 2 C 3 D 4

在 KMP 算法中，失配后指针的回溯位置由部分匹配表（也称为前缀函数表）决定。部分匹配表的值表示在失配时，模式串中已经匹配的部分中最长的相同前缀和后缀的长度。
​
给定模式串为 "mnopmn"，我们首先构建它的部分匹配表（前缀函数表）。
​

模式串 "mnopmn" 的前缀函数表计算过程：

​

1. 字符 "m": 没有前缀和后缀匹配，部分匹配值为 0。
2. 字符 "n": 没有前缀和后缀匹配，部分匹配值为 0。
3. 字符 "o": 没有前缀和后缀匹配，部分匹配值为 0。
4. 字符 "p": 没有前缀和后缀匹配，部分匹配值为 0。
5. 字符 "m": 前缀 "m" 和后缀 "m" 匹配，部分匹配值为 1。
6. 字符 "n": 前缀 "mn" 和后缀 "mn" 匹配，部分匹配值为 2。
   ​
   所以，模式串 "mnopmn" 的部分匹配表如下：

​

分析失配情况：

​
在匹配过程中，指针指向第 5 个字符 "m" 时发生失配。
​

• 失配发生在第 5 个字符 "m"，前缀函数表的值为 1。
• 根据 KMP 算法的规则，指针需要回溯到前缀函数表中值为 1 的位置（也就是相同的前缀和后缀的长度为 1），即回溯到模式串的第 2 个字符。
  ​
  因此，失配时指针回溯的位置是 B：2。
  ​

代码需要经过一系列步骤编译成机器指令，根据完成任务不同，可以将编译器的组成部分划分为前端与后端。下列选项是编译器前端在编译源程序时编译的顺序，正确的是（）

A 词法分析器->语法分析器->中间代码生成器 B 语法分析器->词法分析器->中间代码生成器 C 词法分析器->中间代码生成器->语法分析器 D 语法分析器->中间代码生成器->词法分析器

正确答案是 A：词法分析器 -> 语法分析器 -> 中间代码生成器。
​
解释如下：
​

1. 词法分析器：首先，词法分析器将源代码转化为词法单元（tokens）。它识别出代码中的关键字、标识符、操作符等基本元素。
2. 语法分析器：然后，语法分析器接收词法分析器生成的词法单元序列，构建语法树或抽象语法树（AST），验证代码是否符合语言的语法规则。
3. 中间代码生成器：最后，中间代码生成器根据语法树生成中间代码，这种代码独立于具体机器平台，方便后续的优化和目标代码生成。
   ​
   所以，正确的编译顺序是 词法分析器 -> 语法分析器 -> 中间代码生成器。
   ​

不同的数据存放区存放的数据和对应的管理方法是不同的。对于某些数据，如果在编译期间就可以确定数据对象的大小和数据对象的数目，在编译期间为数据对象分配存储空间，这些数据对应的存储分配策略是（）

A 栈式存储分配 B 堆式存储分配 C 动态存储分配 D 静态存储分配

正确答案是 D：静态存储分配。
​
静态存储分配 是在编译期间确定数据对象的大小和数目，并为其分配存储空间的策略。这种分配方式通常适用于全局变量、静态变量和常量，这些数据在程序的整个生命周期内都存在，并且存储位置在程序加载时已经确定。
​
栈式存储分配 通常用于局部变量，函数调用时在栈上分配空间，函数返回后释放。
​
堆式存储分配 则用于动态内存分配，通常使用malloc、new等在运行时分配内存，使用free、delete释放内存。
​
动态存储分配 是在运行时根据需求动态分配和释放存储空间，通常涉及堆式存储。
​

下列选项中只要其中一个表中存在匹配，则返回行的 SQL JOIN 的 类型是（）。

A INNER JOIN B LEFT JOIN C RIGHT JOIN D FULL JOIN

正确答案是 D：FULL JOIN。
​
FULL JOIN（或称 FULL OUTER JOIN）返回的是左右两个表中所有匹配的记录，以及在两个表中没有匹配到的记录。只要任一表中存在匹配，都会返回结果，未匹配到的地方则用 NULL 填充。
​
具体来说：
​

• INNER JOIN 只返回两个表中匹配的记录。
• LEFT JOIN 返回左表的所有记录以及左右表中匹配的记录，右表未匹配的部分用 NULL 填充。
• RIGHT JOIN 返回右表的所有记录以及左右 k 表中匹配的记录，左表未匹配的部分用 NULL 填充。
• FULL JOIN 返回两个表中的所有记录，无论是否匹配，只要存在记录就会被返回。
  ​
  因此，FULL JOIN 是只要其中一个表中存在匹配就返回行的 JOIN 类型。
  ​
  ---
  ## 已知某个 Mysql 数据库里面有一个帖子表，这个表会存储帖子的各种信息，请问以下哪种情况对应的列不适合建索引 A 帖子表中存储帖子内容的列 B 帖子表中存储帖子作者性别的列 C 帖子表中存储帖子作者 id 的列 D 帖子表中存储表示帖子状态的列，所有可能值不超过 10 种

正确答案是 A：帖子表中存储帖子内容的列。
​

原因：

​

• 帖子内容的列 通常存储大块的文本数据（如文章内容、评论等），这些数据占用较大的存储空间。为这样的列建立索引会导致索引文件非常庞大，不仅占用大量磁盘空间，还会降低插入、更新操作的性能。因此，通常不建议为大文本或 BLOB 列建立索引。
  ​
  ### 其他选项：
  ​
• 帖子作者性别的列：性别通常只有两个或少数几个值（例如“男”或“女”），属于低基数（Low Cardinality）列，为这样的列建立索引通常意义不大，因为索引选择性较低。
• 帖子作者 ID 的列：这通常是一个高基数（High Cardinality）的列（即每个帖子可能由不同的作者发布），为这样的列建立索引是有意义的，有助于快速查找特定作者的帖子。
• 表示帖子状态的列：如果状态的可能值较少（不超过 10 种），也是低基数列，索引的效果可能不如高基数列明显，但在某些查询条件下可能仍然有用，如查询某特定状态的所有帖子。
  ​
  因此，A 选项中存储大量文本内容的列最不适合建索引。

什么情况下建立索引

建立索引的主要目的是提高数据库查询的性能，但索引并不是在任何情况下都适合使用。以下是一些适合建立索引的情况：
​

1. 频繁用于查询条件（WHERE 子句）中的列

​

• 如果某列经常出现在查询的WHERE子句中，并且选择性较高（即能够过滤掉大量数据），那么为该列建立索引可以显著提高查询效率。
• 例如：用户 ID、订单 ID 等。

2. 经常用于 JOIN 操作的列

​

• 在涉及多表连接（JOIN）的查询中，常常用作连接条件的列适合建立索引。这可以加速表之间的连接操作。
• 例如：在用户表和订单表之间用用户 ID 进行 JOIN 操作时，为用户 ID 建立索引可以提高性能。

3. 用于排序（ORDER BY）或分组（GROUP BY）的列

​

• 如果某列经常用于ORDER BY或GROUP BY操作，建立索引可以减少排序或分组操作所需的时间。
• 例如：订单日期、创建时间等。

4. 唯一性约束的列

​

• 对于必须唯一的列（如主键或具有 UNIQUE 约束的列），索引是必要的，以确保数据的唯一性和快速检索。
• 例如：用户表中的邮箱地址、用户名等。

5. 经常用于范围查询的列

​

• 如果某列经常用于范围查询（如BETWEEN、<、>等），为该列建立索引有助于加快范围查询的速度。
• 例如：年龄、日期范围等。

6. 用于覆盖索引的列

​

• 覆盖索引指的是包含了查询所需的所有列的索引。对于特定的查询，如果索引包含了所有的查询列，则可以避免回表操作，直接从索引中返回结果。
• 例如：复合索引（如包含用户 ID、订单日期的复合索引）可以加速特定查询。

7. 高基数（High Cardinality）列

​

• 高基数列是指具有大量唯一值的列。为这种列建立索引通常会带来显著的查询性能提升。
• 例如：订单 ID、用户 ID 等。

需要注意的情况：

​

• 低基数列：如性别、状态（有少量可能值）等列的选择性较差，索引的效果不明显，可能不适合建立索引。
• 频繁更新的列：如果某列的数据经常被更新，为该列建立索引可能会影响写操作的性能，因为每次更新都需要维护索引。
• 大文本或 BLOB 列：如长篇文章、图像数据等，索引会占用大量存储空间，不推荐在这些列上建立索引。

总结

​
索引的主要目的是加速数据检索操作，但也会带来额外的存储和维护开销。因此，是否建立索引应该基于列的用途、查询频率、数据的分布和性能需求综合考虑。

下列哪些运算不会排序（）

A GROUP BY 子句 B ORDER BY 子句 C 聚合函数（SUM、COUNT、AVG、MAX、MIN） D BETWEEN

正确答案是 C：聚合函数（SUM、COUNT、AVG、MAX、MIN） 和 D：BETWEEN。

解释：

• A. GROUP BY 子句：GROUP BY 会对结果集进行排序，以便将相同的值分组在一起。因此，它会涉及排序操作。
• B. ORDER BY 子句：ORDER BY 显式要求对结果集进行排序，按照指定的列进行升序或降序排列，因此它肯定会排序。
• C. 聚合函数（SUM、COUNT、AVG、MAX、MIN）：这些聚合函数通常在查询的聚合阶段执行，并不要求对结果集进行排序。它们直接在数据上进行计算，并输出聚合结果。例如，SUM 计算总和、COUNT 计算行数、AVG 计算平均值、MAX 和 MIN 计算最大值和最小值，均不涉及排序操作。
• D. BETWEEN：BETWEEN 是一个范围查询操作符，用于查找在指定范围内的值。它只是一个过滤条件，不要求对结果集进行排序。
  ​
  因此，C. 聚合函数 和 D. BETWEEN 都不会进行排序操作。

编程题 1

小美拿到了一个 n ∗ n 的矩阵，其中每个元素是 0 或者 1。小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。现在，小美希望你回答有多少个 i ∗ i 的完美矩形区域。你需要回答 1 ≤ i ≤ n 的所有答案。第一行输入一个正整数 n，代表矩阵大小。接下来的 n 行，每行输入一个长度为 n 的 01 串，用来表示矩阵。 输出 n 行，第 i 行输出 i*i 的完美矩形区域的数量

问题分析

​ 我们需要找到矩阵中每个可能的 子矩形区域（对于 ），并计算每个子矩形区域中 0 和 1 的数量是否相等。

具体步骤

​

1. 前缀和：构建两个前缀和矩阵，一个记录 0 的数量，另一个记录 1 的数量。前缀和矩阵可以帮助我们在常数时间内计算任意子矩形区域内 0 或 1 的数量。
2. 遍历所有子矩形：对于每个 子矩形区域，我们可以利用前缀和矩阵快速计算该区域内 0 和 1 的数量，并检查它们是否相等。
3. 统计结果：对每个可能的 i 计算符合条件的 子矩形的数量。

实现代码

下面是使用 Java 实现上述问题的代码：

import java.util.Scanner;

public class PerfectRectangles {

public static void main(String[] args) {  
    Scanner scanner = new Scanner(System.in);  
      
    // 输入矩阵大小  
    int n = scanner.nextInt();  
    scanner.nextLine();  // 跳过换行符  
      
    int[][] matrix = new int[n][n];  
      
    // 输入矩阵  
    for (int i = 0; i < n; i++) {  
        String line = scanner.nextLine();  
        for (int j = 0; j < n; j++) {  
            matrix[i][j] = line.charAt(j) - '0';  
        }  
    }  
      
    // 计算并输出每个大小的完美矩形数量  
    for (int size = 1; size <= n; size++) {  
        int count = countPerfectRectangles(matrix, n, size);  
        System.out.println(count);  
    }  
      
    scanner.close();  
}  
​  
private static int countPerfectRectangles(int[][] matrix, int n, int size) {  
    // 前缀和矩阵  
    int[][] prefixZero = new int[n + 1][n + 1];  
    int[][] prefixOne = new int[n + 1][n + 1];  
      
    // 计算前缀和  
    for (int i = 1; i <= n; i++) {  
        for (int j = 1; j <= n; j++) {  
            prefixZero[i][j] = prefixZero[i - 1][j] + prefixZero[i][j - 1] - prefixZero[i - 1][j - 1] + (matrix[i - 1][j - 1] == 0 ? 1 : 0);  
            prefixOne[i][j] = prefixOne[i - 1][j] + prefixOne[i][j - 1] - prefixOne[i - 1][j - 1] + (matrix[i - 1][j - 1] == 1 ? 1 : 0);  
        }  
    }  
      
    int count = 0;  
      
    // 计算符合条件的矩形数量  
    for (int i = size; i <= n; i++) {  
        for (int j = size; j <= n; j++) {  
            int zeroCount = prefixZero[i][j] - prefixZero[i - size][j] - prefixZero[i][j - size] + prefixZero[i - size][j - size];  
            int oneCount = prefixOne[i][j] - prefixOne[i - size][j] - prefixOne[i][j - size] + prefixOne[i - size][j - size];  
              
            if (zeroCount == oneCount) {  
                count++;  
            }  
        }  
    }  
      
    return count;  
}

}

代码解释：

• 前缀和矩阵：在countPerfectRectangles方法中，首先计算每个前缀和矩阵（prefixZero和prefixOne），分别存储矩阵中 0 和 1 的前缀和。这样可以快速计算任意子矩形内的 0 和 1 的数量。
• 子矩形计数：对于每个可能的矩形大小，代码遍历整个矩阵，检查每个子矩形区域内 0 和 1 的数量是否相等。如果相等，则计数加 1。

输入输出：

在运行该程序时，输入矩阵大小n和矩阵的 01 字符串。程序将计算并输出每个i*i矩形区域中完美矩形的数量，从1<=i<=n。

复杂度：

该算法的时间复杂度是O(n^4)，因为要遍历所有可能的i*i矩形区域并检查其内的 0 和 1 的数量。对于n最大为 200 的情况，算法在合理范围内可以接受。

编程题 2

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。现在小美想知道，如果那些未知的元素在区间 范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？共有 q q 次询问。第一行输入两个正整数 n,q，代表数组大小和询问次数。第二行输入 n 个整数 ，其中如果输入的 为 0，那么说明 是未知的。接下来的 q 行，每行输入两个正整数 l,r，代表一次询问。 , , , , 输出 q 行，每行输出两个正整数，代表所有元素之和的最小值和最大值。

这个问题要求计算数组在多个查询下的元素之和的最小值和最大值。对于每个查询，我们要处理数组中值为0的元素，并将它们视为在指定区间 [l, r] 中的某个值。

解决思路

1. 初始化数组总和：首先，我们计算数组中所有非 0 元素的总和，因为这些值是固定的，无论查询区间是什么，它们都会对最小值和最大值产生同样的贡献。
2. 处理0值元素：对于每个查询 [l, r]，我们要计算数组中的0值元素如果取l和r，分别会导致总和的最小值和最大值：
   
   • 对于最小值，假设所有0元素都取l。
   • 对于最大值，假设所有0元素都取r。
3. 输出结果：对于每个查询，输出总和的最小值和最大值。

实现代码

import java.util.Scanner;

public class Main {

public static void main(String[] args) {  
    Scanner scanner = new Scanner(System.in);  
  
    // 输入数组大小和询问次数  
    int n = scanner.nextInt();  
    int q = scanner.nextInt();  
  
    int[] arr = new int[n];  
    long sumFixed = 0; // 固定元素的总和  
    int zeroCount = 0;  // 0 元素的个数  
  
    // 输入数组元素并计算固定元素的总和  
    for (int i = 0; i < n; i++) {  
        arr[i] = scanner.nextInt();  
        if (arr[i] == 0) {  
            zeroCount++;  
        } else {  
            sumFixed += arr[i];  
        }  
    }  
  
    // 处理每个查询  
    for (int i = 0; i < q; i++) {  
        int l = scanner.nextInt();  
        int r = scanner.nextInt();  
  
        // 最小值：假设所有 0 都取值为 l  
        long minSum = sumFixed + (long) zeroCount * l;  
        // 最大值：假设所有 0 都取值为 r  
        long maxSum = sumFixed + (long) zeroCount * r;  
  
        System.out.println(minSum + " " + maxSum);  
    }  
  
    scanner.close();  
}

}

解释

• sumFixed：这个变量存储数组中所有非 0 元素的总和。

• zeroCount：这个变量存储数组中值为 0 的元素个数。

  对于每次查询 [l, r]：

• 最小值计算：假设所有0都取值为l，因此最小值为sumFixed + zeroCount * l。

• 最大值计算：假设所有0都取值为r，因此最大值为sumFixed + zeroCount * r。

  复杂度分析

• 时间复杂度：构建初始总和和计算zeroCount的时间复杂度为O(n)。每次查询的时间复杂度为O(1)，因此总时间复杂度为O(n + q)，能够处理最大规模的数据。

  这个算法能够有效处理n和q都为 10^5 级别的输入。

如果有用例超时，通常是因为对于大规模输入，算法的效率不够高。在当前的解决方案中，我们计算最小值和最大值的过程实际上是O(1)，主要耗时在输入和输出处理上。然而，有可能是因为输入输出处理不够高效，导致在大规模数据上出现了性能问题。

以下是几种优化方案：

1. 优化输入输出：

• 对于大规模数据，Java 的Scanner在处理输入时可能较慢，可以尝试使用更快的输入输出方式，如BufferedReader和BufferedWriter。

  优化后的代码：

import java.io.BufferedReader; 
import java.io.BufferedWriter; 
import java.io.InputStreamReader; 
import java.io.OutputStreamWriter; 
import java.io.IOException;

public class Main {

public static void main(String[] args) throws IOException {  
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));  
    BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));  
  
    // 读取数组大小和询问次数  
    String[] input = reader.readLine().split(" ");  
    int n = Integer.parseInt(input[0]);  
    int q = Integer.parseInt(input[1]);  
  
    long sumFixed = 0; // 固定元素的总和  
    int zeroCount = 0;  // 0 元素的个数  
  
    // 读取数组并计算固定元素的总和  
    String[] arr = reader.readLine().split(" ");  
    for (int i = 0; i < n; i++) {  
        int value = Integer.parseInt(arr[i]);  
        if (value == 0) {  
            zeroCount++;  
        } else {  
            sumFixed += value;  
        }  
    }  
  
    // 处理每个查询  
    for (int i = 0; i < q; i++) {  
        String[] range = reader.readLine().split(" ");  
        int l = Integer.parseInt(range[0]);  
        int r = Integer.parseInt(range[1]);  
  
        // 最小值：假设所有 0 都取值为 l  
        long minSum = sumFixed + (long) zeroCount * l;  
        // 最大值：假设所有 0 都取值为 r  
        long maxSum = sumFixed + (long) zeroCount * r;  
  
        writer.write(minSum + " " + maxSum + "\n");  
    }  
  
    // 刷新输出缓冲区  
    writer.flush();  
    writer.close();  
    reader.close();  
}

}

2. 减少内存分配：

• 尽量减少在循环中的字符串处理操作和对象创建，可以通过复用数组或字符串缓冲区来避免不必要的内存分配。

  3. 并行化计算：

• 如果运行环境支持多线程，并且查询数量非常大，可以考虑将查询并行化处理。不过在大多数竞赛环境下，可能不允许使用多线程。

  4. 避免多次拆分字符串：

• 避免在循环中多次调用split()方法，可以将输入的字符串拆分操作集中在一起处理。

  ---

编程题 3

假设美团的工号是由 18 位数字组成的，由以下规则组成：前面 6 位代表是哪个部门 7-14 位代表是出生日期，范围是 1900.01.01-2023.12.31 , 15-17 位代表是哪个组，不能是完全一样的 3 位数字 18 位是一位的校验和，假设是 x x，则需要满足 [(x + a1 + a_2 + a_3 + a_4 + ... + a{17}) \mod 8 = 1]，a 1 − a 17 代表了前面的 17 位数字 现在需要写一份代码，判断输入的工号是否符合对应的规则。提示：出生日期这里需要判断闰年。闰年判断的条件是能被 4 整除，但不能被 100 整除；或能被 400 整除。第一行输入一个整数 n() 接下来 n 行，每行输入一个字符串，表示一个合法的部门。如果工号不属于合法部门的话，则认为这个工号不符合规则。接下来输入一个整数 m() 接下来 m 行，每行输入一个字符串，表示需要验证的工号。如果不满足上述任一个规则，输出 "error" ，都满足的话输出 "ok"

import java.util.HashSet; import java.util.Scanner; import java.util.Set;

public class Main {

public static void main(String[] args) {  
    Scanner scanner = new Scanner(System.in);  
  
    // 输入合法部门  
    int n = scanner.nextInt();  
    Set<String> validDepartments = new HashSet<>();  
    for (int i = 0; i < n; i++) {  
        validDepartments.add(scanner.next());  
    }  
  
    // 输入需要验证的工号  
    int m = scanner.nextInt();  
    for (int i = 0; i < m; i++) {  
        String employeeNumber = scanner.next();  
        if (isValidEmployeeNumber(employeeNumber, validDepartments)) {  
            System.out.println("ok");  
        } else {  
            System.out.println("error");  
        }  
    }  
  
    scanner.close();  
}  
  
private static boolean isValidEmployeeNumber(String employeeNumber, Set<String> validDepartments) {  
    if (employeeNumber.length() != 18) {  
        return false;  
    }  
  
    // 验证部门  
    String department = employeeNumber.substring(0, 6);  
    if (!validDepartments.contains(department)) {  
        return false;  
    }  
  
    // 验证出生日期  
    String birthDate = employeeNumber.substring(6, 14);  
    if (!isValidDate(birthDate)) {  
        return false;  
    }  
  
    // 验证组号  
    String group = employeeNumber.substring(14, 17);  
    if (group.charAt(0) == group.charAt(1) && group.charAt(1) == group.charAt(2)) {  
        return false;  
    }  
  
    // 验证校验和  
    int checksum = Character.getNumericValue(employeeNumber.charAt(17));  
    int sum = checksum;  
    for (int i = 0; i < 17; i++) {  
        sum += Character.getNumericValue(employeeNumber.charAt(i));  
    }  
    if (sum % 8 != 1) {  
        return false;  
    }  
  
    return true;  
}  
  
private static boolean isValidDate(String date) {  
    if (date.length() != 8) {  
        return false;  
    }  
  
    int year = Integer.parseInt(date.substring(0, 4));  
    int month = Integer.parseInt(date.substring(4, 6));  
    int day = Integer.parseInt(date.substring(6, 8));  
  
    if (year < 1900 || year > 2023) {  
        return false;  
    }  
  
    if (month < 1 || month > 12) {  
        return false;  
    }  
  
    int[] daysInMonth = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};  
  
    // 闰年判断  
    if (isLeapYear(year)) {  
        daysInMonth[1] = 29;  
    }  
  
    return day >= 1 && day <= daysInMonth[month - 1];  
}  
  
private static boolean isLeapYear(int year) {  
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);  
}

}

代码功能描述：

1. 部门验证：前 6 位代表部门，使用集合Set来存储合法的部门编号，判断是否在集合中。
2. 出生日期验证：7-14 位代表出生日期，验证日期是否在合法的范围内，并判断是否为有效日期。还包括闰年的判断。
3. 组号验证：15-17 位代表组号，组号不能是完全相同的 3 位数字。
4. 校验和验证：18 位校验和计算，确保 (x + a1 + a2 + ... + a17) % 8 == 1。

复杂度分析：

​

• 时间复杂度主要取决于输入的工号数量，验证一个工号的时间复杂度为 O(1)，因此总时间复杂度为 O(m)，其中 m 为工号数量。
• 使用Set来验证部门，使得部门验证的时间复杂度为 O(1)。