普及组初赛模拟28

一、选择题

1. 计算机中央处理器简称为（ ）。 {{ select(1) }}

• CPU
• RAM
• ROM
• LAN

2. 1946年2月，在美国宾夕法尼亚大学诞生的世界上第一台电子计算机是（ ）。 {{ select(2) }}

• ICPC
• ENIAC
• ECF
• GGF

3. 计算机直接识别和执行的语言是（ ）。 {{ select(3) }}

• $C++$
• 汇编语言
• 高级语言
• 机器语言

4. 八进制数15264转换成的二进制数是（ ）。 {{ select(4) }}

• 001101010110100
• 101101011010101
• 001011000110100
• 001101010100110

5. 计算机所能辨认的最小信息单位是（ ）。 {{ select(5) }}

• 字节
• KB
• 位
• TB

6. 设 $a = false$, $b = true$, $c = true$, 以下表达式为假的是（ ）。 {{ select(6) }}

• $(a \land b) \land c$
• $(a \land b) \lor (b \land c)$
• $(a \lor b) \land c$
• $(a \lor c) \land (c \land b)$

7. 一个二叉搜索树前序遍历的结果为7, 2, 1, 5, 13, 9, 这棵树的根的左子树有多少个节点？（ ）。 {{ select(7) }}

• 2
• 5
• 4
• 3

8. 小明一次可以跨上一阶台阶或两阶台阶。他从第一阶台阶出发，有多少种方案恰好到达第10阶台阶？（ ）。 {{ select(8) }}

• 53
• 55
• 54
• 57

9. 冒泡排序的复杂度为（ ）。 {{ select(9) }}

• $O(n)$
• $O(\log n)$
• $O(n^2)$
• $O(\log^2 n)$

10. 有18个表观完全相同的零件，其中有且仅有一个是质量略轻的次品零件。有一个天平，但是没有砝码，可以用干比较左右两个盘中物体的质量。最坏情况下，最少需要多少次称量可以找到这个次品零件？（ ）。 {{ select(10) }}

• 3
• 4
• 6
• 9

11. 甲乙丙丁四个人被安排完成三份代码，每份代码至少需要一个人完成，且一个人只能去完成一份代码，甲乙有矛盾不能完成同一份代码，有多少种合理的安排方式？（ ）。 {{ select(11) }}

• 12
• 30
• 48
• 36

12. [后进先出]的数据结构是（ ）。 {{ select(12) }}

• 链表
• 队列
• 邻接表
• 栈

13. 所有满足除以3的余数为2，除以7的余数为1中，最小的数是8，第五小的数是（ ）。 {{ select(13) }}

• 40
• 50
• 71
• 92

14. 小于28的正整数中，与28互质的数的个数为（ ）。 {{ select(14) }}

• 10
• 11
• 12
• 13

15. 2021年7月1日是星期四，我们热烈庆贺了中国共产党成立一百周年，完成了两个一百年的第一个。我们将在2049年10月1日欢庆建国一百年，这一天是星期几？（ ）。 {{ select(15) }}

• 星期四
• 星期五
• 星期六
• 星期日

二、阅读程序

程序1

#include <iostream>
using namespace std;

int n, ans, C[105][105];

int main()
{
    cin >> n;
    C[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= i; j++)
            ans += C[i][j];
    cout << ans;
    return 0;
}

1. 所有数字均不会超过 int 上限。（ ） {{ select(16) }}

• 正确
• 错误

2. 将第 13 行的 $j <= i$ 改为 $j <= n$ 不影响程序的结果。（ ） {{ select(17) }}

• 正确
• 错误

3. 将第 9 行放在现在的第 15 行后不影响程序的结果。（ ） {{ select(18) }}

• 正确
• 错误

4. 如果输入的 $n$ 为 100，程序可能无法输出正确的结果。（ ） {{ select(19) }}

• 正确
• 错误

5. 若输入的 $n$ 为 7，输出为（ ）。 {{ select(20) }}

• 127
• 128
• 255
• 256

