一、单向选择题

第 1 题

在内存储器中每个存储单元都被赋予一个唯一的序号，称为（）。

A. 地址

B. 序号

C. 下标

D. 编号

选A。内存储器是计算机中的一种存储设备，用于存储程序和数据。每个存储单元都被赋予一个唯一的序号，称为地址。地址是内存中的一个位置，它是由二进制数字表示的，用于定位内存中的特定位置。在计算机中，地址通常是由处理器读取的，以访问内存中的特定位置。

第 2 题

编译器的主要功能是（）。

A. 将源程序翻译成机器指令代码

B. 将源程序重新组合

C. 将低级语言翻译成高级语言

D. 将一种高级语言翻译成另一种高级语言

选A。编译器是一种程序，它将一种高级语言编写的程序转换成目标语言（通常为低级语言）的程序。编译器能够识别代码中的词汇、句子以及各种特定的格式，并将他们转换成计算机能够识别的二进制形式，这个过程称为编译。

编译器的主要功能包括：将源代码翻译成目标代码、进行语义检查、优化和生成目标文件等。

第 3 题

设 x=true,y=true,z=false，以下逻辑运算表达式值为真的是（）。

A. (y∨z)∧x∧z

B. x∧(z∨y) ∧z

C. (x∧y) ∧z

D. (x∧y)∨(z∨x)

选D。有一个^z，值为假。

第 4 题

现有一张分辨率为 2048×1024 像素的 32 位真彩色图像。请问要存储这张图像，需要多大的存储空间？（）。

A. 16MB

B. 4MB

C. 8MB

D. 2MB

选C。用32位二进制数表示1个像素的颜色，即一个像素32个bit，转换成Byte：32 / 8 = 4 Byte。

$$
\frac{32}{8} * 2048 * 1024 \
= 4 * 2^{11} * 2^{10} \
= 2^2 * 2^{21} B \
= \frac{2^{23}}{2^{20}}MB = 2^3 MB = 8 MB
$$

第 5 题

冒泡排序算法的伪代码如下：

输入：数组L, n ≥ k。输出：按非递减顺序排序的 L。
算法 BubbleSort：
   1. FLAG ← n //标记被交换的最后元素位置
   2. while FLAG > 1 do
   3.     k ← FLAG -1
   4.     FLAG ← 1
   5.     for j=1 to k do
   6.         if L(j) > L(j+1) then do
   7.              L(j)  ↔ L(j+1)
   8.              FLAG ← j

对 n 个数用以上冒泡排序算法进行排序，最少需要比较多少次?（）。

A. $n^2$

B. n−2

C. n−1

D. n

选C。最好情况，程序已经排好序，n个数要比较n - 1次。

第 6 题

设 A 是 n 个实数的数组，考虑下面的递归算法：

XYZ (A[1..n])
    if n=1 then return A[1]
    else temp ← XYZ (A[1..n-1])
    if temp < A[n]
    then return temp
    else return A[n]

请问算法 XYZ 的输出是什么？（）。

A. A 数组的平均

B. A 数组的最小值

C. A 数组的中值

D. A 数组的最大值

选B。

这个递归算法是一种简单的选择排序，它用于在数组中查找最小值。让我们逐步解释算法的工作原理：

如果数组只有一个元素（n=1），那么最小值就是该元素本身，直接返回 A[1]。

否则，我们递归地调用 XYZ 函数来对前 n-1 个元素进行排序，并将结果存储在临时变量 temp 中。

然后，我们将第 n 个元素与 temp 进行比较。

如果 temp 小于第 n 个元素，说明在第 n-1 个元素中已经找到了最小值，因此我们可以直接返回 temp。

否则，第 n 个元素就是最小的元素，我们将其返回。

通过递归地将问题分解为更小的子问题，并在每个子问题上选择最小值，最终算法会找到整个数组中的最小值并返回。因此，答案是 B. A 数组的最小值。

第 7 题

链表不具有的特点是（）。

A. 可随机访问任一元素

B. 不必事先估计存储空间

C. 插入删除不需要移动元素

D. 所需空间与线性表长度成正比

选A. 可随机访问任一元素。

