一、单项选择题（共15题，每题2分，共计30分）

第1题

下列哪个不是操作系统？（）

• A. Android
• B. Windows
• C. Linux
• D. QQ

答案：D

解析：

• 选项A（Android）：由Google主导开发的移动操作系统，基于Linux内核，广泛应用于智能手机、平板电脑、智能手表、智能电视等移动设备，属于操作系统。
• 选项B（Windows）：微软公司开发的图形化操作系统，支持个人电脑（PC）、服务器、嵌入式设备等多种硬件，是主流桌面操作系统之一，属于操作系统。
• 选项C（Linux）：由Linus Torvalds开发的开源操作系统内核，遵循Unix设计哲学，可搭配不同发行版（如Ubuntu、Fedora）用于服务器、超级计算机、个人电脑等，属于操作系统。
• 选项D（QQ）：腾讯公司开发的即时通讯软件，功能是实现用户间的聊天等社交互动，需依赖操作系统运行，属于应用软件，而非操作系统。

第2题

小K是一名摄影爱好者，他购买了一个容量为1TB的移动硬盘，用于存储图片。若每张图片的平均大小为5MB，则该硬盘大约可以存储多少张这样的图片？（）

• A. ($2×10^{4}$)
• B. ($2×10^{5}$)
• C. ($2×10^{6}$)
• D. ($2×10^{7}$)

答案：D

解析： 首先明确存储单位换算关系：计算机存储中，($1TB = 1024GB$)，($1GB = 1024MB$)。 为简化计算可近似为($1TB = 1024×1024MB≈10^{7}MB$)。 计算可存储图片数量：总容量÷单张图片大小，即($10^{7}÷5 = 2×10^{6}$)（张）。 故正确答案为D。

第3题

以下关于进制转换的描述中，不正确的是？（）

• A. 二进制数1111转换为十进制数是15
• B. 十进制数31转换为十六进制数是1F
• C. 十六进制数A6转换为二进制数是10100110
• D. 八进制数22转换为十进制数是20

答案：D

解析：

• 选项A：二进制数1111转十进制，按“位权展开法”计算：($1×2^{3}+1×2^{2}+1×2^{1}+1×2^{0}=8 + 4 + 2 + 1 = 15$)，转换正确。
• 选项B：十进制数31转十六进制，利用“短除法”计算得到余数按计算顺序是15（F）和1，余数15在十六进制中用字母F表示，逆序排列后得到1F，故结果为1F，转换正确。
• 选项C：十六进制数转二进制需“一位拆四位”，A（十进制10）拆为1010，6拆为0110，组合后为10100110，转换正确。
• 选项D：八进制数22转十进制，按“位权展开法”计算：($2×8^{1}+2×8^{0}=16 + 2 = 18≠20$)，转换错误。

第4题

($(11)_2 + (11)_8$)的结果是？（）

• A. ($(22)_{10}$)
• B. ($(1111)_2$)
• C. ($(C)_{16}$)
• D. ($(22)_8$)

答案：C

解析：

• 第一步：将不同进制数统一转为十进制计算：
  • 二进制($(11)_2$)：($1×2^{1}+1×2^{0}=2 + 1 = 3$)；
  • 八进制($(11)_8$)：($1×8^{1}+1×8^{0}=8 + 1 = 9$)；
  • 两者之和：($3 + 9 = 12$)（十进制）。

• 第二步：验证选项：

• A. ($(22)_{10}=22≠12$)；
  • • B. ($(1111)_2=1×2^{3}+1×2^{2}+1×2^{1}+1×2^{0}=15≠12$)；
  • • C. 十六进制中，C对应十进制12，故($(C)_{16}=12$)，符合结果；
  • • D. ($(22)_8=2×8^{1}+2×8^{0}=18≠12$)。

第5题

已知中缀表达式：($(A + B)*C - D$)，其中A、B、C、D为操作数。以下哪个后缀表达式是正确的？（）

• A. ($AB + C*D -$)
• B. ($AB + CD*-$)
• C. ($AB + CD*-$)
• D. ($ABC* + D -$)

答案：A

解析：

1. 处理括号内的($(A + B)$)：操作数A、B在前，运算符“+”在后，得到“($AB+$)”；
2. 处理乘法($(A + B)*C$)：将“($AB+$)”视为整体操作数，与C结合，运算符“*”在后，得到“($AB + C*$)”；
3. 处理减法($(A + B)*C - D$)：将“($AB + C*$)”视为整体操作数，与D结合，运算符“-”在后，最终得到“($AB + C*D -$)”，对应选项A。

