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

每题有且仅有一个正确选项。

1. 分辨率为 $800\times600$、$16$ 位色的位图，存储图像信息所需的空间为（ ）。

{{ select(1) }}

• $937.5\mathrm{KB}$
• $4218.75\mathrm{KB}$
• $4320\mathrm{KB}$
• $2880\mathrm{KB}$

2. 十进制小数 $13.375$ 对应的二进制数是（ ）。

{{ select(2) }}

• 1101.011
• 1011.011
• 1101.101
• 1010.001

3. 判断 a 不等于 $0$ 且 b 不等于 $0$ 的正确的条件表达式是（ ）。

{{ select(3) }}

• !a == 0 || !b == 0
• a && b
• !((a == 0) && (b == 0))
• !(a == 0 && b == 0)

4. 欧拉图 $G$ 是指可以构成一个闭回路的图，且图 $G$ 的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中，不一定是欧拉图的是（ ）。

{{ select(4) }}

• 图 $G$ 中没有度为奇数的顶点
• 包含欧拉环游的图（欧拉环游是指通过图中每边恰好一次的闭路径）
• 包含欧拉闭迹的图（欧拉迹是指通过图中每边恰好一次的路径）
• 存在一条回路，通过每个顶点恰好一次

5. 下列关于二叉树性质的说法正确的有（ ）。

{{ select(5) }}

• 非空满二叉树的结点个数一定为奇数个。
• 非完全二叉树也可以用像完全二叉树那样使用顺序存储结构进行存储
• 当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。
• 完全二叉树最多只有最下面的一层结点度数可以小于 $2$

6. 对于入栈顺序为 $a,b,c,d,e,f,g$ 的序列，下列（ ）不可能是合法的出栈序列。

{{ select(6) }}

• $a,b,c,d,e,f,g$
• $a,d,c,b,e,g,f$
• $a,d,b,c,g,f,e$
• $g,f,e,d,c,b,a$

7. 根节点深度为 $0$，一棵深度为 $h$ 的满 $k(k>1)$ 叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 $k$ 个子结点的树，共有（ ）个结点。

{{ select(7) }}

• $\dfrac{k^{h+1}-1}{k-1}$
• $\dfrac{k^{h+1}}{k-1}$
• $k^h-1$
• $k^h$

8. 由四个不同的点构成的简单无向连通图的个数是（ ）。

{{ select(8) }}

• $32$
• $35$
• $38$
• $41$

9. 下列关于无向连通图特性的叙述中，正确的是（ ）。

Ⅰ. 所有顶点的度之和为偶数

Ⅱ. 边数大于顶点个数

Ⅲ. 至少有一个顶点的度为 $1$

{{ select(9) }}

• 只有Ⅰ
• 只有Ⅱ
• Ⅰ和Ⅱ
• Ⅰ和Ⅲ

10. 散列（Hash）文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的（ ）法是散列文件的关键。

{{ select(10) }}

• 散列函数
• 除余法中质数
• 冲突处理
• 散列函数和冲突处理

11. 表达式 $a*d-b*c$ 的前缀表达形式为（ ）。

{{ select(11) }}

• ad * bc * -
• - * ad * bc
• a * d - b * c -
• - * *adbc

12. 方程 $a\times b=(a\ \mathrm{or}\ b)\times(a\ \mathrm{and}\ b)$，在 a,b 都取 $[0,31]$ 中的整数时，共有（ ）组解。（$\times$ 表示乘法；or 表示按位或运算；and 表示按位与运算）

{{ select(12) }}

• $32$
• $256$
• $454$
• $512$

13. 从一个 $4\times4$ 的棋盘（不可旋转）中选取不在同一行也不在同一列上的两个方格，共有（ ）种方法。

{{ select(13) }}

• $16$
• $72$
• $256$
• $512$

14. 某中学在安排期末考试时发现，有 $7$ 个学生要参加 $7$ 门课程的考试，下表列出了哪些学生参加哪些考试（用 √ 表示要参加相应的考试）。最少要安排（ ）个不同的考试时间段才能避免冲突。

考试	学生 $1$	学生 $2$	学生 $3$	学生 $4$	学生 $5$	学生 $6$	学生 $7$
通用技术	√				√		√
物理		√
化学				√
生物	√				√	√
历史			√	√
地理		√					√
政治						√

{{ select(14) }}

• $3$
• $5$
• $6$
• $7$

15. 某计算机的 CPU 和内存之间的地址总线宽度是 $32$ 位，这台计算机最多可以使用（ ）的内存。

{{ select(15) }}

• $2\mathrm{GB}$
• $4\mathrm{GB}$
• $8\mathrm{GB}$
• $16\mathrm{GB}$