链表是一种线性数据结构，其中的元素不是连续存储的。每个元素都包含一个指向下一个元素的指针。因此，要访问链表中的任一元素，必须先遍历到该元素所在的节点，然后通过节点中的指针来访问该元素。由于需要遍历，所以链表不能像数组那样直接通过索引来访问任一元素，因此不具备随机访问任一元素的特点。

第 8 题

有 10 个顶点的无向图至少应该有（）条边才能确保是一个连通图。

A. 9

B. 10

C. 11

D. 12

选A。一个无向图的连通性是指图中任意两个顶点都存在一条路径相连。

对于有n个顶点的无向图，其连通性至少需要满足的条件是：当且仅当图中含有n-1条边时，这个图才是连通的。

因此，对于有10个顶点的无向图，至少需要9条边才能确保它是连通图。这是因为当图中只有8条边时，这个图就不是一个连通图。

举个例子，考虑一个有4个顶点的无向图，它只有3条边，所以它不是一个连通图。但是如果我们添加第4条边，这个图就变成了一个连通图。

第 9 题

二进制数 1011 转换成十进制数是（）。

A. 11

B. 10

C. 13

D. 12

选A。我们可以通过将二进制数的每一位乘以$2^n$(其中$n$为该位上的数字),然后将结果相加来将二进制数转换为十进制数。二进制数1011的转换过程如下：$1\times2^3+0\times2^2+1\times2^1+1\times2^0=11$

第 10 题

5 个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（）种不同排列方法?

A. 48

B. 36

C. 24

D. 72

选A。我们可以把双胞胎看作一个整体，那么就有4个整体(3个小朋友和一个双胞胎整体)需要排列，共有$4!=24$种排列方法。而双胞胎之间又有2种排列方法。所以总的排列方法为$24\times2$ $=48$种。

第 11 题

下图中所使用的数据结构是（ )。

A. 栈

B. 队列

C. 二叉树

D. 哈希表

选A。先入后出，是栈。

第 12 题

独根树的高度为 1。具有 61 个结点的完全二叉树的高度为（）。

A. 7

B. 8

C. 5

D. 6

选D。

解析：根据二叉树的性质，由于高度h的满二叉树共有$2^{h}-1$个结点，所以满二叉树的高度为 $\log_2(n+1)$，其中 n 为结点个数。

高度h的完全二叉树至少有$2^{h-1}$个结点

高度h的完全二叉树至多有$2^h-1$个结点.

因此，具有 61 个结点的完全二叉树的高度为 $\lfloor \log_2(61) \rfloor + 1 = \lfloor \log_2(61) \rfloor + 1 = 6$。

第1层有1个结点，第2层有2个结点，第3层有4个，每次都是乘2，从二进制数的角度看，就是左移一位。

第1层有1个结点，第2层有10个结点，第3层有100个。

高度为2的满二叉树共有 1 + 10 = 11 个结点，高度为3的满二叉树共有 100 + 11 = 111 个结点。

第 13 题

干支纪年法是中国传统的纪年方法，由 10 个天干和 12 个地支组合成 60 个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。

天干 =（公历年份）除以 10 所得余数
地支 =（公历年份）除以 12 所得余数

例如，今年是 2020 年，2020 除以 10 余数为 0，查表为”庚”；2020 除以 12，余数为 4，查表为“子” 所以今年是庚子年。

请问 1949 年的天干地支是（）

A. 己酉

B. 己亥

C. 己丑

D. 己卯

选C。首先，我们需要计算1949年除以10和12的余数。

$1949\div10$ $=194.9$,余数为9。

$1949\div12$ $=1949/12$,余数为5。

1949年的天干是9,地支是5，天干地支是己丑。

第 14 题

10 个三好学生名额分配到 7 个班级，每个班级至少有一个名额，一共有（）种不同的分配方案。

A. 84

B. 72

C. 56

D. 504

选A。可将10个学生看成10个元素，一字排开，元素之间形成9个空。在9个空中插入6块板即可将其分为7部分，则共有$C_9^6=84$种方案。

第 15 题

有五副不同颜色的手套（共 10 只手套，每副手套左右手各 1 只），一次性从中取 6 只手套，请问恰好能配成两副手套的不同取法有（）种。

A. 120

B. 180

C. 150

D. 30

