一、单项选择题

1. 以下哪个是面向过程的程序设计语言？（{{ select(1) }}）

• C
• C++
• Python
• Java

2. 1GB代表的字节数是（{{ select(2) }}）。

• (2^{10})
• (2^{20})
• (2^{30})
• (2^{40})

3. 八进制数356.433转成十六进制数是（{{ select(3) }}）。

• EE.AD8
• EF.EDB
• FC.3E
• FD.ADC

4. 二进制数00101100和00011101的和是（{{ select(4) }}）。

• 00111101
• 01000001
• 01100001
• 01101001

5. （{{ select(5) }}）是一种先进后出的线性表。

• 栈
• 队列
• 哈希表（散列表）
• 二叉树

6. 下列网络协议中，（{{ select(6) }}）不是用于电子邮件的协议。

• IMAP
• SMTP
• POP3
• P2P

7. 3名男生与3名女生站成一排，若要求男女相间，则不同的排法数有（{{ select(7) }}）。

• 36
• 55
• 72
• 108

8. 已知一棵二叉树有100个节点，则其中至多有（{{ select(8) }}）个节点有2个子节点。

• 23
• 35
• 49
• 82

9. （{{ select(9) }}）算法的平均时间复杂度为(O(n \log n))，其中(n)是待排序的元素个数。

• 冒泡排序
• 选择排序
• 快速排序
• 插入排序

10. 原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符串ABBCCC共有（{{ select(10) }}）个不同的非空子串。

• 11
• 14
• 17
• 20

11. 3570和2023的最大公约数是（{{ select(11) }}）。

• 13
• 59
• 119
• 337

12. 折半查找对元素的排列要求及适用的表的存储方式为（{{ select(12) }}）。

• 元素无序，链接方式存储
• 元素有序，链接方式存储
• 元素无序，顺序方式存储
• 元素有序，顺序方式存储

13. 从1到2023这2023个整数中，共有（{{ select(13) }}）个包含数字3的数。

• 367
• 566
• 729
• 933

14. 考虑如下递归算法的伪代码：

solve(n,m)
 if n==1 return 1
 else if m==1 return n
 else return solve(n-1,m)+solve(n,m-1)

则调用solve(5, 6)得到的结果是（{{ select(14) }}）。

• 126
• 210
• 252
• 283

15. 从ENIAC到当前最先进的计算机，冯·诺依曼体系结构始终占有重要地位。冯·诺依曼体系结构的核心内容是（{{ select(15) }}）。

• 采用开关电路
• 采用半导体器件
• 采用存储程序和程序控制原理
• 采用机器学习算法

二、阅读程序

第一小题

#include <iostream>
using namespace std;
int n, a[1000];
void check(int& a, int& b) {
    if (a > b) {
        int t = a;
        a = b;
        b = t;
    }
}
int main() {
    cin >> n;
    a[1] = n/2+1;
    for (int i = 2; i <= n; i++)
        a[i] = (a[i-1] * 5 - 2) % n + 1;
    for (int i = 2; i <= n; i++)
        check(a[1], a[i]);
    for (int i = 3; i <= n; i++)
        check(a[2], a[i]);
    cout << a[1] << endl;
    cout << a[2] << endl;
    return 0;
}

16.当输入为1000时，程序会发生数组越界。（{{ select(16) }}）

• √
• ×

17.对于任意输入的n，a[1]到a[n]是一个1到n的排列。（{{ select(17) }}）

• √
• ×

18.当输入为5时，输出的第一行为3。（{{ select(18) }}）

• √
• ×

19.当输入为10时，输出的第一行为7。（{{ select(19) }}）

• √
• ×

20.当n>1时，输出的第一行的数字和输出的第二行的数字之间的关系（{{ select(20) }}）

• 第一行数字一定大于第二行数字
• 第一行数字一定等于第二行数字
• 第一行数字一定小于第二行数字
• 不确定

21.当输入为20时，输出的第二行数字为（{{ select(21) }}）。

• 2
• 3
• 4
• 5

第二小题

#include <iostream>
using namespace std;
int a[101], n, cnt;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        int j = i;
        while (j > 1 && a[j] < a[j/2]) {
            cnt++;
            int t = a[j];
            a[j] = a[j/2];
            a[j/2] = t;
            j /= 2;
        }
    }
    cout << cnt << endl;
    return 0;
}

假设输入的n是正整数，a[i]都是在[1,n]范围内的整数，完成下面的判断题和单选题：

22.循环结束时，a[1]保存的是输入的n个数中的最小值。（{{ select(22) }}）

• √
• ×

23.循环结束时，a[1]到a[n]按升序排序（即a[1]≤a[2]≤⋯≤a[n]）。（{{ select(23) }}）

• √
• ×

24.当n为10时，无论输入的a[1]到a[10]值为多少，输出的cnt不会大于19。（{{ select(24) }}）

• √
• ×

25.当n为100时，无论输入的a[1]到a[100]值为多少，输出的cnt不会大于450。（{{ select(25) }}）