第6题

在C++语言中，二维数组($a[10][20]$)从内存地址1000开始存储，每个元素占4字节。假设按行优先顺序存储，请问($a[5][10]$)的地址是多少？（）

• A. 1424
• B. 1444
• C. 1420
• D. 1440

答案：D

解析： C++中二维数组按“行优先”存储。 地址计算公式为：($a[i][j]$)地址 = 基地址 + ($(i×列数 + j)×$)每个元素字节数。 本题基地址：1000、行数：10行、列数：20列。 ($a[5][10]$)地址 = ($1000 + (5×20 + 10)×4 = 1000 + 110×4 = 1440$)。

第7题

序列1,2,3,4,5依次进入一个初始为空的栈中（1第一个进入栈），在每个元素入栈后，可以随时进行出栈操作（也可以是空操作）。以下哪个选项不可能是从栈中弹出的序列？（）

• A. 1,2,3,4,5
• B. 5,4,3,2,1
• C. 2,1,5,4,3
• D. 3,1,2,4,5

答案：D

解析： 栈是“先进后出”的数据结构。

• 选项A：每次入栈一个元素就出栈，可得到该序列；
• 选项B：全部入栈后再依次出栈，可得到该序列；
• 选项C：1、2入栈，出栈2，再出栈1；3、4、5入栈，出栈5，再出栈4，最后出栈3，可得到该序列；
• 选项D：3出栈后，栈内还剩1、2（2在栈顶），接下来出栈的应该是2，而不是1，所以该序列不可能。 要首先弹出3，需1、2、3依次入栈，弹出3后栈顶为2。接下来若要弹出1，必须先弹出2，无法直接弹出1，所以选项D的序列不可能。

第8题

对图进行深度优先遍历（DFS），从顶点1出发，不可能的访问顺序是（）

• A. 1,3,5,2,4
• B. 1,2,3,5,4
• C. 1,2,4,3,5
• D. 1,3,2,5,4

答案：D

解析： DFS规则是“一条路走到底，无法前进再回溯——从起点出发，优先访问当前节点的未访问‘邻居’，直至无新节点可访问，再返回上一节点继续探索”。

• 选项A：从($1→3→5$)，到5无新邻居，回溯到3，3还有未访问邻居2，走($3→2$)，再走($2→4$)，完全合法。
• 选项B：从($1→2→3→5$)，5回溯到3，3无其他未访问邻居，再回溯到2，然后去4，2还有未访问邻居4，所以($2→4$)合法。
• 选项C：从($1→2→4$)，回溯到2，2还有未访问邻居3，所以($2→3$)合理，接着去($3→5$)，合法。
• 选项D：如果走($1→3→2$)，现在在顶点2，其未访问邻居有4，所以下一步必须访问4，处理完4，再回溯到3，最后走5。但这个序列是($1,3,2,5,4$)，通过分析已知从2无法直接跳到5，所以这个序列不合法。

第9题

用数字0、1、2、3、4、5组成没有重复数字的四位数，其中千位数字不能为0，而且不能出现“250”形式（如1250，2503），这样的四位数共有多少个？（）

• A. 240
• B. 294
• C. 300
• D. 288

答案：B

解析：

• 第一步：计算所有无重复数字且千位非0的四位数个数。千位有5种选择（1、2、3、4、5），百位从剩下5个数字（含0）选，有5种选择，十位从剩下4个数字选，有4种选择，个位从剩下3个数字选，有3种选择。总数为($5×5×4×3 = 300$)。
• 第二步：减去包含“250”形式的数。情况1：千位、百位、十位为2、5、0（即250X形式），个位从剩下3个数字（1、3、4）选，有3个数（2501、2503、2504）；情况2：百位、十位、个位为2、5、0（即X250形式），千位从1、3、4选，有3个数（1250、3250、4250）。总共禁止的数字有($3 + 3 = 6$)。最终符合要求的四位数个数为($300 - 6 = 294$)。

第10题

一个($4×5$)的网格，从左上角A走到右下角B（只能沿着向右或向下的方向走）共有多少种方案？（）

• A. 10
• B. 15
• C. 20
• D. 35

答案：D

解析： 从起点A到终点B，需要向右移动4次（从第1列到第5列），向下移动($4 - 1 = 3$)次（从第1行到第4行），总移动次数为($4 + 3 = 7$)次。这相当于从7次移动中选3次向下（或4次向右），根据组合数公式($C_{n}^k=\frac{n!}{k!(n - k)!}$)，可得方案数为($C_{7}^3=\frac{7!}{3!(7 - 3)!}=\frac{7×6×5}{3×2×1}=35$)。