二、阅读程序（判断题1分，选择题3分，共计40分）

判断题正确填 T，错误填 F。

第1题

void solve1(int n)
{
    if (n == 0) return;
    int lowbit = n & 1;
    solve1((n - lowbit) / -2);
    std::cout << lowbit;
}

void solve2(int n)
{
    int a[100];
    int size = 0;
    while (n != 0)
    {
        int lowbit = n % 2;
        if (lowbit == -1) lowbit = 1;

        a[size++] = lowbit;
        n = (n - lowbit) / -2;
    }

    if (size == 0) {
        std::cout << 0;
    }
    else {
        while (size > 0)
        {
            int highbit = a[--size];
            std::cout << highbit;
        }
    }
}

保证 solve1 与 solve2 的参数 n 是整数。

判断题

16. solve1(111) 的返回值为 110110011（ ）。

{{ select(16) }}

• 正确
• 错误

17. solve2(111) 的返回值为 110011011（ ）。

{{ select(17) }}

• 正确
• 错误

选择题

18. 当输入 $n=0$ 时，solve1 和 solve2 分别输出（ ）。

{{ select(18) }}

• 0，0
• 运行错误，运行错误
• 无输出，0
• 0，无输出

19. 两段程序中计算 lowbit 的方法（ ）。

{{ select(19) }}

• 完全等价
• 仅在 n 为正整数时成立
• 仅在 n 为非负整数时成立
• 仅在 n 为负整数时成立

20. solve1(n) 与 solve2(n) 的时间复杂度为（ ）。

{{ select(20) }}

• $\Theta(\log n)$，$\Theta(\log n)$
• $\Theta(\log n)$，$\Theta(n)$
• $\Theta(n)$，$\Theta(\log n)$
• $\Theta(n^2)$，$\Theta(n)$

第2题

int solve(int n, int a[])
{
    std::sort(a, a + n);
    int half = n / 2;
    int j = half;
    int pair = 0;
    for (int i = 0; i < half; ++i)
    {
        while (j < n && a[i] * 2 > a[j])
        {
            j++;
        }
        if (j < n)
        {
            pair++;
            j++;
        }
    }
    return pair;
}

判断题

21. 若参数 n = 3，a = [1 2 3]，程序返回 1（ ）。

{{ select(21) }}

• 正确
• 错误

22. 返回值 pair 不超过 half（ ）。

{{ select(22) }}

• 正确
• 错误

23. 当 n 是奇数时，i 的值会超过 j（ ）。

{{ select(23) }}

• 正确
• 错误

24. 若参数 n = 10，a 也只含 10，程序返回 5（ ）。

{{ select(24) }}

• 正确
• 错误

选择题

25. 若参数 n = 6，a = [2 3 4 4 7 10]，程序返回（ ）。

{{ select(25) }}

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

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

{{ select(26) }}

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

27. 代码使用了（ ）算法策略。

{{ select(27) }}

• 贪心
• 动态规划
• 分治
• 回溯

第三题

struct hash_map
{
    const int max_size = 32767;
    struct node
    {
        int key;
        int value;
        int next;
    }
    map[max_size * 4];

    int size = 0;

    int hash[max_size] = {0};

    int& operator[] (int key)
    {
        int code = key % max_size;

        int addr = hash[code];
        while (addr > 0)
        {
            if (map[addr].key == key)
                return map[addr].value;
            else
                addr = map[addr].next;
        }

        ++size;
        map[size].key = key;
        map[size].value = 0;
        map[size].next = hash[code];
        hash[code] = size;

        return map[size].value;
    }
};

void test(int q)
{
    hash_map map;
    while (q > 0)
    {
        --q;

        char op;
        std::cin >> op;
        if (op == '+')
        {
            int key, value;
            std::cin >> key >> value;
            map[key] = value;
        }
        if (op == '?')
        {
            int key;
            std::cin >> key;
            std::cout << map[key] << "\n";
        }
    }
}

判断题

28. hash_map 的最大容量可以超过 max_size（ ）。

{{ select(28) }}

• 正确
• 错误

29. 当查询 ? 到一个不存在于 map 的 key 时，将会返回 0（ ）。

{{ select(29) }}

• 正确
• 错误

30. 当重复执行 + 1 2 四遍的时候，hash_map 的 size 将会增加 4（ ）。

{{ select(30) }}

• 正确
• 错误

31. hash_map 不能存储 key 恰等于 0 的键值对（ ）。

{{ select(31) }}

• 正确
• 错误

选择题

32. 该代码解决哈希冲突的方式为（ ）。

{{ select(32) }}

• 链地址法
• 线性探测法
• 再哈希法
• 忽略冲突