选A。恰好能配成两幅手套，那么只能是$5$只手套成一副，剩下1只手套。

所以先从5副中取2副，有$C_5^2=10$种，

再从剩下的6只中，取第5个，6种取法，

从剩下的5只中，取第6个，不能与第5个相同，只有2种取法，

共有$C_5^2\times 6 \times \times 2=120$种。

二、阅读程序

2.1

#include <cstdlib>
#include <iostream>
using namespace std;

char encoder[26] = {'C','S','P',0};
char decoder[26];

string st;

int main()  {
    int k = 0;
    for (int i = 0; i < 26; ++i)
        if (encoder[i] != 0) ++k;
    for (char x ='A'; x <= 'Z'; ++x) {
        bool flag = true;
        for (int i = 0; i < 26; ++i)
            if (encoder[i] ==x) {
                flag = false;
                break;
            }
        if (flag) {
            encoder[k]= x;
            ++k;
        }
    }
    for (int i = 0; i < 26; ++i)
        decoder[encoder[i]- 'A'] = i + 'A';
    cin >> st;
    for (int i = 0; i < st.length( ); ++i)
        st[i] = decoder[st[i] -'A'];
    cout << st;
    return 0;
}

这个程序实现了一个简单的字符编码器和解码器。它使用了两个数组，encoder和decoder，分别用于存储编码后的字符和解码后的字符。初始时，encoder数组中已经包含了一些字符（’C’、’S’、’P’），这些字符被用作起始的编码映射。

程序首先通过遍历encoder数组来计算实际使用的字符个数，即变量k的值。然后，它使用一个循环来遍历字母表中的大写字母（从’A’到’Z’），并检查每个字母是否已经在encoder数组中出现过。如果某个字母没有出现过，就将其添加到encoder数组中，并增加k的值。

接下来，程序使用另一个循环来构建decoder数组，将编码后的字符映射回原始字符。具体来说，它将encoder数组中的每个元素减去’A’的ASCII值，然后将索引值加上’A’的ASCII值，得到对应的原始字符的索引。这样就建立了编码和解码之间的映射关系。

程序接着读取输入的字符串st，并使用循环遍历该字符串的每个字符。对于每个字符，它通过查找decoder数组来获取对应的原始字符，并将其替换为原始字符。最后，程序输出解码后的字符串st。

总结起来，这段程序实现了一个简单的编码器和解码器，可以将输入的字符串进行编码和解码操作。

判断题

16、输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。（正确）

如果输入小写字母‘a’，st[i] - 'A'大于25。

17、若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。（错误）

输入T，输出也为T。

18、将第 12 行的 i < 26 改为 i < 16，程序运行结果不会改变。（正确）

就三个字符C S P，执行3次就够了，i < 16结果一样。

19、将第 26 行的 i < 26 改为 i < 16，程序运行结果不会改变。（错误）

decode要解码26个字符，16不够，结果不一样。

单选题

20、若输出的字符串为ABCABCABCA，则下列说法正确的是（）。

A. 输入的字符串中既有 S 又有 P

B. 输入的字符串中既有 S 又有 B

C. 输入的字符串中既有 A 又有 P

D. 输入的字符串中既有 A 又有 B

选A。看上面解析图片。

21、若输出的字符串为 CSPCSPCSPCSP，则下列说法正确的是（）。

A. 输入的字符串中既有 P 又有 K

B. 输入的字符串中既有 J 又有 R

C. 输入的字符串中既有 J 又有 K

D. 输入的字符串中既有 P 又有 R

选D。看上面解析图片。

2.2

#include <iostream> 
using namespace std; 

long long n, ans; // 定义长整型变量n和ans，其中n用于存储数组的长度，ans用于存储进位次数
int k, len; // 定义整型变量k和len，k进制，len用于存储当前k进制数的长度
long long d[1000000]; // 定义一个长整型数组d，用于存储输出结果，d[0]是最后一位，d[len-1]是最高位

