该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

一、单项选择题(每题 2 分,共 30 分)

1. GNU GCC 是常用的 C/C++ 编译器。现需要用 g++把 admin1.cpp 编译为可执行文件 admin1,可以用( )。

{{ select(1) }}

• g++ -S admin1 admin1.cpp
• g++ -S admin1.cpp admin1
• g++ -o admin1 admin1.cpp
• g++ -o admin1.cpp admin1

2. 关于编译语言与解释语言,说法错误的是( )。

{{ select(2) }}

• C++ 是编译语言,需先编译得到可执行程序再执行
• 编译语言程序每一次执行都需要重新编译
• 解释器负责把解释语言的源程序翻译为可执行的机器代码
• Python 是常见的解释语言

3. 输入 $x$ 是 $1$ 到 $10$ 的正整数,下面代码输出不可能是( )。

switch(x) {
    case 1: { cout << "A"; break; }
    case 3: { cout << "C"; }
    default: { cout << "Q"; }
    case 5: { cout << "E"; }
}

{{ select(3) }}

• A
• CQE
• QE
• Q

4. $k(k>4)$ 进制数 $4321$ 与十进制数( )相等。

{{ select(4) }}

• $4321$
• $4k^4+3k^3+2k^2+k$
• $4k^3+3k^2+2k+1$
• $10k$

5. 下面代码执行完后, ans 的值是( )。

int N = 10, ans = 0, x = 0;
for(int i = 1; i <= N; i++)
    for(int j = i + 1; j <= N; j++)
        ans += ++x;

{{ select(5) }}

• $45$
• $55$
• $990$
• $1035$

6. 空栈支持入栈和出栈。把 $1$ 到 $10$ 依次入栈,第一个出栈的是 $8$ ,则第二个出栈的数不可能是( )。

{{ select(6) }}

• $1$
• $7$
• $9$
• $10$

7. 有序表有 $100$ 个元素,二分查找元素 X。恰好比较 $5$ 次能找到的元素有( )个。

{{ select(7) }}

• $100$
• $32$
• $31$
• $16$

8. 下面是图 G 的邻接矩阵,度数最大的点的度是( )。

   A B C D E

A $0$ $1$ $1$ $0$ $1$

B $1$ $0$ $1$ $0$ $0$

C $1$ $1$ $0$ $1$ $1$

D $0$ $0$ $1$ $0$ $1$

E $1$ $0$ $1$ $1$ $0$

{{ select(8) }}

• $1$
• $2$
• $3$
• $4$

9. $8$ 支队伍均分为第一组与第二组进行小组赛。A 队和 B 队在同一组,C 队与它们不在同一组,分组方案有( )种。

{{ select(9) }}

• $10$
• $20$
• $30$
• $40$

10. 把一根长度为 $3$ 的木棍随机折成三段,断点在中点两侧等概率分布,三段能构成三角形的概率是( )。

{{ select(10) }}

• $1$
• $0.5$
• $0.25$
• $0.125$

11. 关于快速排序,不正确的是( )。

{{ select(11) }}

• 典型应用分治法
• 最坏时间复杂度为 $O(n \log n)$
• 基于交换的排序
• sort 是 STL 提供的排序,结合了堆排序、插入排序等技术

12. 关于 $8$ 位二进制编码,错误的是( )。

{{ select(12) }}

• $-17$ 的原码为 $10010001$
• $22$ 的补码为 $00010110$
• $-13$ 的反码为 $11110010$
• 以上说法存在错误

13. 表达式 $(x-2)(x-\dfrac{1}{2})^4$ 中,$x$ （一次式）的系数为( )。

{{ select(13) }}

• $24$
• $\dfrac{1}{16}$
• $\dfrac{17}{16}$
• $-\dfrac{1}{8}$

14. 二叉树 T 中序为 CGEADBF,后序为 GECDFBA,其前序为( )。

{{ select(14) }}

• ACEGBDF
• ACGEBDF
• ABDFCEG
• ABCDEFG

