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

1. 下面 $\tt C$++ 代码用于求斐波那契数列，该数列第 $1$、$2$ 项为 $1$，以后各项均是前两项之和。函数 $\tt fibo()$ 属于（ ）。

   int fibo(int n) {
       if (n <= 0)
           return 0;
       if (n == 1 || n == 2)
           return 1;
       int a = 1, b = 1, next;
       for (int i = 3; i <= n; i++) {
           next = a + b;
           a = b;
           b = next;
       }
       return next;
   }
   

{{ select(1) }}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

2. 下面 $\tt C$++ 代码用于将输入金额换成最少币种组合方案，其实现算法是（ ）。

   #include <iostream>
   using namespace std;
   
   #define N_COINS 7
   int coins[N_COINS] = {100, 50, 20, 10, 5, 2, 1}; //货币面值，单位相同
   int coins_used[N_COINS];
   
   void find_coins(int money) {
       for (int i = 0; i < N_COINS; i++) {
           coins_used[i] = money / coins[i];
           money = money % coins[i];
       }
       return;
   }
   int main() {
       int money;
       cin >> money; //输入要换算的金额
       
       find_coins(money);
       for (int i = 0; i < N_COINS; i++)
           cout << coins_used[i] << endl;
     
       return 0;
   }
   

{{ select(2) }}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

3. 小杨采用如下双链表结构保存他喜欢的歌曲列表：

   struct dl_node {
       string song;
       dl_node* next;
       dl_node* prev;
   };
   

   小杨想在头指针为 $\tt head$ 的双链表中查找他喜欢的某首歌曲，采用如下查询函数，该操作的时间复杂度为（ ）。

   dl_node* search(dl_node* head, string my_song) {
       dl_node* temp = head;
       while (temp != nullptr) {
           if (temp->song == my_song)
               return temp;
           temp = temp->next;
       }
       return nullptr;
   }
   

{{ select(3) }}

• $O(1)$
• $O(n)$
• $O(\log n)$
• $O(n^2)$

4. 小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌曲，则下面横线上应填入的代码为（ ）。

   void insert(dl_node *head, string my_song) {
       p = new dl_node;
       p->song = my_song;
       p->prev = nullptr;
       p->next = head;
       if (head != nullptr) {
           ________________________________ // 在此处填入代码
       }
       head = p;
   }
   

{{ select(4) }}

• head->next->prev = p;
• head->next = p;
• head->prev = p;
• 触发异常，不能对空指针进行操作

5. 下面是根据欧几里得算法编写的函数，它计算的是 $a$ 与 $b$ 的（ ）。

   int gcd(int a, int b) {
       while (b != 0) {
           int temp = b;
           b = a % b;
           a = temp;
       }
       return a;
   }
   

{{ select(5) }}

• 最小公倍数
• 最大公共质因子
• 最大公约数
• 最小公共质因子

6. 欧几里得算法还可以写成如下形式：

   int gcd(int a, int b) {
       return b == 0 ? a : gcd(b, a % b);
   }
   

   下面有关说法，错误的是（ ）。

{{ select(6) }}

• 本题的 $\tt gcd()$ 实现为递归方式
• 本题的 $\tt gcd()$ 代码量少，更容易理解其辗转相除的思想
• 当 $a$ 较大时，本题的 $\tt gcd()$ 实现会多次调用自身，需要较多额外的辅助空间
• 当 $a$ 较大时，相比上题中的 $\tt gcd()$ 的实现，本题的 $\tt gcd()$ 执行效率更高

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

   vector<int> linear_sieve(int n) {
       vector<bool> is_prime(n + 1, true);
       vector<int> primes;
       is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
       for (int i = 2; i <= n; ++i) {
           if (is_prime[i]) {
               primes.push_back(i);
           }
           ________________________________ { // 在此处填入代码
               is_prime[i * primes[j]] = 0;
               if (i % primes[j] == 0)
                   break;
           }
       }
       return primes;
   }
   

{{ select(7) }}

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

8. 上题代码的时间复杂度是（ ）。

{{ select(8) }}

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

9. 为了正确实现快速排序，下面横线上的代码应为（ ）。

   void qsort(vector<int>& arr, int left, int right) {
       int i, j, mid;
       int pivot;
       i = left;
       j = right;
       mid = (left + right) / 2; // 计算中间元素的索引
       pivot = arr[mid]; // 选择中间元素作为基准值
       do {
           while (arr[i] < pivot) i++;
           while (arr[j] > pivot) j--;
           if (i <= j) {
               swap(arr[i], arr[j]); // 交换两个元素
               i++; j--;
           }
       } ________________________________; // 在此处填入代码
       if (left < j) qsort(arr, left, j); // 对左子数组进行快速排序
       if (i < right) qsort(arr, i, right); // 对右子数组进行快速排序
   }
   

