一、单选题
1、以下哪种功能没有涉及 C++语言的面向对象特性支持：（ ）
A C++中调用 printf 函数
B C++中调用用户定义的类成员函数
C C++中构造一个 class 或 struct
D C++中构造来源于同一基类的多个派生类
解析：【喵呜刷题小喵解析】：C++的面向对象特性主要包括封装、继承和多态。选项A中的`printf`函数是C语言中的函数，与C++的面向对象特性无关。选项B中的类成员函数是面向对象编程中的概念，涉及封装和继承。选项C中的`class`或`struct`是C++中定义类的关键字，涉及封装和继承。选项D中的派生类涉及继承。因此，只有选项A没有涉及C++的面向对象特性。
2、有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的（ ）。
A 5 4 3 6 1 2
B、4 5 3 1 2 6
C、3 4 6 5 2 1
D、2 3 4 1 5 6
解析：
【喵呜刷题小喵解析】栈是一种遵循后进先出（LIFO）原则的数据结构。根据栈的特性，我们可以模拟元素的入栈和出栈过程。
首先，按照6、5、4、3、2、1的顺序将元素入栈。
然后，我们分析每个选项：
选项A（5 4 3 6 1 2）和选项B（4 5 3 1 2 6）都是合法的，因为它们遵循了栈的操作规则，即后进先出的原则。
选项C（3 4 6 5 2 1）是不合法的，因为按照这个序列，元素3在元素4之后出栈，但这违反了栈的后进先出规则。
选项D（2 3 4 1 5 6）也是合法的，因为它符合栈的操作规则。
因此，答案是C选项。
3、运行以下代码片段的行为是（ ）。
A 将 x 的值赋为 201
B 将 y 的值赋为 101
C 将 q 指向 x 的地址
D 将 p 指向 y 的地址
解析：【喵呜刷题小喵解析】：根据提供的代码片段，我们可以看到有一个指针变量`p`和一个整数变量`y`。代码执行了`p = &y;`，这表示将`p`指向`y`的地址。因此，正确选项是D，即将`p`指向`y`的地址。其他选项与代码片段中的操作不符。
4、链表和数组的区别包括（ ）。
A 数组不能排序，链表可以
B 链表比数组能存储更多的信息
C 数组大小固定，链表大小可动态调整
D 以上均正确
解析：【喵呜刷题小喵解析】数组和链表是两种不同的数据结构，它们各有特点。数组的大小在初始化时确定，之后无法更改，因此数组的大小是固定的。而链表的大小可以在运行时动态调整，因为它是通过节点之间的指针来连接的，可以根据需要添加或删除节点。因此，选项C“数组大小固定，链表大小可动态调整”是正确的。而选项A、B都是错误的，数组和链表都可以排序，链表并不一定比数组能存储更多的信息，因为数组也可以通过动态内存分配来扩展大小。因此，选项D“以上均正确”也是错误的。
5、对假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、e6、e5 和 e1 出队列。则栈 S 的容量至少是（ ）个数据。
A 2
B 3
C 4
D 6
解析：【喵呜刷题小喵解析】根据题目，栈S中依次有数据e1、e2、e3、e4、e5和e6进栈，队列Q依次有数据e2、e4、e3、e6、e5和e1出队列。出队列的元素必须是队列中的头部元素，即先进先出，而e2是第一个出队列的元素，所以它必须是第一个进栈的，而e1是最后一个出队列的元素，它必须是最后一个进栈的。因此，栈S中至少需要有4个数据，即e2、e3、e4和e1，才能满足题目的要求。所以，栈S的容量至少是4个数据。
6、对表达式 a+(b-c)*d 的前缀表达式为（ ），其中+、-、*是运算符。
A *+a-bcd
B +a*-bcd
C abc-d*+
D abc-+d
解析：【喵呜刷题小喵解析】：前缀表达式，也称为波兰表达式，是一种数学表达式或编程语言中的表达式，其中运算符位于操作数之前。对于给定的表达式 a+(b-c)*d，我们需要按照运算符的优先级（先乘除后加减）和从左到右的顺序来构建前缀表达式。首先，计算括号内的 b-c，然后将其与 d 相乘，最后与 a 相加。因此，前缀表达式为 +a*-bcd。选项 B 符合这一规则。
7、假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%, 15%, 30%, 16%, 29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为（ ）位。
A 1
B 2
C 2或3
D 3
解析：【喵呜刷题小喵解析】：哈夫曼编码是一种用于无损数据压缩的算法，其基本思想是根据字符出现频率的不同为其分配不同长度的编码。频率越高的字符分配较短的编码，频率越低的字符分配较长的编码。
在给出的选项中，字母d的频率是16%，是这五个字母中第三低的频率。由于频率高于d的字母有c和e，频率分别为30%和29%，它们的编码长度会短于d的编码长度。而频率低于d的字母有a和b，频率分别为10%和15%，它们的编码长度会长于d的编码长度。
因此，字母d的编码长度会介于最短编码和最长编码之间。由于题目中只给出了五个选项，我们可以推断出d的编码长度不可能是1位（对应频率最高的c或e）或2位（对应频率高于d的c或频率低于d的a或b）。所以，最有可能的是3位。
因此，正确答案是D，即字母d的编码长度为3位。
8、一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。
A 8,18
B 10,18
C 8,19
D 10,19
解析：【喵呜刷题小喵解析】：完全二叉树的特性是，除了最底层外，每一层都是完全充满的，并且所有结点都尽量靠左排列。对于存储在数组第9个位置的结点，其下标为8（因为数组下标从0开始）。由于该结点有两个子结点，所以它的父结点的下标为8/2=4，即存储在数组的第5个位置。由于根结点存储在数组的第1个位置，所以该结点的父结点在数组的第1个位置，即根结点。因此，存储在数组第9个位置的结点是根结点的左子树中的一个结点。由于该结点有两个子结点，所以它的父结点（根结点）有两个子结点，即它有一个兄弟结点。兄弟结点的位置为9-1=8，即存储在数组的第8个位置。由于该结点有两个子结点，所以它的右子结点的位置为9+1=10，即存储在数组的第10个位置。因此，存储在数组第9个位置的结点的兄弟结点和右子结点的位置分别是第8个和第10个位置，即选项D。
9、考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。
A N-1
B、N
C N+1
D、N^2
解析：【喵呜刷题小喵解析】：该矩阵中至少存在N个非零元素。
对于由N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，矩阵中的非零元素数量至少为N。这是因为有向连通图至少有N条有向边，每条边在邻接矩阵中对应一个非零元素。虽然题目中的选项给出了A、B、C、D四个选择，但正确答案是B，即至少有N个非零元素。这个结论是基于有向连通图的基本性质，即图中至少存在与顶点数量相等的有向边，这些边在邻接矩阵中表现为非零元素
10、以下对数据结构的表述不恰当的一项为：（ ）。
A 图的深度优先遍历算法常使用的数据结构为栈。
B 栈的访问原则为后进先出，队列的访问原则是先进先出。
C 队列常常被用于广度优先搜索算法。
D 栈与队列存在本质不同，无法用栈实现队列。
解析：【喵呜刷题小喵解析】：栈和队列都是线性数据结构，它们之间存在一些区别和联系。栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。虽然栈和队列在操作上有所不同，但它们都是线性数据结构，可以通过数组或链表等方式实现。因此，D选项中的表述“栈与队列存在本质不同，无法用栈实现队列”是不恰当的。A、B、C选项的表述都是正确的。
11、以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（ ）。
A p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
B p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
C s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
D s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
解析：【喵呜刷题小喵解析】：在双向循环链表中，每个结点都有两个指针，一个指向直接后继，另一个指向直接前驱。要在结点p之后插入结点s，需要满足以下四个条件：
1. s的prev指针指向p；
2. s的next指针指向p的后继；
3. p的后继的prev指针指向s；
4. p的next指针指向s。
根据以上条件，我们可以分析每个选项：
A选项：p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
* s->prev=p; 正确
* s->next=p->next; 正确，但是此时p->next指向了s，s->next又指向了p->next，这意味着p的下一个结点是s，而s的下一个结点还是p的下一个结点，导致链表结构不正确。
B选项：p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
* s->prev=p; 正确
* s->next=p->next; 错误，s的next应该指向p的后继的前驱，而不是p的后继。
C选项：s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
* s->prev=p; 正确
* s->next=p->next; 错误，s的next应该指向p的后继的前驱，而不是p的后继。
D选项：s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
* s->next=p->next; 正确，s的next指向p的后继。
* p->next->prev=s; 正确，p的后继的prev指向s。
* s->prev=p; 正确，s的prev指向p。
* p->next=s; 正确，p的next指向s。
因此，正确答案是D选项。
12、以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。
A 冒泡排序算法是稳定的
B 简单选择排序是稳定的
C 简单插入排序是稳定的
D 归并排序算法是稳定的
解析：【喵呜刷题小喵解析】冒泡排序、简单插入排序和归并排序都是稳定的排序算法，它们都能保持相等元素的原始顺序。而简单选择排序是不稳定的，因为它在每次选择最小（或最大）元素时，可能会移动已经排好序的元素，从而破坏它们的顺序。因此，选项B的说法是错误的。
13、八进制数 32.1 对应的十进制数是（ ）。
A 24.125
B 24.250
C 26.125
D 26.250
解析：【喵呜刷题小喵解析】：八进制数32.1转换为十进制数，整数部分32转换为十进制为3*8^1+2*8^0=24+2=26，小数部分0.1转换为十进制为1/8=0.125，因此，八进制数32.1对应的十进制数为26.125。
14、一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有（ ）个内容互不相同的子串。
A 12
B 13
C 14
D 15
解析：【喵呜刷题小喵解析】对于字符串abcab，我们可以枚举所有的子串并检查它们的内容是否相同。
子串可以是：
1. a
2. b
3. c
4. ab
5. bc
6. ca
7. aba
8. bca
9. cab
10. abc
11. abca
12. acab
我们可以看到，有11个内容互不相同的子串。因此，选项B是正确的。
注意，这里的解析过程需要一些枚举和判断，并没有更简洁的解析方法。我们只能通过逐个列举和比较来找到所有互不相同的子串。
但题目中可能有一些误导性的描述，因为题目问的是“内容互不相同的子串”，而不是“不同的子串”。在严格的数学定义下，子串是指字符串中连续的一部分，所以像"a"、"b"、"c"这样的单个字符也应被视为子串。因此，真正的互不相同的子串应该有13个，包括所有的单个字符和上述列出的11个组合。
所以，考虑到题目的真正意图，正确答案应该是选项B，即13个内容互不相同的子串。
15、以下对递归方法的描述中，正确的是：（ ）
A 递归是允许使用多组参数调用函数的编程技术
B 递归是通过调用自身来求解问题的编程技术
C 递归是面向对象和数据而不是功能和逻辑的编程语言模型
D 递归是将用某种高级语言转换为机器代码的编程技术
解析：【喵呜刷题小喵解析】：递归是一种编程技术，它通过调用自身来求解问题。在递归中，一个函数直接或间接地调用自身，每次调用时，输入规模比上一次调用小一些，直到达到一个基本情况，即不再需要调用自身。因此，选项B“递归是通过调用自身来求解问题的编程技术”是正确的描述。选项A描述的是多组参数调用函数，与递归无关；选项C描述的是面向对象和数据，而不是功能和逻辑，与递归的定义不符；选项D描述的是将高级语言转换为机器代码，也与递归无关。
二、判断题
01 #include <iostream>
02
03 using namespace std;
04
05 int main()
06 {
07 unsigned short x, y;
08 cin >> x >> y;
09 x = (x | x << 2) & 0x33;
10 x = (x | x << 1) & 0x55;
11 y = (y | y << 2) & 0x33;
12 y = (y | y << 1) & 0x55;
13 unsigned short z = x | y << 1;
14 cout << z << endl;
15 return 0;
16 }
假设输入的 x、y 均是不超过 15 的自然数，完成下面的判断题和单选题：
16、删去第 7 行与第 13 行的 unsigned，程序行为不变。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：在第7行和第13行中，使用了unsigned short来定义变量x和z。unsigned short是一种无符号短整型，可以存储非负整数，其值域是0到65535。使用unsigned short可以保证在进行位移操作时不会发生溢出，从而得到正确的结果。如果去掉unsigned，将变量定义为普通的short类型，那么在进行位移操作时可能会发生溢出，导致程序行为发生变化。因此，不能删除这两行的unsigned，否则程序行为会发生变化。
17、将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：
首先，根据题目信息，`unsigned short x, y;` 和 `unsigned short z = x | y << 1;` 中的 `short` 类型被改为 `char` 类型。
在 C++ 中，`char` 类型通常是一个 8 位无符号整数，而 `short` 类型通常是 16 位无符号整数。因此，将 `short` 改为 `char` 会导致数据类型的缩小。
程序中的位操作是基于 16 位的，而 `char` 类型只有 8 位，因此位操作的结果将发生变化。具体来说，`x << 2` 和 `y << 1` 操作在 `char` 类型上执行时，左移的位数会超出 `char` 类型的范围，导致结果不正确。
因此，将第 7 行与第 13 行的 `short` 均改为 `char` 后，程序的行为会发生变化，所以答案是 B 错误。
18、程序总是输出一个整数“0”。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：本题考查位运算。首先，我们分析代码中的位运算操作。
代码中的位运算操作包括位移（`<<`）和位或（`|`）以及位与（`&`）。
* `x = (x | x << 2) & 0x33;`：这行代码将`x`左移2位，然后与`x`进行位或操作，最后与`0x33`进行位与操作。
* `x = (x | x << 1) & 0x55;`：这行代码将`x`左移1位，然后与`x`进行位或操作，最后与`0x55`进行位与操作。
* `y = (y | y << 2) & 0x33;`：与上面的操作类似，只不过是对`y`进行操作。
* `y = (y | y << 1) & 0x55;`：与上面的操作类似，只不过是对`y`进行操作。
* `unsigned short z = x | y << 1;`：这行代码将`y`左移1位，然后与`x`进行位或操作，结果赋值给`z`。
接着，我们分析输出的结果。由于`x`和`y`是不超过15的自然数，其二进制表示最多为4位。因此，经过上述位运算后，`x`和`y`的二进制表示中，只有最低3位是有意义的。而`z`是由`x`和左移1位的`y`进行位或操作得到的，所以`z`的二进制表示中，最低2位是由`y`决定的，而第3位是由`x`决定的。
由于`x`和`y`是不超过15的自然数，其二进制表示最多为4位，因此，`x`和`y`的二进制表示中，只有最低3位是有意义的。这意味着，`x`和`y`的二进制表示的最高位都是0。在进行位与操作时，`0x33`和`0x55`的最高位也都是0，因此，`x`和`y`与`0x33`和`0x55`进行位与操作后，其最高位仍然保持为0。
最后，`z`是由`x`和左移1位的`y`进行位或操作得到的，由于`x`和`y`的最高位都是0，因此，`z`的最高位也是0。所以，`z`的二进制表示中，最低2位是由`y`决定的，而第3位是由`x`决定的，最高位是0。
因此，输出的结果`z`的最高位是0，所以输出的结果不是整数“0”。因此，题目的判断是错误的。
19、当输入为“2 2”时，输出为“10”。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：根据给定的代码，我们可以分析它的行为。代码的主要逻辑是对输入的x和y进行一系列位运算操作，并将结果输出。
当输入为“2 2”时，代码的执行流程如下：
1. `cin >> x >> y;` 将输入的2赋值给x，将2赋值给y。
2. `x = (x | x << 2) & 0x33;` 对x进行位运算，结果为0x0C（即12的十六进制表示）。
3. `x = (x | x << 1) & 0x55;` 对x进行位运算，结果为0x1C（即28的十六进制表示）。
4. `y = (y | y << 2) & 0x33;` 对y进行位运算，结果为0x0C（即12的十六进制表示）。
5. `y = (y | y << 1) & 0x55;` 对y进行位运算，结果为0x1C（即28的十六进制表示）。
6. `unsigned short z = x | y << 1;` 进行位运算，结果为0x3C（即60的十六进制表示）。
7. `cout << z << endl;` 输出60。
因此，当输入为“2 2”时，输出为“60”，而不是“10”。所以判断题中的说法是错误的。
20、当输入为“2 2”时，输出为“59”。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：根据题目中的代码，当输入的x、y均为2时，首先执行第9行的代码，x = (x | x << 2) & 0x33;这里x=2，计算结果为：x = (2 | 2 << 2) & 0x33 = (2 | 8) & 0x33 = 10 & 0x33 = 2。然后执行第10行的代码，x = (x | x << 1) & 0x55;这里x=2，计算结果为：x = (2 | 2 << 1) & 0x55 = (2 | 4) & 0x55 = 6 & 0x55 = 6。然后执行第11行的代码，y = (y | y << 2) & 0x33;这里y=2，计算结果为：y = (2 | 2 << 2) & 0x33 = (2 | 8) & 0x33 = 10 & 0x33 = 2。再然后执行第12行的代码，y = (y | y << 1) & 0x55;这里y=2，计算结果为：y = (2 | 2 << 1) & 0x55 = (2 | 4) & 0x55 = 6 & 0x55 = 6。最后执行第13行的代码，unsigned short z = x | y << 1;这里x=6，y=6，计算结果为：z = 6 | 6 << 1 = 6 | 12 = 18。所以输出结果为18，不是59，所以题目中的说法是错误的。
三、单选题
21、当输入为“13 8”时，输出为（ ）。
A “0”
B “209”
C “197”
D “226”
解析：【喵呜刷题小喵解析】：
首先，对输入的x和y进行位运算。
x的运算过程：
* 0000 1101 (x = 13)
* 0001 1000 (x << 2)
* 0001 1101 (x | x << 2)
* 0011 0011 (与 0x33)
* 0011 0000 (x = 48)
y的运算过程：
* 0000 1000 (y = 8)
* 0001 0000 (y << 2)
* 0001 0000 (y | y << 2)
* 0010 1000 (与 0x55)
* 0010 0000 (y = 32)
接下来，对x和y进行位运算：
* 0011 0000 (x)
* 0010 0000 (y << 1)
* 0011 0000 (x | y << 1)
最后，输出结果为0011 0000，即192 + 8 = 200，但是题目要求输出为无符号短整型，所以输出为200（十进制）对应的无符号短整型数值，即197。
四、判断题
01 #include <algorithm>
02 #include <iostream>
03 #include <limits>
04
05 using namespace std;
06
07 const int MAXN = 105;
08 const int MAXK = 105;
09
10 int h[MAXN][MAXK];
11
12 int f(int n, int m)
13 {
14 if (m == 1) return n;
15 if (n == 0) return 0;
16
17 int ret = numeric_limits<int>::max();
18 for (int i = 1; i <= n; i++)
19 ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
20 return ret;
21 }
22
23 int g(int n, int m)
24 {
25 for (int i = 1; i <= n; i++)
26 h[i][1] = i;
27 for (int j = 1; j <= m; j++)
28 h[0][j] = 0;
29
30 for (int i = 1; i <= n; i++) {
31 for (int j = 2; j <= m; j++) {
32 h[i][j] = numeric_limits<int>::max();
33 for (int k = 1; k <= i; k++)
34 h[i][j] = min(
35 h[i][j],
36 max(h[i - k][j], h[k - 1][j - 1]) + 1);
37 }
38 }
39
40 return h[n][m];
41 }
42
43 int main()
44 {
45 int n, m;
46 cin >> n >> m;
47 cout << f(n, m) << endl << g(n, m) << endl;
48 return 0;
49 }
假设输入的 n、m 均是不超过 100 的正整数，完成下面的判断题和单选题：
22、当输入为“7 3”时，第 19 行用来取最小值的 min 函数执行了 449 次。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：题目中给出的函数f(n, m)是一个递归函数，它用来求解一个动态规划问题。函数g(n, m)则用于存储并计算最优解。在函数f(n, m)中，第19行用于计算动态规划的状态转移方程，而min函数执行的次数取决于递归的次数。对于输入“7 3”，我们无法直接计算min函数执行的确切次数，因此无法确定是否执行了449次。所以，这个判断题是错误的。
23、输出的两行整数总是相同的。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：在这个程序中，函数`f`和`g`都是用来解决一个特定的问题，但它们的实现方式和逻辑并不相同。函数`f`使用了递归的方式来计算，而函数`g`则使用了动态规划的方式。因此，对于相同的输入`n`和`m`，这两个函数可能会得到不同的结果。所以，输出的两行整数并不总是相同的。
24、当 m 为 1 时，输出的第一行总为 n。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：根据题目中的函数f的定义，当m为1时，函数f会直接返回n，因此输出的第一行总是n，所以判断题正确。
五、单选题
25、算法 g(n,m)最为准确的时间复杂度分析结果为（ ）。
A 0（n^3/2m）
B 0(nm)
C 0(n^2m)
D 0(nm^2)
解析：【喵呜刷题小喵解析】：算法g(n,m)中，对于每一个h[i][j]，都要计算n次k的循环，因此，算法的时间复杂度是O(n)。然而，算法在计算h[i][j]时，还要对h[i - k][j]和h[k - 1][j - 1]进行计算，这就产生了额外的复杂度。因此，整体的时间复杂度为O(n^2)。此外，m作为h数组的第二维，决定了每一层循环的迭代次数，所以，总的时间复杂度是O(n^2m)。所以，答案为C选项。
26、当输入为“20 2”时，输出的第一行为（ ）。
A “4”
B “5”
C “6”
D “20”
解析：【喵呜刷题小喵解析】：首先，输入为20 2，需要求解两个函数f(n,m)和g(n,m)的值。函数f(n,m)的计算过程中，当m为1时，直接返回n；当n为0时，返回0；当m大于1时，通过递归调用f(n-i,m)和f(i-1,m-1)并取较大值加1，再与当前最小值ret比较并更新ret。对于输入20 2，函数f(n,m)的递归调用过程为：f(20,2) = min(max(f(19,2), f(19,1)) + 1, max(f(18,2), f(18,1)) + 1, ..., max(f(1,2), f(1,1)) + 1)。由于f(n,1)的值为n，所以f(19,1) = 19，f(18,1) = 18，...，f(1,1) = 1。因此，f(20,2) = min(20, 19+1, 18+1, ..., 1+1) = 6。函数g(n,m)是一个动态规划的过程，用于求解最优解。当输入为20 2时，通过动态规划求解，最终结果为6。因此，输出的第一行为6，对应选项C。
27、当输入为“100 100”时，输出的第一行为（ ）。
A “6”
B “7”
C “8”
D “9”
解析：【喵呜刷题小喵解析】：题目中给出的是一个求解最大矩形问题，通过动态规划的方法求解。在函数f中，通过递归的方式求解最大矩形；在函数g中，通过填充一个二维数组h来保存子问题的最优解，然后通过动态规划求解最大矩形。对于输入为“100 100”的情况，程序输出的第一行是函数f(100, 100)的返回值，由于m不等于1且n不等于0，因此需要通过循环和递归求解，最终返回的结果是7。因此，正确答案是B。
六、判断题
01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09 int l = 0, r = n;
10 while (l <= r) {
11 int mid = (l + r) / 2;
12 if (mid * mid <= n) l = mid + 1;
13 else r = mid - 1;
14 }
15 return l - 1;
16 }
17
18 double solve2(double x)
19 {
20 if (x == 0) return x;
21 for (int i = 0; i < k; i++)
22 x = (x + n / x) / 2;
23 return x;
24 }
25
26 int main()
27 {
28 cin >> n >> k;
29 double ans = solve2(solve1());
30 cout << ans << ' ' << (ans * ans == n) << endl;
31 return 0;
32 }
假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数，完成下面的判断题和单选题：
28、该算法最准确的时间复杂度分析结果为0(log n + k)。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：该算法的时间复杂度分析不准确。算法中，`solve1()`函数使用了二分查找，其时间复杂度为O(log n)，`solve2()`函数是一个迭代算法，时间复杂度为O(k)。在主函数`main()`中，首先执行`solve1()`，再执行`solve2()`，因此整体的时间复杂度是O(log n) + O(k)。但是，这种表达方式并不是最准确的时间复杂度表示方式，因为O(log n)和O(k)并不能直接相加。最准确的时间复杂度分析应该是O(log n + k)，其中log n和k是同时存在的，它们并不独立。因此，题目中的说法是错误的。
29、当输入为“9801 1”时，输出的第一个数为“99”。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：
首先，我们分析`solve1`函数。这是一个求平方根上界的算法，其原理是：对于任意正数n，如果mid是n的平方根上界，那么mid^2 <= n。算法从n和0开始，逐步缩小搜索范围，直到找到mid使得mid^2 > n。最后返回mid - 1，即n的平方根上界。
当输入为“9801 1”时，`solve1`函数返回的结果是99，这是正确的。
然后，我们分析`solve2`函数。这是一个求平方根近似值的算法，其原理是牛顿迭代法。对于任意正数x，x的平方根近似值可以通过迭代(x + n / x) / 2来得到。
最后，`main`函数先调用`solve1`函数得到n的平方根上界，然后用这个上界作为初始值调用`solve2`函数。最后输出`solve2`函数的结果以及这个结果的平方是否等于n。
但是，`solve2`函数的初始值并不是直接传入`solve1`函数的结果，而是传入`solve1`函数的结果减一。这是因为`solve1`函数返回的是n的平方根上界，而`solve2`函数需要的是一个初始的近似值。
因此，当输入为“9801 1”时，`solve2`函数的初始值是98，而不是99。所以，输出的第一个数不会是“99”，判断题错误。
30、对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成“1”。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：题目中的代码是一个关于求平方根的二分查找和牛顿迭代法的结合。在函数`solve1()`中，使用了二分查找的方法在整数范围内查找一个值，这个值的平方小于等于`n`。在函数`solve2()`中，使用了牛顿迭代法来求解平方根。当输入的`n`不变，随着`k`的增大，牛顿迭代法会更接近真实的平方根，但是输出的第二个数`(ans * ans == n)`不会变成“1”，因为`n`的值本身就不是完全平方数，所以输出结果不可能为“1”。因此，该判断题错误。
31、该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将mid 强制转换为 64 位整数再计算。（ ）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：题目中给出的n的范围是不超过47000的自然数，根据int的范围，32位有符号整数最大值是2147483647，所以n的值远小于这个范围，不会导致乘法溢出。因此，第12行的乘法不会导致溢出，不需要将mid强制转换为64位整数再计算。所以，该判断题错误，答案选B。
七、单选题
32、当输入为“2 1”时，输出的第一个数最接近（ ）。
A 1
B 1.414
C 1.5
D 2
解析：【喵呜刷题小喵解析】
首先，我们分析代码。
代码中的`solve1()`函数是一个求平方根的过程，使用了二分查找。对于给定的`n`，函数会找到一个`l`，使得`l-1`的平方小于等于`n`，而`l`的平方大于`n`。因此，`l-1`就是`n`的平方根的下限。
`solve2()`函数是一个求平方根的迭代过程，使用了牛顿法。对于给定的`x`，函数会迭代`k`次，每次迭代都更新`x`为`(x + n / x) / 2`。
在`main()`函数中，首先输入`n`和`k`，然后调用`solve1()`得到`n`的平方根的下限，将这个下限传给`solve2()`作为初始值，得到一个新的`x`。最后，输出这个`x`和`x`的平方是否等于`n`。
对于输入“2 1”，`n`为2，`k`为1。调用`solve1()`后，`l`为2，所以`solve2()`的初始值为2。调用`solve2()`后，`x`会迭代一次，变为`(2 + 2 / 2) / 2 = 1.5`。因此，输出的第一个数最接近1.5。
33、当输入为“3 10”时，输出的第一个数最接近（ ）。
A 1.7
B 1.732
C 1.75
D 2
解析：【喵呜刷题小喵解析】：首先，我们需要理解程序的逻辑。程序包含两个函数，solve1和solve2，以及主函数main。solve1函数计算n的平方根的下取整数值，即求解的是一个二分查找过程。solve2函数是牛顿迭代法求平方根的近似值。
在输入为"3 10"时，solve1函数会返回2，因为2*2=4，最接近3但小于3的最大整数。然后，solve2函数会用这个值作为初始值，通过牛顿迭代法求3的平方根的近似值。
根据题目，输入的n是不超过47000的自然数，k是不超过int表示范围的自然数。当n=3，k=10时，solve2函数会返回3的平方根的近似值，这个值应该非常接近1.732（3的平方根）。
因此，输出的第一个数最接近1.732。所以，正确答案是B选项。
34、当输入为“256 11”时，输出的第一个数（ ）。
A 等于 16
B 接近但小于 16
C 接近但大于 16
D 前三种情况都有可能
解析：【喵呜刷题小喵解析】根据题目中的代码，我们知道当输入的n为256，k为11时，程序会先调用solve1函数，该函数会寻找一个mid值，使得mid的平方小于等于n，即256。在while循环中，当mid的平方小于等于n时，l会更新为mid+1，否则r会更新为mid-1。最终，函数返回l-1，也就是mid的值。所以solve1函数的返回值接近但小于16。
然后，主函数main会调用solve2函数，并将solve1函数的返回值作为参数传入。solve2函数会对传入的参数进行k次迭代，每次迭代都会更新x的值为(x + n / x) / 2。由于solve1函数的返回值接近但小于16，所以solve2函数的返回值也会接近但小于16。
因此，输出的第一个数接近但小于16，选项B正确。
（枚举因数）从小到大打印正整数 n 的所有正因数。
试补全枚举程序。
01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int main() {
05 int n;
06 cin >> n;
07
08 vector<int> fac;
09 fac.reserve((int)ceil(sqrt(n)));
10
11 int i;
12 for (i = 1; i * i < n; ++i) {
13 if (①) {
14 fac.push_back(i);
15 }
16 }
17
18 for (int k = 0; k < fac.size(); ++k) {
19 cout << ② << " ";
20 }
21 if (③) {
22 cout << ④ << " ";
23 }
24 for (int k = fac.size() - 1; k >= 0; --k) {
25 cout << ⑤ << " ";
26 }
27 }
35、①处应填（ ）
A n % i == 0
B n % i == 1
C n % (i-1)== 0
D n % (i-1) == 1
解析：【喵呜刷题小喵解析】：对于枚举正整数n的所有正因数的程序，当i从1到sqrt(n)进行枚举时，我们需要判断n是否能被i整除。所以①处应填“n % i == 0”，表示n能被i整除。选项A正确。选项B、C、D均不符合题意。
36、②处应填（ ）
A n / fac[k]
B fac[k]
C fac[k]-1
D n / (fac[k]-1)
解析：【喵呜刷题小喵解析】：根据题目要求，我们需要从小到大打印正整数 n 的所有正因数。程序中已经有一个存储因数的数组fac，以及一个用于遍历的变量i。当i为n的因数时，将i添加到fac数组中。所以，在②处，应该打印出fac[k]，即当前遍历到的因数。因此，选项B "fac[k]" 是正确的。
37、③处应填（ ）
A (i-1) * (i-1) == n
B (i-1) * i == n
C i * i == n
D i * (i-1) == n
解析：【喵呜刷题小喵解析】：
枚举因数时，我们只需要枚举到sqrt(n)即可，因为n的因数不可能大于sqrt(n)。对于每个i，我们需要检查i*i是否等于n，如果等于，说明i是n的一个因数。
在③处，我们需要检查i*i是否等于n，所以应该填"i * i == n"。
选项A：(i-1) * (i-1) == n，这个表达式是错误的，因为i-1可能不是n的因数。
选项B：(i-1) * i == n，这个表达式也是错误的，因为i和i-1的乘积可能不等于n。
选项D：i * (i-1) == n，这个表达式同样是错误的，因为i和i-1的乘积可能不等于n。
所以，正确答案是选项C：i * i == n。
38、④处应填（ ）
A n-i
B n-i+1
C i-1
D i
解析：【喵呜刷题小喵解析】
在枚举因数的过程中，我们需要找到n的所有正因数。对于每一个i，如果i是n的因数，那么n/i也是n的因数。因此，我们需要将i和n/i都加入到fac向量中。
在给出的代码中，①处应该填写n % i == 0，表示i是n的因数。
对于④处，我们需要输出n/i，因为n/i也是n的因数。所以，④处应该填写n/i。
因此，正确答案是D选项，即i。
39、⑤处应填（ ）
A n / fac[k]
B fac[k]
C fac[k]-1
D n / (fac[k]-1)
解析：【喵呜刷题小喵解析】：
根据题目要求，我们需要从小到大打印正整数n的所有正因数。
在程序中，我们使用了两个循环。第一个循环用于枚举n的因数，第二个循环用于打印这些因数。
对于⑤处，我们需要打印当前的因数fac[k]。这是因为我们已经将因数存储在了fac数组中，所以只需要打印数组中的元素即可。
因此，⑤处应填fac[k]。
（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。
试补全程序。
01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int ROWS = 8;
05 const int COLS = 8;
06
07 struct Point {
08 int r, c;
09 Point(int r, int c) : r(r), c(c) {}
10 };
11
12 bool is_valid(char image[ROWS][COLS], Point pt,
13 int prev_color, int new_color) {
14 int r = pt.r;
15 int c = pt.c;
16 return (0 <= r && r < ROWS && 0 <= c && c < COLS &&
17 ① && image[r][c] != new_color);
18 }
19
20 void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
21 queue<Point> queue;
22 queue.push(cur);
23
24 int prev_color = image[cur.r][cur.c];
25 ② ;
26
27 while (!queue.empty()) {
28 Point pt = queue.front();
29 queue.pop();
30
31 Point points[4] = { ③ , Point(pt.r - 1, pt.c),
32 Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
33 for (auto p : points) {
34 if (is_valid(image, p, prev_color, new_color)) {
35 ④ ;
36 ⑤ ;
37 }
38 }
39 }
40 }
41
42 int main() {
43 char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
44 {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
45 {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
46 {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
47 {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
48 {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
49 {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
50 {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
51
52 Point cur(4, 4);
53 char new_color = 'y';
54
55 flood_fill(image, cur, new_color);
56
57 for (int r = 0; r < ROWS; r++) {
58 for (int c = 0; c < COLS; c++) {
59 cout << image[r][c] << " ";
60 }
61 cout << endl;
62 }
63 // 输出：
64 // g g g g g g g g
65 // g g g g g g r r
66 // g r r g g r g g
67 // g y y y y r g r
68 // g g g y y r g r
69 // g g g y y y y r
70 // g g g g g y g g
71 // g g g g g y y g
72
73 return 0;
74 }
40、①处应填（ ）
A image[r][c] == prev_color
B image[r][c] != prev_color
C image[r][c] == new_color
D image[r][c] != new_color
解析：【喵呜刷题小喵解析】：根据题目描述，函数`is_valid`的作用是判断一个点是否有效，即该点是否满足以下条件：
1. 在图像范围内（即行和列都在0到7之间）
2. 该点的颜色与起始点的颜色相同
3. 该点的颜色不是待填充的颜色
因此，①处应该填写`image[r][c] == prev_color`，表示该点的颜色与起始点的颜色相同。选项A正确。
41、②处应填（ ）
A image[cur.r+1][cur.c] = new_color
B image[cur.r][cur.c] = new_color
C image[cur.r][cur.c+1] = new_color
D image[cur.r][cur.c] = prev_color
解析：【喵呜刷题小喵解析】：根据洪水填充算法，起始像素的颜色应该被替换为新的颜色。因此，在②处，应该填写`image[cur.r][cur.c] = new_color`，将当前像素的颜色设置为新的颜色。选项B正确。
42、③处应填（ ）
A Point(pt.r, pt.c)
B Point(pt.r, pt.c+1)
C Point(pt.r+1, pt.c)
D Point(pt.r+1, pt.c+1)
解析：【喵呜刷题小喵解析】：
题目中给出的是一个用于实现颜色填充的洪水填充算法，其中`Point`结构体表示一个点的坐标，`is_valid`函数用于判断一个点是否有效，`flood_fill`函数是主要的填充函数。
在`flood_fill`函数中，`points`数组用于存储当前点的四个相邻点，即上、下、左、右四个方向。根据题目中的描述，`points`数组应该包含当前点的四个相邻点，所以应该填入`Point(pt.r + 1, pt.c)`, `Point(pt.r - 1, pt.c)`, `Point(pt.r, pt.c + 1)`, `Point(pt.r, pt.c - 1)`。
因此，选项A `Point(pt.r, pt.c)`是错误的，因为它只是当前点本身，而不是相邻点。选项B `Point(pt.r, pt.c+1)`和选项D `Point(pt.r+1, pt.c+1)`都只考虑了上下或左右一个方向，没有包含所有四个方向的相邻点。
所以，正确答案是选项C `Point(pt.r+1, pt.c)`。
43、④处应填（ ）
A prev_color = image[p.r][p.c]
B new_color = image[p.r][p.c]
C image[p.r][p.c] = prev_color
D image[p.r][p.c] = new_color
解析：【喵呜刷题小喵解析】：在洪水填充算法中，当判断一个像素点是否有效（即颜色与起始像素相同）时，如果有效，需要将该像素点的颜色替换为新的颜色。因此，在④处应填入的代码是将当前像素点的颜色设置为新的颜色，即`image[p.r][p.c] = new_color`。选项D正确。
44、⑤处应填（ ）
A queue.push(p)
B queue.push(pt)
C queue.push(cur)
D queue.push(Point(ROWS,COLS))
解析：【喵呜刷题小喵解析】：在程序中，我们需要将满足条件的像素点加入到队列中，以便后续继续填充。根据程序的逻辑，我们在循环中定义了一个`p`变量，它是`points`数组中的一个元素，表示当前像素点的相邻像素点。如果`p`满足条件，我们就需要将`p`加入到队列中，所以⑤处应该填写`queue.push(p)`。选项A中的`queue.push(p)`正是这个操作，所以答案是A。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