• √
• ×

26.当输入的n为5，a[1]到a[5]依次为3, 5, 2, 4, 1时，输出的结果为（{{ select(26) }}）。

• 1
• 2
• 3
• 4

27.当输入的n为5，a[1]到a[5]依次为2, 3, 1, 4, 5时，输出的结果为（{{ select(27) }}）。

• 1
• 2
• 3
• 4

第三小题

#include <iostream>
using namespace std;
int f[1001], g[1001], p[1001], m, n;
void init() {
    f[1] = g[1] = 1;
    for (int i = 2; i <= 1000; i++) {
        if (!f[i]) {
            p[++m] = i;
            for (int j = i*i; j <= 1000; j += i)
                f[j] = 1;
        }
        g[i] = g[i-1] + f[i];
    }
}
int main() {
    init();
    cin >> n;
    cout << f[n] << endl;
    cout << g[n] << endl;
    if (n <= 100)
        cout << p[n] << endl;
    return 0;
}

28.第16行执行结束后，f[103]的值为0。（{{ select(28) }}）

• √
• ×

29.第16行执行结束后，g[1000]+m的值为1000。（{{ select(29) }}）

• √
• ×

30.g[1000]+m等于1000。（{{ select(30) }}）

• √
• ×

31.当输入为123时，输出的第一行为（{{ select(31) }}）。

• 0
• 1
• 33
• 123

32.当输入为30时，输出的第二行为（{{ select(32) }}）。

• 10
• 15
• 20
• 25

33.当输入为25时，输出的第三行为（{{ select(33) }}）。

• 93
• 97
• 101
• 103

三、完善程序

第一小题 （汽水问题）徐老师从商店里买了n瓶汽水，他每喝完一瓶汽水就把瓶盖保存起来，k个瓶盖可以换一瓶新的汽水，请计算徐老师最终能喝多少瓶汽水。需要注意的是，本题中徐老师不可以赊账。 试补全该模拟程序。

#include <iostream>
using namespace std;
int main() {
    int n, // n表示当前购买但未喝的汽水瓶数
        k, // k表示可以兑换一瓶汽水的瓶盖数
        s = 0, // s记录徐老师喝了的汽水总瓶数
        t = 0; // t记录徐老师拥有的瓶盖数量
    cin >> n >> k;
    do {
        s += ___ (1) ___ ;
        t += ___ (2) ___ ;
        n = ___ (3) ___ ;
        t %= ___ (4) ___ ;
    } while ( ___ (5) ___ );
    cout << s << endl;
    return 0;
}

34._ (1) _ 处应填（{{ select(34) }}）

• n
• k
• s
• t 35._ (2) _ 处应填（{{ select(35) }}）
• n
• k
• s
• t 36._ (3) _ 处应填（{{ select(36) }}）
• n
• k
• s
• t 37._ (4) _ 处应填（{{ select(37) }}）
• n
• k
• s
• t 38._ (5) _ 处应填（{{ select(38) }}）
• n > 0
• t > 0
• n < k
• t >= k

第二小题

（最优装配问题）有n个盒子需要打包邮寄给同一个买家，每个盒子有一个体积，用$a_i$表示第i个盒子的体积，已知若第i个盒子的体积不超过第j个盒子体积的一半（即$2×a_i≤a_j$），就可将第i个盒子放入第j个盒子内一起打包，但是同一个包裹内最多装两个盒子（即不能将一个装有盒子的盒子再放入另一个盒子中），卖家希望尽可能多地将盒子合并在一起以减少打包的包裹数量。 下面的代码使用二分算法求解并输出最少打包数量，试补全代码。

#include <iostream>
#include <algorithm>
using namespace std;
int n, a[1000];
bool check(int x) {
    for (int i = 1; i <= x; i++)
        if (2 * a[i] > ___ (1) ___ )
            return false;
    return true;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a+1, ___ (2) ___ );
    int l = 0, r = n/2, mid, res;
    while ( ___ (3) ___ ) {
        mid = (l + r) / 2;
        if (check(mid)) {
            res = mid;
            ___ (4) ___ ;
        } else {
            ___ (5) ___ ;
        }
    }
    cout << n - res << endl;
    return 0;
}

39._ (1) _ 处应填（{{ select(39) }}）

• a[n - i]
• a[n + 1 - i]
• a[n - x + i]
• a[n - x + i + 1]

40._ (2) _ 处应填（{{ select(40) }}）

• a + n
• a + n + 1
• a - n
• a + n - 1

41._ (3) _ 处应填（{{ select(41) }}）

• l != r
• l < r
• l <= r
• r - l != 1

42._ (4) _ 处应填（{{ select(42) }}）

• l = mid - 1
• l = mid + 1
• r = mid - 1
• r = mid + 1

43._ (5) _ 处应填（{{ select(43) }}）

• l = mid - 1
• l = mid + 1
• r = mid - 1
• r = mid + 1