第11题

下列代码片段运行后输出结果为22，则输入的正整数k的最大值为（）

int n = 1, s = 1, k;
cin >> k;
while (n < k)
{
    s = (s << 1) + n;
    n = n * (n + 1);
}
cout << s;

• A. 41
• B. 42
• C. 43
• D. 86

答案：B

解析： 模拟循环过程：

• 初始：($n = 1$)，($s = 1$)。
• 第1次：($s = 2×1 + 1 = 3$)，($n = 1×2 = 2$)。
• 第2次：($s = 2×3 + 2 = 8$)，($n = 2×3 = 6$)。
• 第3次：($s = 2×8 + 6 = 22$)，($n = 6×7 = 42$)。
• 第4次：($s = 2×22 + 42 = 86$)，($n = 42×43 = 1806$)。

第三次迭代后，($s = 22$)，($n = 42$)。若此时($n \geq k$)，循环退出，输出($s = 22$)。要使循环在此退出，需($42 \geq k$)，所以($k$)最大值为42。

第12题

如果根节点深度记为1，则一棵恰好有2025个度（儿子节点数量）为1的节点的二叉树深度最少可以是多少？（）

• A. 11
• B. 12
• C. 13
• D. 14

答案：C

解析： 要使树深度最小，需让树“长得胖而不是高”。先构建“基础树”（尽量丰满，用度为2的节点和根节点组成），再把2025个度为1的节点“分散挂”在基础树分支上。深度为($h$)的满二叉树，叶子节点（最底层节点）数量是($2^{(h - 1)}$)个。通过计算，当深度为13时，能满足有2025个度为1的节点且深度最少。 C选项和D选项都能构造恰好有2025个度为1的节点的二叉树，但要选深度最小的，所以正确答案为C选项。

第13题

小H的作业有8道题目，小H对了5道，而且恰好有3道是连续做对的，请问总共有多少种可能的情况（）

• A. 24
• B. 12
• C. 36
• D. 25

答案：A

解析： 把连续3个“√”视为一个整体（记为A），剩余2个“√”为单独个体（记为a和b）。3道“×”将序列分割为4个空位。从4个空位中选3个放置A、a、b（元素间不相邻），选法有($C(4,3)=4$)种。选出3个空位后，A、a、b全排列有($3!=6$)种。总可能情况为($4×6 = 24$)，所以正确答案为A选项。

第14题

以下C++递归函数的输出是什么？

int f(int i)
{
    if (i == 1) return 1;
    return i * f(i - 1);
}
int main() {
    cout << f(5);
    return 0;
}

答案：D

解析： 函数f是计算阶乘的递归函数。 当i == 1时，返回1（阶乘的基本情况：($1! = 1$)）。 否则，返回($i × f(i - 1)$)（阶乘的递归关系：($i! = i × (i - 1)!$)）。 计算过程： ($f(5) = 5 × f(4)$) ($f(4) = 4 × f(3)$) ($f(3) = 3 × f(2)$) ($f(2) = 2 × f(1)$) ($f(1) = 1$)（触发基本情况，返回1） 所以($f(5)=5 × f(4)=5×4 × f(3)=5×4×3 × f(2)=5×4×3×2 × f(1)=5×4×3×2×1 = 120$)。 所以正确答案为D选项。

第15题

以下排序算法中，哪一种是非基于比较的排序算法？（）

• A. 冒泡排序
• B. 选择排序
• C. 插入排序
• D. 计数排序

答案：D

解析：

• 基于比较的排序：通过比较元素之间的大小来确定位置，如冒泡排序（反复比较交换相邻元素）、选择排序（比较找出最值并交换）、插入排序（将元素与已排序部分比较后插入）。它们的时间复杂度下限为($O(n \log n)$)。
• 非基于比较的排序：不依赖元素间的大小比较，而是利用元素的具体数值特征或分布范围来排序。例如计数排序，它通过统计每个数值出现的次数，直接计算出元素在结果中的位置，时间复杂度可达($O(n + k)$)（($k$)为数值范围）。

所以正确答案为D选项。

二、程序阅读

(1)

#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int main() {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%d\n", gcd(x, y));
    return 0;
}

完成下面的判断题和单选题：

判断题：