int main() { 
    cin >> n >> k; // 从输入流中读取n和k的值
    d[0] = 0; // k进制最后一位初值为0
    len = 1; // 0的总位数是1
    ans = 0; // 进位次数是0
    for (long long i = 0; i <n; ++i) { // 遍历数列中的每个元素
        ++d[0]; // 最后一位加1
        for (int j = 0; j + 1<len; ++j) { // 0到len-2，处理进位
            if (d[j] == k) { // 第j位为k
                d[j] = 0; // j位清0
                d[j + 1] += 1; // 高位进1
                ++ans; // 进位次数加1
            }
        }
        if (d[len- 1] == k) { // 上面的循环从0到len-2，此时最高位n-1位的进位
            d[len - 1] = 0; // 清0
            d[len] =1; // 高位进1
            ++len; // 总位数+1
            ++ans; // 进位+1
        }
    }
    cout << ans << endl; // 输出进位次数
    return 0; 
}

这段代码将10进制的数字n转换成k进制，存储在d数组，输出的ans是进位的次数。

假设输入的 n 是不超过 $2^{62}$ 的正整数，k 都是不超过 10000 的正整数，完成下面的判断题和单选题：

判断题

1）若 k = 1，则输出 ans 时，len = n。（错误）

n = 1, k = 1时，len = 2。

i = 0：d = { 1 }，15行for不满足条件，跳过，22行满足，d = { 0, 1 }，len = 2，ans = 1。

++d[0]; // 最后一位加1
for (int j = 0; j + 1<len; ++j) { //for (int j = 0; j + 1 < 1; ++j)，不进入循环
    if (d[j] == k) { 
        d[j] = 0; 
        d[j + 1] += 1; 
        ++ans; 
    }
}
if (d[len- 1] == k) { // if (d[0] == 1)，此时d[0]是0
    d[len - 1] = 0; // d[0] = 0;
    d[len] = 1; // d[1] =1;
    ++len; // len = 2
    ++ans; // ans = 1
}

2）若 k>1，则输出 ans 时，len —定小于 n。（错误）

k = 2，n = 1 时，转换成二进制数 len = 1，不是小于。

++d[0]; // 最后一位加1
for (int j = 0; j + 1<len; ++j) { //for (int j = 0; j + 1 < 1; ++j)，不进入循环
    if (d[j] == k) { 
        d[j] = 0; 
        d[j + 1] += 1; 
        ++ans; 
    }
}
if (d[len- 1] == k) { // if (d[0] == 2)，此时d[0]是1
    d[len - 1] = 0; // d[0] = 0;
    d[len] = 1; // d[1] = 1;
    ++len; // len = 1
    ++ans; // ans = 0
}

3）若 k > 1，则输出 ans 时，$k^{len}$ —定小于 n。（正确）

n 转化为 len 位的 k 进制数，n的最大值为$k^{len} - 1$，一定小于$k^{len}$。

单选题

4）若输入的 n 等于：$10^{15}$，输入的 k 为 1，则输出等于（）。

A. 1

B. $(10^{30} − 10^{15}) \div 2$

C. $(10^{30} + 10^{15}) \div 2$

D. $10^{15}$

选D。

i=0,d[0]=1，不进入15行for循环，进入22行if，d[0]=0,d[1]=1, ans=1, len=2。

i=1,d[0]=1，进入15行for循环，j=0,进入16行if，d[0]=0,d[1]=2,ans=2。len=2,不进入22行if。

i=2，d[0]=1，进入15行for循环，j=0，进入16行if，d[0]=0,d[1]=3,ans=3。Len=2,不进入22行if。

所以一直是两位数。i每循环一次，ans递增一次。

5）若输入的 n 等于 205, 891, 132, 094, 649（即 $3^{30}$），输入的 k 为 3，则输出等于（）。

A. $3^{30}$

B. $(3^{30} − 1) \div 2$

C. $3^{30} − 1$

D. $(3^{30} + 1) \div 2$

选B。

6）若输入的 n 等于 100, 010, 002, 000, 090，输入的 k 为 10，则输出等于（）。

A. 11, 112, 222, 444, 543

B. 11,122, 222, 444, 453

C. 11, 122, 222, 444, 543

D. 11, 112, 222, 444, 453

选D。

2.3

#include <algorithm>
#include <iostream>
using namespace std;                     

int n;                                   
int d[50][2]; //全局变量                 
int ans;                                 