15. $2024$ 年,来自 Google DeepMind 的 Demis Hassabis 和 John Jumper 获得了( ),表彰他们在人工智能方面的贡献。

{{ select(15) }}

• 王选奖
• 图灵奖
• 诺贝尔奖
• 贝尔奖

二、阅读程序

判断题每题 1.5 分，选择题每题 3 分，第 29 题 3 分，第 32 题 4 分，共 40 分。

程序 ($1$)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int l, r;
    cin >> l >> r;
    int cnt = 0;
    long long sum = 0;
    for(int i = l; i <= r; ++i) {
        if((i & (i - 1)) != 0) {
            cnt += 1;
            sum += i;
        }
    }
    cout << cnt << " " << sum << endl;
    return 0;
}

(1) 输入 $2$ $5$ ,输出是 $2$ $8$ 。

{{ select(16) }}

• 正确
• 错误

(2) 程序输出总是两个正整数。

{{ select(17) }}

• 正确
• 错误

(3) 把第 $8$ 行 long long 改成 int,程序行为不变。

{{ select(18) }}

• 正确
• 错误

(4) 输入 $1$ $100$ ,输出是( )。

{{ select(19) }}

• $93$ $4923$
• $92$ $4823$
• $93$ $4823$
• $92$ $4923$

(5) 输入 $10000$ $1000000$ ,第一个输出是( )。

{{ select(20) }}

• $989993$
• $989994$
• $989995$
• $989996$

程序 ($2$)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> dp(m + 1);
    dp[0] = 0;
    for(int i = 1; i <= m; ++i) {
        int now = 0;
        for(int j = 0; j < n; ++j) {
            if(i >= a[j] && dp[i - a[j]] == 0) {
                now = a[j];
            }
        }
        dp[i] = now;
    }
    cout << dp[m] << endl;
    return 0;
}

(1) 输入 $3$ $5$ $1$ $3$ $4$ ,输出是 $0$ 。

{{ select(21) }}

• 正确
• 错误

(2) 数组 $a$ 为 {$1$} 且 $m$ 为偶数时,输出是 $0$ 。

{{ select(22) }}

• 正确
• 错误

(3) 把第 $16$ 行 i >= a[j] && dp[i-a[j]] == 0 改成 dp[i-a[j]] == 0 ,可能产生编译错误。

{{ select(23) }}

• 正确
• 错误

(4) 输入 $4$ $13$ $1$ $2$ $3$ $4$ ,输出是( )。

{{ select(24) }}

• $0$
• $1$
• $2$
• $3$

(5) 输入 $7$ $1000$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ ,输出是( )。

{{ select(25) }}

• $0$
• $1$
• $2$
• $3$

(6) $a$ 为 {$1,2,3,4,5$} 时,有多少个符合范围的 $m$ 使输出为 $3$?( )

{{ select(26) }}

• $165$
• $166$
• $167$
• $168$

程序 ($3$)

#include<bits/stdc++.h>
using namespace std;

vector <int> primes;
int comp_by[2000005];
void sieve(int n) {
    for(int x = 2; x <= n; x++) {
        if(comp_by[x] == 0)
            primes.push_back(x);
        for(int i = 0; i < primes.size(); i++) {
            if(x * primes[i] > n) break;
            comp_by[x * primes[i]] = primes[i];
            if(x % primes[i] == 0) break;
        }
    }
}
int main() {
    freopen("input.txt", "w", stdout);
    freopen("output.txt", "r", stdin);
    int n;
    cin >> n;
    sieve(n);
    for(int i = 1; i <= n; i++)
        cout << comp_by[i] << ' ';
    return 0;
}

(1) 程序从 input.txt 读入、输出到 output.txt。

{{ select(27) }}

• 正确
• 错误

(2) 交换第 $11$、$12$ 行,不会数组越界。

{{ select(28) }}

• 正确
• 错误

