一、单选题（每题 2 分，共 30 分）

第 1 题 对如下定义的循环单链表，横线处填写( )。

01 // 循环单链表的结点
02 struct Node {
03     int data;    // 数据域     
04     Node* next;  // 指针域    
05    
06    Node(int d) : data(d), next(nullptr) {}
07 };
08 
09 // 创建一个只有一个结点的循环单链表
10 Node* createList(int value) {
11     Node* head = new Node(value);
12     head->next = head;
13     return head;
14 }
15 
16 // 在循环单链表尾部插入新结点
17 void insertTail(Node* head, int value) {
18     Node* p = head;
19     while (p->next != head) {
20         p = p->next;
21     }
22     Node* node = new Node(value);
23     node->next = head;
24     p->next = node;
25 }
26 
27 // 遍历并输出循环单链表
28 void printList(Node* head) {
29     if (head == nullptr) return;
30 
31     Node* p = head;
32     _____________________ // 在此处填入代码     
33     cout << endl;
34 }

{{ select(1) }}

• 01 while (p != nullptr){
  02 cout << p->data << " ";
  03 p = p->next;
  04 }
  

• 01 while (p->next != nullptr){
  02     cout << p->data << " ";
  03     p = p->next;
  04 }
  

• 01 do {
  02     cout << p->data << " ";
  03     p = p->next;
  04 } while (p != head);
  

• 01 for(; p; p=p->next){
  02     cout << p->data << " ";
  03 }
  

第 2 题 区块链技术是比特币的基础。在区块链中，每个区块指向前一个区块，构成链式列表，新区块只能接在链尾，不允许在中间插入或删除。下面代码实现插入区块添加函数，则横线处填写( )。

01 //区块（节点）
02 struct Block {
03     int index; // 区块编号（高度）
04     string data;  // 区块里保存的数据 
05     Block* prev;  // 指向前一个区块   
06 
07     Block(int idx, const string& d, Block* p) : index(idx), data(d), prev(p) {}
08 };
09 
10 // 区块链
11 struct Blockchain {
12     Block* tail;
13
14     // 初始化
15     void init() {
16         tail = new Block(0, "Genesis Block", nullptr);
17     }
18 
19     // 插入新区块
20     void addBlock(const string& data) {
21         __________________ //在此处填入代码    
22     }
23 
24     // 释放内存
25     void clear() {
26         Block* cur = tail;
27         while (cur != nullptr) {
28             Block* p = cur->prev;
29             delete cur;
30             cur = p;
31         } 
32     tail = nullptr;
33     }
34 };

{{ select(2) }}

• 01 Block* newBlock = new Block(tail->index + 1, data, tail);
  02 tail = newBlock->prev;
  

• 01 Block* newBlock = new Block(tail->index + 1, data, tail);
  02 tail = newBlock;
  

• 01 Block* newBlock = new Block(tail->index + 1, data, tail->prev);
  02 tail = newBlock;
  

• 01 Block* newBlock = new Block(tail->index + 1, data, tail->prev);
  02 tail = newBlock->prev;
  

第 3 题 下面关于单链表和双链表的描述中，正确的是( )

01 struct DNode {
02     int data;
03     DNode* prev;
04     DNode* next;
05 };
06 
07 // 在双链表中删除指定节点
08 void deleteNode(DNode* node) {
09     if (node->prev) {
10         node->prev->next = node->next;
11     }
12     if (node->next) {
13         node->next->prev = node->prev;
14     }
15     delete node;
16 }
17 
18 struct SNode {
19     int data;
20     SNode* next;
21 };
22 
23 // 在单链表中删除指定节点
24 void deleteSNode(SNode* head, SNode* node) {
25     SNode* prev = head;
26     while (prev->next != node) {
27         prev = prev->next;
28     }
29     prev->next = node->next;
30     delete node;
31 }

{{ select(3) }}

