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

## 二、阅读程序（判断题1分，选择题3分，共计40分） 判断题正确填 `T`，错误填 `F`。 ### 第1题 ```cpp 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` 是整数。 判断题

选择题

### 第2题 ```cpp 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; } ``` 判断题

选择题

### 第三题 ```cpp 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"; } } } ``` 判断题

选择题

## 三、完善程序（单选题，每小题3分，共计30分） ### 第1题 `solve(int n, int a[])` 解决的问题是：给定 $n$ 个整数 $a_1,a_2,\ldots,a_n$，每个数字都是 $0,1,2$ 中的一个。不断交换这个序列中的任意两个数字，让这个序列成为升序，函数返回最少需要的交换次数。 ```cpp 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"; } ```

### 第2题 有三种操作可以修改一个变量的值： - 增加：将变量加一； - 减少：将变量减一； - 翻倍：将变量翻倍。 函数 `solve(x, y)` 用于求解最少需要几步操作，才能将变量的值从 $x$ 变成 $y$。 ```cpp 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]; } ```