(3) 对所有 $1≤i≤n$ ,第 $i$ 个输出为 $0$ 当且仅当 $i$ 是质数。

{{ select(29) }}

• 正确
• 错误

(4) 该程序最接近哪种算法?( )

{{ select(30) }}

• 递归法
• 动态规划
• 埃氏筛
• 欧拉筛

(5) 把第 $13$ 行移到第 $11$ 行前,输入 $1000000$ 时,第几个输出会变?( )

{{ select(31) }}

• $75$
• $45$
• $97$
• $105$

(6) 输入 $100$ ,所有输出数字之和为( )。

{{ select(32) }}

• $154$
• $194$
• $197$
• $214$

三、完善程序

单项选择题,每题 $3$ 分,共 $30$ 分。

($33$ 至 $42$) 把空缺处的正确代码填进去,使程序完成既定功能。

($1$)全排列检查 原题:给定长度为 $n$ 的数组 $a$ ,判断其是否构成全排列。如果 $1,2$ , ..., $n$ 都恰好在数组 $a$ 中出现且仅出现一次,那么就称这个数组是一个全排列。试补全程序。

#include<bits/stdc++.h>
using namespace std;

bool is_permutation(vector<int> &a) {
    int n =  ① ;
    vector<int> count( ② );
    for(int i = 0; i < n; i++) {
        if( ③ )
            count[a[i]]++;
        else
            ④ ;
    }
    for(int i = 1; i <= n; i++)
        if(count[ ⑤ ] > 1)
            return false;
    return true;
}
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    if(is_permutation(a))
        cout << "The sequence is a permutation.";
    else
        cout << "The sequence is not a permutation.";
    return 0;
}

(1) ① 处应填( )。

{{ select(33) }}

• length()
• size()
• back()
• capacity()

(2) ② 处应填( )。

{{ select(34) }}

• 0
• n
• n+1
• 1000000000

(3) ③ 处应填( )。

{{ select(35) }}

• 1<=a[i]&&a[i]<=n
• 1<=a[i]<=n
• 1<=a[i]||a[i]<=n
• a[i]<1||a[i]>n

(4) ④ 处应填( )。

{{ select(36) }}

• break
• continue
• return true
• return false

(5) ⑤ 处应填( )。

{{ select(37) }}

• i
• a[i]
• i-1
• i / 2

($2$)跳跃 (倍增/二进制提升) 原题:给定一个数组 a[0] , a[1] , ..., a[n-1] ,每次跳跃从当前位置 $x$ 跳至位置 a[x] 。回答 $q$ 次询问,每次给出 (x, $k$),输出从 $x$ 跳跃 $k$ 次后的位置编号。试补全程序。

#include <iostream>
using namespace std;

const int N = 100010, LOG = 20;
int a[N], dp[N][LOG];

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) {
        dp[i][0] =  ① ;
    }
    for (int k = 1; k < LOG; k++) {
        for (int i = 0; i < n; i++) {
            dp[i][k] =  ② ;
        }
    }

    while (q--) {
        int x, k;
        cin >> x >> k;
        int u = x;
        for (int j = 0; j < LOG; j++) {
            if ( ③ ) {
                u =  ④ ;
            }
        }
        cout <<  ⑤  << endl;
    }
    return 0;
}

(1) ① 处应填( )。

{{ select(38) }}

• i
• a[i]
• 0
• dp[i][1]

(2) ② 处应填( )。

{{ select(39) }}

• dp[dp[i][k-1]][k-1]
• dp[i][k-1]+dp[i][k-1]
• dp[i-1][k-1]
• dp[k-1][i]

(3) ③ 处应填( )。

{{ select(40) }}

• k&j
• k>>j
• (k>>j)&1
• (k>>j)^1

(4) ④ 处应填( )。

{{ select(41) }}

• dp[j][u]
• dp[k][u]
• dp[u][j]
• a[u]

(5) ⑤ 处应填( )。

{{ select(42) }}

• u
• x
• k
• dp[u][0]