• 双链表删除指定节点是 O(1)，单链表是O(1)
• 双链表删除指定节点是 O(n)，单链表是O(1)
• 双链表删除指定节点是 O(1)，单链表是O(n)
• 双链表删除指定节点是 O(n)，单链表是O(n)

第 4 题 假设我们有两个数 $a=38$ 和$b=14$，它们对模 $m$ 同余，即 a=b(modm)。以下哪个值不可能是 $m$?

{{ select(4) }}

• $3$
• $4$
• $6$
• $9$

第 5 题 下面代码实现了欧几里得算法。下面有关说法，错误的是( )

01 int gcd1(int a, int b) {
02     return b == 0 ? a : gcd1(b, a % b);
03 }
04 
05 int gcd2(int a, int b) {
06     while (b != 0) {
07         int temp = b;
08         b = a % b;
09         a = temp;
10     }
11     return a;
12 }

{{ select(5) }}

• gcd1() 实现为递归方式。
• gcd2() 实现为迭代方式。
• 当 $a$ 较大时，gcd1() 实现会多次调用自身，需要较多额外的辅助空间。
• 当 $a$ 较大时，gcd1() 的实现比 gcd2() 执行效率更高。

第 6 题 唯一分解定理描述的内容是( )。

{{ select(6) }}

• 任何正整数都可以表示为两个素数的和。
• 任何大于 $1$ 的合数都可以唯一分解为有限个质数的乘积。
• 两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。
• 所有素数都是奇数。

第 7 题 下述代码实现素数表的线性筛法，筛选出所有小于等于 $n$ 的素数，则横线上应填的代码是( )。

01 vector<int> linear_sieve(int n) {
02     vector<bool> is_prime(n +1, true);
03     vector<int> primes;
04 
05     is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
06     for (int i = 2; i <= n; ++i) {
07         if (is_prime[i]) {
08             primes.push_back(i);
09         }
10         _______________ {    // 在此处填入代码
11             is_prime[ i * primes[j] ] = 0;
12             if (i % primes[j] == 0)
13                 break;
14         }
15     }
16
17     return primes;
18 }

{{ select(7) }}

• for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
• for(int j = sqrt(n); j <= n && i * primes[j] <= n; j++)
• for (int j = 1; j <= sqrt(n); j++)
• for(int j = 1; j < n && i * primes[j] <= n; j++)

第 8 题 下列关于排序的说法，正确的是( )。

{{ select(8) }}

• 快速排序是稳定排序
• 归并排序通常是稳定的
• 插入排序是不稳定排序
• 冒泡排序不是原地排序

第 9 题 下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是( )。

01 void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
02     int i = l, j = mid + 1, k = l;
03     while (i <= mid && j <= r) {
04         if (arr[i] <= arr[j]) temp[k++] = arr[i++];
05         else temp[k++] = arr[j++];
06     }
07     while (i <= mid) temp[k++] = arr[i++];
08     while (j <= r)   temp[k++] = arr[j++];
09     for (int p = l; p <= r; p++) arr[p] = temp[p];
10 }
11 
12 void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) {
13     if (l >= r) return;
14     int mid = l + (r - l) / 2;
15     mergeSort(arr, temp, l, mid);
16     mergeSort(arr, temp, mid + 1, r);
17     merge(arr, temp, l, mid, r);
18 }

{{ select(9) }}

• 归并排序的平均复杂度是 $O(nlogn)$。
• 归并排序需要 $O(n)$ 的额外空间。
• 归并排序在最坏情况的时间复杂度是 $O(n^2)$。
• 归并排序适合大规模数据。

第 10 题 下述 C++ 代码实现了快速排序算法，最坏情况的时间复杂度是( )