16. (1分) 在递归函数gcd中，当b等于0时，函数返回a，递归结束。（） 答案：正确 解析：在递归函数gcd中，当b == 0时，根据欧几里得算法，此时a就是两个数的最大公约数，函数返回a，递归结束，该说法正确。

17. 在递归调用gcd(b, a % b)时，a % b的值小于b。（） 答案：正确 解析：根据取余运算的性质，对于任意整数a和正整数b，a % b的结果一定是小于b且大于等于0的整数，该说法正确。

18. 递归函数gcd(a,b)能够正确的求出任意两个整数的最大公约数。（） 答案：错误 解析：欧几里得算法（即该递归函数gcd的实现原理）要求求的是两个正整数的最大公约数。如果输入的是负数，该函数不能正确求出最大公约数。所以该函数能正确求出任意两个整数的最大公约数，该说法错误。

单选题：

19. 当输入为24和18时，程序的输出是（）

• A. 6
• B. 12
• C. 18
• D. 24 答案：A 解析：计算gcd(24, 18)，因为18 != 0，所以调用gcd(18, 24 % 18)，24 % 18 = 6，调用gcd(6, 18 % 6)，18 % 6 = 0。此时b = 0，返回a = 6，所以程序输出6，答案选A。

20. 当输入为11和3时，递归函数gcd被调用的次数（包括第一次调用）是（）

• A. 2
• B. 3
• C. 4
• D. 5 答案：C 解析：
• 第一次调用：gcd(11, 3)，因为3 != 0，调用gcd(3, 11 % 3)，11 % 3 = 2。
• 第二次调用：gcd(3, 2)，因为2 != 0，调用gcd(2, 3 % 2)，3 % 2 = 1。
• 第三次调用：gcd(2, 1)，因为1 != 0，调用gcd(1, 2 % 1)，2 % 1 = 0。
• 第四次调用：gcd(1, 0)，此时b = 0，返回a = 1。

包括第一次调用在内，gcd函数共被调用4次。

判断题

21. (1分) 将第一行#include<bits/stdc++.h>改成#include<iostream>不会影响程序正常运行。（） 答案：错误 解析：原程序中使用了cin、cout和sort函数。#include<bits/stdc++.h>包含了所有标准库，而#include<iostream>只包含输入输出流库，不包含sort函数所需的算法库。因此替换后程序会因缺少sort函数的声明而无法编译，该说法错误。

22. 变量ans记录的是a序列中非负数的个数。（） 答案：错误 解析：ans不仅统计非负数的个数，还会统计一部分负数（当m足够抵消该负数绝对值时）。例如，若m足够大，程序会将符合条件的负数也计入ans，因此该说法错误。

23. 如果a序列有小于0的元素，程序运行结束后m的值一定发生变化。（） 答案：错误 解析：如果a序列中的负数绝对值均大于m，则程序不会选择任何负数（循环直接break），m的值保持不变。因此“一定发生变化”的说法错误。

单选题

24. 该程序时间复杂度为（）。

• A. ($O(n)$)
• B. ($O(n\log n)$)
• C. ($O(n^{2})$)
• D. 不确定 答案：B 解析：程序的主要耗时操作是sort，排序算法的时间复杂度为($O(n\log n)$)，后续的循环操作是($O(n)$)。整体时间复杂度由排序主导，因此答案选B。

25. 对于以下输入数据，执行完程序后，a数组的值为（）

输入数据：

5 5
1 -3 -6 5 -2

选项：

• A. [1, -3, -6, 5, -2]
• B. [-6, -3, -2, 1, 5]
• C. [-6, 0, 0, 1, 5]
• D. [5, 1, -2, -3, -6]

答案：B 解析：程序中sort(a + 1, a + n + 1)对数组从索引1开始进行升序排序。输入数组[1, -3, -6, 5, -2]排序后为[-6, -3, -2, 1, 5]，且排序后数组元素值不会被修改，因此答案选B。

26. 对于以下输入数据，输出结果为（）。

输入数据：

8 100
-91 30 -20 233 -30 -50 -50 -20

选项：

• A. 4
• B. 5
• C. 6
• D. 8

答案：B 解析：输入数据排序后为[-91, -50, -50, -30, -20, -20, 30, 233]（升序），循环从末尾（最大元素）开始处理：

1. 非负数233、30：ans累计2，m不变（仍为100）。
2. 负数-20：绝对值20≤100，m变为80，ans = 3。
3. 负数-20：绝对值20≤80，m变为60，ans = 4。
4. 负数-30：绝对值30≤60，m变为30，ans = 5。
5. 负数-50：绝对值50＞30，循环终止。 最终ans = 5，答案选B。