33. 执行 q 次插入 + 的平均时间复杂度为（ ）。

{{ select(33) }}

• $\Theta(q)$
• $\Theta(q^2)$
• $\Theta(q\log q)$
• $\Theta(q\sqrt q)$

34. 执行单次查询 ? 的平均时间复杂度为（ ）。

{{ select(34) }}

• $\Theta(\mathrm{size})$
• $\Theta(\log \mathrm{size})$
• $\Theta(1)$
• $\Theta(\mathrm{max\_size})$

35. 以下说法正确的是（ ）。

{{ select(35) }}

• 当 value 改为 std::string 类型时，需要对程序进行较大的改动
• 当 key 改为 std::string 类型时，需要对程序进行较大的改动
• hash_map 无法提供删除功能
• hash_map 处理的 key 数值大小不能超过 max_size

三、完善程序（单选题，每小题3分，共计30分）

第1题

solve(int n, int a[]) 解决的问题是：给定 $n$ 个整数 $a_1,a_2,\ldots,a_n$，每个数字都是 $0,1,2$ 中的一个。不断交换这个序列中的任意两个数字，让这个序列成为升序，函数返回最少需要的交换次数。

int cal(int q[3][3], int u, int v)
{
    int pair = std::min(____(1)____);
    q[u][v] -= pair;
    q[v][u] -= pair;
    return pair;
}

int solve(int n, int a[])
{
    int c[3] = {0, 0, 0};
    for (int i = 0; i < n; ++i)
    {
        ____(2)____;
    }

    int q[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
    for (int i = 0; i < n; ++i)
    {
        int from = ____(3)____;

        int to;
        if (i < c[0])
            to = 0;
        else if (i < ____(4)____)
            to = 1;
        else
            to = 2;

        q[from][to]++;
    }

    int sum = 0;
    sum += cal(q, 0, 1);
    sum += cal(q, 0, 2);
    sum += cal(q, 1, 2);
    sum += 2 * (____(5)____);
    std::cout << sum << "\n";
}

36. (1) 处应填（ ）。

{{ select(36) }}

• a[u],a[v]
• c[u],c[v]
• q[0][v], q[0][u]
• q[u][v], q[v][u]

37. (2) 处应填（ ）。

{{ select(37) }}

• c[i]++
• c[a[i]]++
• c[i] += a[i]
• c[a[i]] = +1

38. (3) 处应填（ ）。

{{ select(38) }}

• a[c[i]]
• a[i]
• c[i]
• c[a[i]]

39. (4) 处应填（ ）。

{{ select(39) }}

• c[1]
• c[2]
• c[1] + c[2]
• c[0] + c[1]

40. (5) 处应填（ ）。

{{ select(40) }}

• q[0][1] + q[0][2]
• q[1][0] + q[0][2]
• q[1][2] + q[2][0]
• q[1][0] + q[2][1]

第2题

有三种操作可以修改一个变量的值：

• 增加：将变量加一；
• 减少：将变量减一；
• 翻倍：将变量翻倍。

函数 solve(x, y) 用于求解最少需要几步操作，才能将变量的值从 $x$ 变成 $y$。

std::map<int, int> mem;
int solve(int x, int y)
{
    int base = std::max(x - y, y - x);

    if (____(1)____)
        return ____(2)____;

    if (____(3)____)
        return mem[y];

    int reduce;
    if (____(4)____)
    {
        reduce = ____(5)____;
    }
    else
    {
        reduce = std::____(6)____;
    }

    mem[y] = std::____(7)____;
    return mem[y];
}

41. (1)(2) 处应填（ ）。

{{ select(41) }}

• y <= x，0
• x <= y，1
• y <= x，base
• x <= y，base

42. (3) 处应填（ ）。

{{ select(42) }}

• mem[y]
• mem.count(y)
• mem[x]
• mem.count(x)

43. (4)(5) 处应填（ ）。

{{ select(43) }}

• x % 2 == 0，solve(x, y/2) + 1
• x % 2 == 1，solve(x*2, y)
• y % 2 == 1，solve(x*2, y)
• y % 2 == 0，solve(x, y/2) + 1

44. (6) 处应填（ ）。

{{ select(44) }}

• min(solve(x, (x-1)/2), solve(x, (y+1)/2))
• min(solve(x, (y+1)/2), solve(x, (y-1)/2)) + 2
• min(solve(x, (y+1)/2), solve(x, (y-1)/2)) * 2
• min(solve(x, (x-1)/2), solve(x, (y+1)/2)) + 2

45. (7) 处应填（ ）。

{{ select(45) }}

• min(mem[y], reduce)
• min(mem[y], base)
• min(base, reduce)
• reduce