01 int partition(vector<int>& arr, int low, int high) {
02     int i = low, j = high;
03     int pivot = arr[low];  // 以首元素为基准          
04     while (i < j) {
05         while (i < j && arr[j] >= pivot) j--;
06         while (i < j && arr[i] <= pivot) i++;
07         if (i < j) swap(arr[i], arr[j]);
08     }
09     swap(arr[i], arr[low]);
10     return i;
11 }
12
13 void quickSort(vector<int>& arr, int low, int high) {
14     if (low >= high) return;
15     int p = partition(arr, low, high);
16     quickSort(arr, low, p - 1);
17     quickSort(arr, p + 1, high);
18 }

{{ select(10) }}

• $O(n)$
• $O(logn)$
• $O(n^2)$
• $O(nlogn)$

第 11 题 下面代码尝试在有序数组中查找第一个大于等于 x 的元素位置。如果没有大于等于 x 的元素，返回 $arr.size()$。以下说法正确的是( )。

01 int lower_bound(vector<int>& arr, int x) {
02     int l = 0, r = arr.size();
03     while(l < r) {
04         int mid = l + (r - l) / 2;
05         if(arr[mid] >= x) r = mid;
06         else l = mid + 1;
07     }
08     return l;
09 }

{{ select(11) }}

• 上述代码逻辑正确
• 上述代码逻辑错误，whie 循环条件应该用1<=r
• 上述代码逻辑错误，mid 计算错误
• 上述代码逻辑错误，边界条件不对

第 12 题 小杨要把一根长度为 $L$ 的木头切成 $K$ 段，使得每段长度小于等于 $x$。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小 $x$($x$为正整数)，则横线处应填写( )。

01 // 判断：在不超过 K 次切割内，是否能让每段长度 <= x
02 bool check(int L, int K, int x) {
03     int cuts = (L - 1) / x;
04     return cuts <= K;
05 }
06 
07 // 二分查找最小可行的 x
08 int binary_cut(int L, int K) {
09     int l = 1, r = L;
10     while (l < r) {
11         int mid = l + (r - l) / 2;
12         ________________  // 在此处填入代码 
13     }
14     return l;
15 }
16
17 int main() {
18     int L = 10;  // 木头长度
19     int K = 2;   // 最多切 K 刀
20
21     cout << binary_cut(L, K) << endl;
22     return 0;
23 }

{{ select(12) }}

• 01 if (check(L, K, mid))
  02     r = mid;
  03 else
  04     l = mid + 1;
  

• 01 if (check(L, K, mid))
  02     r = mid+1;
  03 else
  04     l = mid + 1;
  

• 01 if (check(L, K, mid))
  02     r = mid + 1;
  03 else
  04     l = mid - 1;
  

• 01 if (check(L, K, mid))
  02     r = mid + 1;
  03 else
  04     l = mid;
  

第 13 题 下面给出了阶乘计算的两种方式。以下说法正确的是( )

01 int factorial1(int n) {
02     if (n <= 1) return 1;
03     return n * factorial1(n - 1); 
04 }
05 
06 int factorial2(int n) {
07     int acc = 1;   
08     while (n > 1) {
09         acc = n * acc;
10         n = n - 1;
11     }
12     return acc;
13 }

{{ select(13) }}

• 上面两种实现方式的时间复杂度相同，都为$O(n)$
• 上面两种实现方式的空间复杂度相同，都为$O(n)$
• 上面两种实现方式的空间复杂度相同，都为$O(1)$
• 函数 factorial1() 的时间复杂度为$O(2^n)$，函数 factorial2() 的时间复杂度为 $O(n)$

第 14 题 给定有 $n$ 个任务，每个任务有截止时间和利润，每个任务耗时 $1$ 个时间单位、必须在截止时间前完成，且每个时间槽最多做$1$ 个任务。为了在规定时间内获得最大利润，可以采用贪心策略，即按利润从高到低排序，尽量安排，则横线处应填写( )。