(3)

#include <bits/stdc++.h>
using namespace std;
int n;
int f1(int n) {
    int res = 0;
    for (int i = 2; i <= n; i += 2) {
        int j = i;
        while (j % 2 == 0) {
            res++;
            j /= 2;
        }
    }
    return res;
}
int f2(int n) {
    int res = 0;
    while (n) {
        n /= 5;
        res += n;
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    cout << min(f1(n), f2(n));
    return 0;
}

判断题

27. 将第8行的j%2==0改为!(j&1)程序功能不变。（） 答案：正确 解析：j%2==0判断j是否为偶数，j&1是位运算，当j为偶数时结果为0，!(j&1)结果为真。两者逻辑等价，替换后程序功能不变，该说法正确。

28. f2函数一定比f1函数运行速度快。（） 答案：错误 解析：f2函数的时间复杂度为($O(\log_{5}n)$)，f1函数的时间复杂度约为($O(n\log n)$)。对于较大的($n$)，f2确实更快，但题目中“一定”过于绝对（如极小数($n = 2$)时两者速度差异可忽略）。因此该说法错误。

29. 该程序能求出($n! (1×2×3×...×n)$)结果中0的个数。（） 答案：正确 解析：($n!$)末尾0的个数由因数中2和5的对数决定（每对($2×5$)产生一个0）。($f1(n)$)统计($1 - n$)中所有数的因数2的总个数，($f2(n)$)统计因数5的总个数，程序取两者最小值，正是($n!$)末尾0的个数。该说法正确。

单选题

30. 下面说法正确的是（）。

• A. ($f2(n)$)的值一定小于($f1(n)$)的值
• B. 第25行如果改为输出($f2(n)$)，程序结果不会发生改变。
• C. ($f1$)函数的作用是求1到($n$)中所有能被2整除的数的个数。
• D. 如果输入($n$)为负整数，程序会陷入死循环。

答案：D 解析：

• 选项A：($n = 1$)时，($f1 = 0$)，($f2 = 0$)，两者相等，故选项A错误。

30. 下面说法正确的是（）。

选项：

• A. ($f2(n)$)的值一定小于($f1(n)$)的值
• B. 第25行如果改为输出($f2(n)$)，程序结果不会发生改变。
• C. ($f1$)函数的作用是求1到($n$)中所有能被2整除的数的个数。
• D. 如果输入($n$)为负整数，程序会陷入死循环。

答案：D 解析：

• 选项A：($n = 1$)时，($f1 = 0$)，($f2 = 0$)，两者相等，故选项A错误。
• 选项B：程序结果是($\min(f1, f2)$)，当($f1 < f2$)时，输出($f1$)，与输出($f2$)结果不同，故选项B错误。
• 选项C：($f1$)统计的是($1 - n$)中所有数的因数2的总个数，故选项C错误。
• 选项D：($f2$)中($n$)为负数，($n /= 5$)始终为负数，陷入死循环，故选项D正确。

31. 如果输入的($n = 20$)，则($f1(n)$)的值为（）。

选项：

• A. 2
• B. 10
• C. 17
• D. 18

答案：D 解析：计算($f1(20)$)（统计($1 - 20$)中所有数的因数2的总个数）：

• 2：1个；4：2个；6：1个；8：3个；10：1个；12：2个；14：1个；16：4个；18：1个；20：2个。
• 总和：($1 + 2 + 1 + 3 + 1 + 2 + 1 + 4 + 1 + 2 = 18$)，答案选D。

32. 对于以下输入数据，输出结果为（）。

输入：

1000

选项：

• A. 200
• B. 248
• C. 249
• D. 252

答案：C 解析：

• ($f2(1000)$)：统计($1 - 1000$)中因数5的总个数。
• ($f1(1000)$)：统计($1 - 1000$)中因数2的总个数。
• 根据数学知识，在($1 - 1000$)之间，因数2的总个数远大于因数5的总个数，所以计算($f2(1000)$)即可。
• ($f2(1000) = 1000/5 + 1000/25 + 1000/125 + 1000/625 = 200 + 40 + 8 + 1 = 249$)，正确答案为C选项。

35. ③处应填（）。

选项：

• A. ($n - 1$)
• B. ($n$)
• C. ($n + 1$)
• D. ($n - 2$)

答案：D 解析：根据题意，($k$)的取值范围是($1\leq k\leq n - 2$)（去掉前($k$)道题后，至少剩余2道题，才能再去掉1道最低分）。循环变量($i$)代表($k$)，因此循环上限应为($n - 2$)。

36. ④处应填（）。

选项：

• A. ($(suf[i + 1] - minm[i + 1])/(n - i)$)
• B. ($(suf[i + 1] - minm[i + 1])/(n - i - 1)$)
• C. ($1.0*(suf[i] - minm[i])/(n - i - 1)$)
• D. ($1.0*(suf[i + 1] - minm[i + 1])/(n - i - 1)$)

答案：D 解析：当($k = i$)时，需计算的是从($i + 1$)到($n$)的题目（共($n - i$)道）中，去掉最低分后的平均分：

• 总和为($suf[i + 1]$)（($i + 1$)到($n$)的和）。
• 最低分为($minm[i + 1]$)（($i + 1$)到($n$)的最小值）。
• 有效题目数量为($(n - i) - 1 = n - i - 1$)（去掉最低分后）。
• 需乘以($1.0$)确保计算结果为浮点数（避免整数除法）。 因此④处应填：($1.0*(suf[i + 1] - minm[i + 1])/(n - i - 1)$)。

37. ⑤处应填（）。

选项：

• A. ($cnt = 0$)
• B. ($cnt++$)
• C. ($cnt = 1$)
• D. ($cnt--$)

答案：A 解析：当找到更高的平均分（($tmp > maxn$)）时，需要清空之前记录的($k$)值，重新记录当前($k$)。($cnt$)用于统计有效($k$)的数量，此时应重置为($0$)，再记录新的($k$)。因此⑤处应填：($cnt = 0$)。

38. ①处应填（）

选项：

• A. int f[N][1000000001]
• B. int f[N][N*1000]
• C. long long f[N][1000000001]
• D. long long f[N][N*1000]

答案：D 解析：

• ($f[i][j]$)的含义是：前($i$)件物品中，达到价值($j$)所需的最小重量。
• 价值上限($sv$)是所有物品价值之和，($n\leq100$)且($v[i]\leq10^3$)，因此($sv\leq100×10^3 = 10^5$)，数组第二维大小应为($N×1000$)（足够存储所有可能价值）。
• 重量可能较大（单物品重量($10^9$)，100件总重可达($10^{11}$)），需用long long防止溢出。 因此①处应填：long long f[N][N*1000]。

39. ②处应填（）

选项：

• A. f[0][0]=0x3f3f3f3f
• B. f[0][0]=0x3f3f3f3f3f3f3f3f
• C. f[0][0]=0
• D. f[0][0]=1

答案：C 解析：

• 初始化状态：($f[0][0]$)表示($0$)件物品，价值($0$)所需的最小重量，显然为($0$)。
• memset(f,0x3f,sizeof(f))已将数组初始化为极大值（表示不可达），需单独设置($f[0][0]=0$)作为基准状态。 因此②处应填：f[0][0]=0。

40. ③处应填（）

选项：

• A. j<sv
• B. j<=sv
• C. j<sw
• D. j<=sw

答案：B 解析：

• 循环变量($j$)表示价值，需遍历所有可能的价值（从($0$)到总价值($sv$)）。
• 因此循环条件应为($j<=sv$)，确保覆盖所有可能的价值状态。

41. ④处应填（）

选项：

• A. min(f[i][j],f[i-1][j-v[i]]+w[i])
• B. min(f[i][j],f[i-1][j-w[i]]+v[i])
• C. max(f[i][j],f[i-1][j-v[i]]+w[i])
• D. max(f[i][j],f[i-1][j-w[i]]+v[i])

答案：A 解析：

• 状态转移逻辑：对于第($i$)件物品，若选择放入（需满足($v[i]<=j$)），则新重量为“前($i - 1$)件物品达到价值($j - v[i]$)的重量”加上当前物品重量($w[i]$)。
• ($f[i][j]$)取“不放入”（($f[i - 1][j]$)）和“放入”（($f[i - 1][j - v[i]] + w[i]$)）中的最小值（最小重量）。 因此④处应填：min(f[i][j],f[i-1][j-v[i]]+w[i])。

42. ⑤处应填（）

选项：

• A. f[n][i]<sv
• B. f[n][i]<=sv
• C. f[n][i]<sw
• D. f[n][i]<=sw

答案：D 解析：

• 最终需找到最大价值($i$)，使得达到该价值的最小重量（($f[n][i]$)）不超过背包容量($sw$)。
• 因此判断条件为($f[n][i]<=sw$)。