{{ select(9) }}

• while (i <= mid)
• while (i < mid)
• while (i < j)
• while (i <= j)

10. 关于分治算法，以下哪个说法正确？（ ）

{{ select(10) }}

• 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果
• 归并排序不是分治算法的应用
• 分治算法通常用于解决小规模问题
• 分治算法的时间复杂度总是优于 $O(n \log n)$

11. 根据下述二分查找法，在排好序的数组 $1$，$3$，$6$，$9$，$17$，$31$，$39$，$52$，$61$，$79$，$81$，$90$，$96$ 中查找数值 $82$，和 $82$ 比较的数组元素分别是（ ）。

    int binary_search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 如果找不到目标元素，返回-1
    }
    

{{ select(11) }}

• $52,\ 61,\ 81,\ 90$
• $52,\ 79,\ 90,\ 81$
• $39,\ 79,\ 90,\ 81$
• $39,\ 79,\ 90$

12. 要实现一个高精度减法函数，则下面代码中加划线应该填写的代码为（ ）。

    //假设a和b均为正数，且a表示的数比b大
    vector<int> minus(vector<int> a, vector<int> b) {
        vector<int> c;
        int len1 = a.size();
        int len2 = b.size();
        int i, t;
        for (i = 0; i < len2; i++) {
            if (a[i] < b[i]) { //借位
                _____________ // 在此处填入代码
                a[i] += 10;
            }
            t = a[i] - b[i];
            c.push_back(t);
        }
        for (; i < len1; i++)
            c.push_back(a[i]);
        len3 = c.size();
        while (c[len3 - 1] == 0) {//去除前导0
            c.pop_back();
            len3--;
        }
    return c;
    }
    

{{ select(12) }}

• a[i + 1]--;
• a[i]--;
• b[i + 1]--;
• b[i]--;

13. 设 $A$ 和 $B$ 是两个长度为 $n$ 的有序数组，现将 $A$ 和 $B$ 合并成一个有序数组，归并排序算法在最坏情况下至少要做（ ）次比较。

{{ select(13) }}

• $n^2$
• $n \log n$
• $2n - 1$
• $n$

14. 给定如下函数：

    int fun(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return fun(n - 2) - fun(n - 1);
    }
    

    则当 $n=7$ 时，函数返回值为（ ）。

{{ select(14) }}

• $0$
• $1$
• $21$
• $-11$

15. 给定如下函数（函数功能同上题，增加输出打印）：

    int fun(int n) {
        cout << n << " ";
        if (n == 1) return 1;
        if (n == 2) return 2;
        return fun(n - 2) - fun(n - 1);
    }
    

    则当 $n=4$ 时，屏幕上输出序列为（ ）。

{{ select(15) }}

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

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

1. 如果将双向链表的最后一个结点的下一项指针指向第一个结点，第一个结点的前一项指针指向最后一个结点，则该双向链表构成循环链表。（ ）

{{ select(16) }}

• 正确
• 错误

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

{{ select(17) }}

• 正确
• 错误

3. 链表的存储空间物理上可以连续，也可以不连续。（ ）

{{ select(18) }}

• 正确
• 错误

4. 找出自然数 $n$ 以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中埃氏筛法效率更高。（ ）

{{ select(19) }}

• 正确
• 错误

5. 唯一分解定理表明任何一个大于 $1$ 的整数都可以唯一地表示为一系列质数的乘积，即质因数分解是唯一的。（ ）

{{ select(20) }}

• 正确
• 错误

6. 贪心算法通过每一步选择局部最优解来获得全局最优解，但并不一定能找到最优解。（ ）

{{ select(21) }}

• 正确
• 错误

7. 归并排序和快速排序都采用递归实现，也都是不稳定排序。（ ）

{{ select(22) }}

• 正确
• 错误

8. 插入排序有时比快速排序时间复杂度更低。（ ）

{{ select(23) }}

• 正确
• 错误

9. 在进行全国人口普查时，将其分解为对每个省市县乡来进行普查和统计。这是典型的分治策略。（ ）

{{ select(24) }}

• 正确
• 错误

10. 在下面 $\tt C$++ 代码中，由于删除了变量 $\tt ptr$，因此 $\tt ptr$ 所对应的数据也随之删除，故执行下述代码时，将报错。（ ）

    int* ptr = new int(10);
    cout << *ptr << endl;
    delete ptr;
    cout << ptr << endl;
    

{{ select(25) }}

• 正确
• 错误