void dfs(int n, int sum) {               
    if (n == 1) { //元素个数为1，求最大值                           
        ans = max(sum, ans);           
        return;                                   
    }                                        
    for (int i = 1; i < n; ++i) {          
        int a = d[i - 1][0], b = d[i - 1][1]; //暂存 d[i-1][0] 和 d[i][1]
        int x = d[i][0], y = d[i][1];            
        d[i - 1][0] = a + x;  // d[i - 1][0] = d[i - 1][0] + d[i][0];          
        d[i - 1][1] = b + y;  // d[i - 1][1] = d[i - 1][1] + d[i][1];              
        for (int j = i; j < n - 1; ++j) //dp[i+1][]到d[n-1]左移一格
            d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
        int s = a + x + abs(b - y); //x向加，y相减              
        dfs(n - 1, sum + s); //递归n-1层              
        for (int j = n - 1; j > i; --j)  //恢复
            d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
        d[i - 1][0] = a, d[i - 1][1] = b; //恢复 
        d[i][0] = x, d[i][1] = y;  //恢复
    }                                        
}                                        

int main() {                             
    cin >> n;                                
    for (int i = 0; i < n; ++i)              
        cin >> d[i][0];
    for (int i = 0; i < n;++i)
        cin >> d[i][1];
    ans = 0;
    dfs(n, 0);
    cout << ans << endl;
    return 0;
}

假设输入的 n 是不超过 50 的正整数，d[i][0]、d[i][1] 都是不超过 10000 的正整数，完成下面的判断题和单选题：

这段代码是一个求解最大和的问题。它使用了深度优先搜索（DFS）算法来遍历所有可能的路径，并计算每个路径上的数字之和。最后，它返回最大的数字之和作为答案。

代码的主要逻辑如下：

首先，定义了一个二维数组 d，用于存储输入的数字对。

然后，定义了一个全局变量 ans，用于记录最大数字之和。

接下来，定义了一个递归函数 dfs，用于进行深度优先搜索。该函数接受两个参数：当前的数字对数量 n 和当前的数字之和 sum。

在 dfs 函数中，首先判断是否到达了基本情况（即只有一个数字对）。如果是，则更新 ans 为当前数字之和和 ans 中的较大值，然后返回。

如果还有多个数字对，则通过循环遍历每个数字对，并将其与下一个数字对进行合并。合并后的结果存储在 d 数组中。

在每次合并后，计算新的数字之和 s，并递归调用 dfs 函数，传入更新后的数字对数量 n - 1 和新的

注意21行的int s = a + x + abs(b - y);，x是求和，y是求差。

判断题

1）若输入 n 为 0，此程序可能会死循环或发生运行错误。（错误）

不进入第10行的if 和第14行的for，函数运行结束，不会死循环。

2）若输入 n 为 20，接下来的输入全为 0，则输出为 0。（正确）

一堆0求和，结果还是0。

3）输出的数一定不小于输入的 d[i][0] 和 d[i][1] 的任意一个。（错误）

反例：n=2,d[0][0]=d[1][0]=1,d[0][1]=d[1][1]=10,输出2。

单选题

4）若输入的 n 为 20，接下来的输入是 20 个 9 和 20 个 0，则输出为（）。

A. 1890

B. 1881

C. 1908

D. 1917

选B。

每层递归都合并[0]和[1]，得到最大值。

$2 \times 9 + 3 \times 9 + 4 \times 9 + … + 20 \times 9 = 1881$

因为d[i][1]=0，所以相当于20个9，每次相邻合并，合并的两个数的和累加，求最大值。

5）若输入的 n 为 30，接下来的输入是 30 个 0 和 30 个 5，则输出为（）。

A. 2000

B. 2010

C. 2030

D. 2020

选C。每层递归都合并[0]和[1]，得到最大值。

$0 + 5 + 10 + 15 + … + 28 \times 5 = 2030$

6）若输入的 n 为 15，接下来的输入是 15 到 1，以及 15 到 1，则输出为（）。

A. 2440

B. 2220

C. 2240

D. 2420

选C。

三、完善程序

3.1 质因数分解

给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。

例如：输入 n=120，程序应该输出 2 2 2 3 5，表示：120 = 2 × 2 × 2 × 3 × 5。输入保证 2 ≤ n ≤ $10^9$。

提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。

试补全程序。

#include <cstdio>
using namespace std;
int n, i;