6. 为了保证所有整数均不溢出，$n$ 最大可以是（ ）。 {{ select(21) }}

• 20
• 24
• 28
• 30

程序2

#include <iostream>
using namespace std;

const int N = 1e6 + 5;

int n, cnt, Prime[N];
bool Vis[N];

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        if (!Vis[i])
            Prime[++cnt] = i;
        for (int j = 1; j <= cnt && (long long)i * Prime[j] <= n; j++)
        {
            int k = i * Prime[j];
            Vis[k] = true;
            if (i % Prime[j] == 0)
                break;
        }
    }
    cout << cnt;
    return 0;
}

1. 如果删去了第16行的强制类型转换 (long long)，输出的结果会发生变化。（ ） {{ select(22) }}

• 正确
• 错误

2. 当输入的 $n$ 为30时，输出为11。（ ） {{ select(23) }}

• 正确
• 错误

3. 第18行得到所有的 $k$ 互不相同。（ ） {{ select(24) }}

• 正确
• 错误

4. 下列做法不可能改变程序的结果的是（ ）。 {{ select(25) }}

• 将第12行的 $i = 2$ 改为 $i = 1$
• 将第20行的 $I\%Prime[j] == 0$ 改成 $k\%Prime[j] == 0$
• 将第19行的 $Vis[k] = true$ 改为 $Vis[k] = false$
• 将第20和21行同时删掉

5. 下列 $n$ 的取值中，输出的结果为25的是（ ）。 {{ select(26) }}

• 90
• 95
• 100
• 105

6. 这份代码的时间复杂度为（ ）。 {{ select(27) }}

• $O(n)$
• $O(n\log n)$
• $O(n\sqrt{n})$
• $O(n^2)$

程序3

#include <iostream>
using namespace std;

const int N = 1e4 + 5;

int n, A[N], B[N], C[N * 2];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> A[i]; 
    for (int i = 1; i <= n; i++) 
        cin >> B[i]; 
    for (int i = 1, j = 1, k = 1; i <= n || j <= n; k++) 
        if (i <= n && A[i] <= B[j]) 
            C[k] = A[i++]; 
        else 
            C[k] = B[j++]; 
    for (int i = 1; i <= 2 * n; i++) 
        cout << C[i] << " ";
    return 0;
}

1. 假设输入的 $n$ 是小于 $N$ 的正整数，数列 $A, B$ 中的数字均是 int 范围内的整数。（ ） {{ select(28) }}

• 正确
• 错误

2. 将第 16 行的 i <= n && \& 删去会影响输出的结果（ ）。 {{ select(29) }}

• 正确
• 错误

3. 将第 17 行的 $i++$ 改为 $++i$，同时将第 19 行的 $j++$ 改为 $++j$，不会影响输出的结果（ ）。 {{ select(30) }}

• 正确
• 错误

4. 若将第 15 行的 $||$ 改为 && ，一定有 $C[2 * n] == 0$（ ）。 {{ select(31) }}

• 正确
• 错误

5. 若数列 $A$ 是 1 5 7 8，数列 $B$ 是 2 3 6 9，则输出的数列 $C$ 是（ ）。 {{ select(32) }}

• 1 5 7 8 2 3 6 9
• 1 2 3 5 6 7 8 9
• 1 5 2 3 6 7 9 8
• 1 3 2 5 6 7 8 9

6. 若给定的数列 $A, B$ 严格递增，对于最后得到的数列 $C$，满足对任意正整数 $i(1 <= i < 2n)$（ ）。 {{ select(33) }}

• $C[i] < C[i+1]$
• $C[i] > C[i+1]$
• $C[i] <= C[i+1]$
• $C[i] >= C[i+1]$

7. 对于以下需求，这份代码可以满足的是（ ）。 {{ select(34) }}

• 给定两个递增数列 $A, B$，输出 $A, B$ 混合后的数列从小到大排序的结果
• 给定两个递增数列 $A, B$，输出 $A, B$ 混合后的数列从大到小排序的结果
• 给定两个递减数列 $A, B$，输出 $A, B$ 混合后的数列从小到大排序的结果
• 给定两个递减数列 $A, B$，输出 $A, B$ 混合后的数列从大到小排序的结果