01 struct Task {
02     int deadline;   //截止时间
03     int profit;     //利润
04 };
05 
06 void sortByProfit(vector<Task>& tasks) {
07     sort(tasks.begin(), tasks.end(),
08          [](const Task& a, const Task& b) {
09              return a.profit > b.profit;
10     });
11 }
12 
13 int maxProfit(vector<Task>& tasks) {
14     sortByProfit(tasks);
15
16     int maxTime = 0;
17     for (auto& t : tasks) {
18         maxTime = max(maxTime, t.deadline);
19     }
20 
21     vector<bool> slot(maxTime + 1, false);
22     int totalProfit = 0;
23 
24     for (auto& task : tasks) {
25         for (int t = task.deadline; t >= 1; t--) {
26             if (!slot[t]) {
27
28                 __________ //在此处填入代码
29                 break;
30             }
31         }
32     }
33     
34     return totalProfit;
35 }

{{ select(14) }}

• 01 slot[t] = true;
  02 totalProfit += task.profit;
  

• 01 slot[t] = false;
  02 totalProfit += task.profit;
  

• 01 slot[t] = true;
  02 totalProfit = task.profit;
  

• 01 
  02 slot[t] = false;
  03 totalProfit = task.profit
  

第 15 题 下面代码实现了对两个数组表示的正整数的高精度加法(数组低位在前)，则横线上应填写( )

01 vector<int> add(vector<int> a, vector<int> b) {
02     vector<int> c;
03     int carry = 0;
04 
05     for (int i = 0; i < a.size() || i < b.size(); i++) {
06         if (i < a.size()) carry += a[i];
07         if (i < b.size()) carry += b[i];
08         _____________  //在此处填入代码
09     }
10     if (carry) c.push_back(carry);
11
12     return c;
13 }

{{ select(15) }}

• 01 c.push_back(carry / 10);
  02 carry %= 10;
  

• 01 c.push_back(carry % 10);
  02 carry /= 10;
  

• 01 c.push_back(carry % 10);
  

• 01 c.push_back(carry);
  02 carry /= 10;
  

二、判断题（每题 2 分，共 20 分）

第 1 题 数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。

{{ select(16) }}

• 正确
• 错误

第 2 题 假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 Lcm(a，b) 函数能正确找到两个正整数 $a$ 和 $b$ 的最小公倍数。

01 int lcm(int a, int b) {
02    return a / gcd(a, b) * b;
03 }

{{ select(17) }}

• 正确
• 错误

第 3 题 在单链表中，已知指针 p 指向要删除的结点(非尾结点)，想在 $O(1)$ 删除 p，可行做法是用 p->next 覆盖 p 的值与 next，然后删除 p->next。

{{ select(18) }}

• 正确
• 错误

第 4 题 在求解所有不大于 $n$ 的素数时，线性筛法(欧拉筛)都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为 $O(n)$，低于埃氏筛法的 $O(nloglogn)$。

{{ select(19) }}

• 正确
• 错误

第 5 题 二分查找仅适用于有序数据。若输入数据无序，当仅进行一次查找时，为了使用二分而排序通常不划算。

{{ select(20) }}

• 正确
• 错误

第 6 题 通过在数组的第一个、最中间和最后一个这 $3$ 个数据中选择中间值作为枢轴(比较基准)，快速排序算法可降低落入最坏情况的概率。

{{ select(21) }}

• 正确
• 错误

第 7 题 贪心算法在每一步都做出当前看来最优的局部选择，并且一旦做出选择就不再回溯;而分治算法将问题分解为若干子问题分别求解，再将子问题的解合并得到原问题的解。

{{ select(22) }}

• 正确
• 错误

第 8 题 以下 fib 函数计算第 $n$ 项斐波那契数 (fib(0)=0，fib(1)=1)，其时间复杂度为 $O(n)$。

01 int fib(int n) {
02     if (n <= 1) return n;
03     return fib(n-1) + fib(n-2);
04 }

{{ select(23) }}

• 正确
• 错误

第 9 题 递归函数一定要有终止条件，否则可能会造成栈溢出。

{{ select(24) }}

• 正确
• 错误

第 10 题 使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。

{{ select(25) }}

• 正确
• 错误