int main() {
    scanf("%d", &n);
    for(i = ①2; ②i*i <=n; i ++){ //用36、7举例
        ③while(n%i == 0) { //输出所有质因子i
            printf("%d ", i);
            n = n / i;
        }
    }
    if(④n > 1) //n除到最后，如果等于1，不输出
        printf("%d ", ⑤n);
    return 0;
}

34、①处应填（）

A. 1

B. n-1

C. 2

D. 0

选C。最小的质因数是2，从2开始。

35、②处应填（）

A. n/i

B. n/(i*i)

C. i*i

D. i*i*i

选C。常用 i * i。

36、③处应填（ )

A. if(n%i == 0)

B. if(i*i <= n)

C. while(n%i == 0)

D. while(i*i <= n)

选C。if不能输出所有质因子，120 = 2 × 2 × 2 × 3 × 5分解出来有多个2，故用while。

37、④处应填（）

A. n > 1

B. n <= 1

C. i < n / i

D. i + i <= n

选A。n除到最后，如果等于1，不输出。

38、⑤处应填（ )

A. 2

B. n/i

C. n

D. i

选C。输出n。

3.2 最小区间覆盖

给出 n 个区间，第 i 个区间的左右端点是 $[a_i, b_i]$。现在要在这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并覆盖（即每一个 0 ≤ i ≤ m 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 n 和 m （1 ≤ n ≤ 5000, 1 ≤ m ≤ $10^9$）

接下来 n 行，每行两个整数 $a_i, b_i$ （0 ≤ $a_i, b_i$ ≤ m）。

提示：使用贪心法解决这个问题。先用 O($n^2$) 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];

void sort() // 冒泡排序，左端点升序
{
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (①A[j].a < A[j-1].a) //如果左侧线段的左端点大，交换
            {
                segment t = A[j];
                ②A[j] = A[j-1]; A[j-1] = t;
            }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> A[i].a >> A[i].b;
    sort(); //左端点升序排序
    int p = 1; //处理后的线段个数
    for (int i = 1; i < n; i++) //其他更大范围的线段
        if (③A[i].b > A[p-1].b) //覆盖的线段删除
            A[p++] = A[i];
    n = p; //p是更新后的线段个数
    int ans =0, r = 0; //已覆盖区间有边界
    int q = 0; //当前线段编号
    while (r < m) //已覆盖区间有边界 < m
    {
        while (④q+1 < n && A[q+1].a <= r) //下一线段存在 且 左端点在已覆盖区间右边界左侧
            q++; 
        ⑤r = max(r, A[q].b); //确定新的已覆盖区间右边界
        ans++; //统计答案
    }
    cout << ans << endl;
    return 0;
}

39、①处应填（）

A. A[j].b > A[j-1].b
B. A[j].a < A[j-1].a
C. A[j].a > A[j-1].a
D. A[j].b < A[j-1].b

选B。左侧线段的左端点更大，交换。

40、②处应填（）

A. A[j+1] = A[j]; A[j] = t;

B. A[j-1] = A[j]; A[j] = t;

C. A[j] = A[j+1]; A[j+1] = t;

D. A[j] = A[j-1]; A[j-1] = t;

选D。两数交换，用t暂存。

41、③处应填（）

A. A[i].b > A[p-1].b

B. A[i].b < A[i-1].b

C. A[i].b > A[i-1].b

D. A[i].b < A[p-1].b

选A。被其他更大范围的线段覆盖了，删除掉。

两条红色线段，被上面一条蓝色线段覆盖了，删除。

42、④处应填（）

A. q+1 < n && A[q+1].a <= r

B. q+1 < n && A[q+1].b <= r

C. q < n && A[q].a <= r

D. q < n && A[q].b <= r

选A。下一线段存在且下一线段的左端点在右边界的左边，区间才能续上。

43、⑤处应填（）

A. r = max(r, A[q+1].b)

B. r = max(r, A[q].b)

C. r = max(r, A[q+1].a)

D. q++

选B。取最大值，已覆盖区间的右边界。

参考

SleepBlog

一、单向选择题

二、阅读程序

2.1

2.2

2.3

三、完善程序

3.1 质因数分解

3.2 最小区间覆盖

你的赏识是我前进的动力