三、完善程序

程序1

小C到商店购物,她只带了SW元钱。有n件商品,第i件商品的价格为Wz元,小C对它的满意度为Vz。小C想要知道,用自己仅有的SW元钱,能买到的所有商品的满意度之和最大是多少。数据保证1≤n≤100,1≤SW≤10000,1≤Wz≤100,1≤Vz≤100。

#include <iostream>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, SW, W[105], V[105], Dp[()];

int main()
{
    cin >> n >> SW;
    for (int i = 1; i <= n; i++)
        cin >> W[i] >> V[i];
    for (int i = 1; i <= SW; i++)
        Dp[i] = @;
    for (int i = 1; i <= n; i++)
        for (@)
            Dp[j] = max(Dp[j], @);
    int ans = 0;
    for (int i = 1; i <= SW; i++)
        @;
    cout << ans << "\n";
    return 0;
}

1. ①处应填（ ）。 {{ select(35) }}

• 100
• 105
• 10000
• 10005

2. ②处应填（ ）。 {{ select(36) }}

• INF
• 0
• $-2^{31}-1$
• 1

3. ③处应填（ ）。 {{ select(37) }}

• intj=SW;j>=W[i];j--
• intj=W[i];j<=SW;j++
• intj=1;j<=nj++
• intj=n;j>=1;j--

4. ④处应填（ ）。 {{ select(38) }}

• Dp[i-W[j]]+V[j]
• Dp[i-V[j]]+W[j]
• Dp[j-W[i]]+V[i]
• Dp[j-V[i]]+W[i]

5. ⑤处应填（ ）。 {{ select(39) }}

• $ans = \max(ans, Dp[i])$
• $ans = \min(ans, Dp[i])$
• $ans = ans + Dp[i]$
• $ans = ans - Dp[i]$

程序2

给定一个字符串 $S$，有 $q$ 组询问，每次给定一个字符串 $T$，求字符串 $T$ 是否是 $S$ 中的一个子序列。数据保证 $1 \leq |S| \leq 105, 1 \leq \sum |T| \leq 106$，所有字符串仅包含小写字母。

#include <iostream>
using namespace std;

const int BASE = 26;

string S, T;
int q, Pos[100005][BASE];

int main()
{
    cin >> S;
    int n = S.size();
    for (int i = 0; i < BASE; i++)
        ①=-1;
    for (int i = n - 1; i >= 0; i--) 
    {
        for (int j = 0; j < BASE; j++)
            ②;
        ③;
    }
    cin >> q;
    while (q--)
    {
        cin >> T;
        int len = T.size(), now = 0;
        for (int i = 0; ④; i++)
            now = ⑤;
        if (now != -1)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

1. ①处应填（ ）。 {{ select(40) }}

• $Pos[i][n-1]$
• $Pos[i][n]$
• $Pos[n-1][i]$
• $Pos[n][i]$

2. ②处应填（ ）。 {{ select(41) }}

• $Pos[i][j] = Pos[i-1][j]$
• $Pos[i][j] = Pos[i+1][j]$
• $Pos[i][j] = Pos[i][j-1]$
• $Pos[i][j] = Pos[i][j+1]$

3. ③处应填（ ）。 {{ select(42) }}

• $Pos[i][S[i] - 'a'] = i$
• $Pos[i][S[i] - 'A'] = i$
• $Pos[i][S[i]] = i$
• $Pos[i][i] = S[i]$

4. ④处应填（ ）。 {{ select(43) }}

• $i < len$
• $now! = -1$
• i < len &&now! = n
• i < len &&now! = -1

5. ⑤处应填（ ）。 {{ select(44) }}

• $Pos[now][T[i] - 'a']$
• $Pos[now][S[i] - 'a']$
• $Pos[now + 1][T[i] - 'a']$
• $Pos[now + 1][S[i] - 'a']$