单选题

1. 与数组相比，链表在（ ）操作上通常具有更高的效率。

   {{ select(1) }}

• 随机访问元素
• 查找指定元素
• 在已知位置插入或删除节点
• 遍历所有元素

2. 下面 C++ 代码实现双向链表。函数 is_empty() 判断链表是否为空，如链表为空返回 true ，否则返回 false 。横线处不能填写（ ）。

   bool is_empty() const {
       return head.data == 0;
   }
   

   {{ select(2) }}

• return head == nullptr;
• return tail == nullptr;
• return head.data == 0;
• return size == 0;

3. 基于上题代码正确的前提下，填入相应代码完善 append()，用于在双向链表尾部增加新节点，横线上应填写（ ）。

   void append(int data) {
       Node* newNode = new Node(data, nullptr, nullptr);
       if (is_empty()) {
           head = tail = newNode;
       } else {
           tail->next = newNode;
           newNode->prev = tail;
           tail = newNode;
       }
       ++size;
   }
   

   {{ select(3) }}

• tail->next = newNode;
• newNode->prev = tail; tail = newNode;
• tail = newNode; newNode->prev = tail; tail->next = newNode;
• tail->next = newNode; newNode->prev = tail; tail = newNode;

4. 下列C++代码用循环链表解决约瑟夫问题，即假设n个人围成一圈，从第一个人开始数，每次数到第k个的人就出圈，输出最后留下的那个人的编号。横线上应填写（ ）。

   prev->next = p->next;
   delete p;
   p = prev->next;
   

   {{ select(4) }}

• prev->next = p->next; delete p; p = prev->next;
• delete p; prev->next = p->next; p = prev->next;
• delete p; p = prev->next; prev->next = p->next;
• prev->next = p->next; p = prev->next; delete p;

5. 下列C++代码判断一个正整数是否是质数，说法正确的是( )。

   bool is_prime(int n) {
       if (n <= 1) return false;
       if (n == 2 || n == 3 || n == 5) return true;
       if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false;
       int i = 7;
       int step = 4;
       int finish_number = sqrt(n) + 1;
       while (i <= finish_number) {
           if (n % i == 0) return false;
           i += step;
           step = 6 - step;
       }
       return true;
   }
   

   {{ select(5) }}

• 代码存在错误，比如5是质数，但因为5 % 5余数是0返回了false
• finish_number的值应该是n / 2，当前写法将导致错误
• 当前while循环正确的前提是：所有大于3的质数都符合6k±1形式
• while循环修改如下，其执行效果和执行时间相同。

6. 下列C++代码用两种方式求解两个正整数的最大公约数，说法错误的是( )。

   int gcd0(int big, int small) {
       if (big < small) swap(big, small);
       if (big % small == 0) return small;
       return gcd0(small, big % small);
   }
   int gcd1(int big, int small) {
       if (big < small) swap(big, small);
       for (int i = small; i >= 1; --i) {
           if (big % i == 0 && small % i == 0) return i;
       }
       return i;
   }
   

   {{ select(6) }}

• gcd0()函数的时间复杂度为O(log n)
• gcd1()函数的时间复杂度为O(n)
• 一般说来，gcd0()的效率高于gcd1()
• gcd1()中的代码for (int i = small; i >= 1; --i)应该修改为for (int i = small; i > 1; --i)

7. 下面的代码用于判断整数n是否是质数，错误的说法是( )。

   bool is_prime(int n) {
       if (n <= 1) return false;
       int finish_number = static_cast<int>(sqrt(n)) + 1;
       for (int i = 2; i < finish_number; ++i) {
           if (n % i == 0) return false;
       }
       return true;
   }
   

   {{ select(7) }}

• 换氏筛算法相对于上面的代码效率更高
• 线性筛算法相对于上面的代码效率更高
• 上面的代码有很多重复计算，因为不是判断单个数是否为质数，故而导致筛选出连续数中质数的效率不高
• 相对而言，换氏筛算法比上面代码以及线性筛算法效率都高

8. 唯一分解定理描述了关于正整数的什么性质？

   {{ select(8) }}

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

9. 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。

   int find_max_recursive(const vector<int>& nums, int left, int right) {
       if (left == right) return nums[left];
       int mid = left + (right - left) / 2;
       int left_max = find_max_recursive(nums, left, mid);
       int right_max = find_max_recursive(nums, mid + 1, right);
       return max(left_max, right_max);
   }
   

   {{ select(9) }}

• 该算法采用分治算法
• 该算法是递归实现
• 该算法采用贪心算法
• 该算法不是递推算法

10. 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。

    int find_max(const vector<int>& nums) {
        if (nums.empty()) throw invalid_argument("输入数组不能为空");
        int max_value = nums[0];
        for (int num : nums) {
            if (num > max_value) max_value = num;
        }
        return max_value;
    }
    

    {{ select(10) }}

• 本题 find_max() 函数采用的是迭代算法
• 本题 find_max() 函数的时间复杂度为 ( O(n) )
• 和上一题的 find_max() 相比，因为没有递归，所以没有栈的创建和销毁开销
• 本题 find_max() 函数和上一题的 find_max() 时间复杂度相同

11. 下面的 C++ 代码用于在升序数组 lst 中查找目标值 target 最后一次出现的位置。相关说法，正确的是（ ）。

    int binary_search_last_occurrence(const vector<int>& lst, int target) {
        if (lst.empty()) return -1;
        int low = 0, high = lst.size() - 1;
        while (low < high) {
            int mid = (low + high + 1) / 2;
            if (lst[mid] <= target) low = mid;
            else high = mid - 1;
        }
        if (lst[low] == target) return low;
        else return -1;
    }
    

    {{ select(11) }}

• 当 lst 中存在重复的 target 时，该函数总能返回最后一个 target 的位置，即便 lst 全由相同元素组成
• 当 target 小于 lst 中所有元素时，该函数会返回 0
• 循环条件改为 while (low <= high) 程序执行效果相同，且能提高准确性
• 将代码中 (low + high + 1) / 2 修改为 (low + high) / 2 效果相同

12. 有关下面C++代码的说法，错误的是（ ）。

    double sqrt_binary(long long n, double epsilon = 1e-10) {
        if (n < 0) throw invalid_argument("输入必须为非负整数");
        if (n == 0 || n == 1) return n;
        long long low = 1, high = n;
        long long k = 0;
        while (low <= high) {
            long long mid = (low + high) / 2;
            long long mid_sq = mid * mid;
            if (mid_sq == n) return mid;
            else if (mid_sq < n) {
                k = mid;
                low = mid + 1;
            } else high = mid - 1;
        }
        long long next_k = k + 1;
        if (next_k * next_k == n) return next_k;
        double low_d = (double)k;
        double high_d = (double)(k + 1);
        double mid;
        while (high_d - low_d >= epsilon) {
            mid = (low_d + high_d) / 2;
            double mid_sq = mid * mid;
            if (mid_sq < n) low_d = mid;
            else high_d = mid;
        }
        double result = (low_d + high_d) / 2;
        long long check_int = (long long(result + 0.5));
        if (check_int * check_int == n) return check_int;
        return result;
    }
    

    {{ select(12) }}

• "阶段1"的目标是寻找正整数n可能的正完全平方根
• "阶段2"的目标是如果正整数n没有正完全平方根，则在可能产生完全平方根附近寻找带小数点的平方根
• 代码check_int = (long long(result + 0.5)是检查因浮点误差是否为正完全平方根
• 阶段的二分法中high_d - low_d >= epsilon不能用于浮点数比较，会进入死循环

13. 硬币找零问题中要求找给客户最少的硬币。coins存储可用硬币规格、单位为角、假设规格都小于10角，且一定有1角规格。amount为要找零的金额，约定必须为1角的整数倍。输出为每种规格及其数量，按规格从大到小输出，如果某种规格不必要，则输出为0。下面是其实现代码，相关说法正确的是（ ）。

    const int MAX_COINS = 10;
    int result[MAX_COINS] = {0};
    int find_coins(const vector<int>& coins, int amount) {
        sort(coins.begin(), coins.end(), greater<int>());
        int n = coins.size();
        for (int i = 0; i < n; ++i) {
            int coin = coins[i];
            int num = amount / coin;
            result[i] = num;
            amount -= num * coin;
            if (amount == 0) break;
        }
        cout << "找零方案如下: " << endl;
        for (int i = 0; i < n; ++i) {
            cout << sorted_coins[i] << "角需要" << result[i] << "枚" << endl;
        }
        return 0;
    }
    

    {{ select(13) }}

• 上述代码采用贪心算法实现
• 针对本题具体要求，上述代码总能找到最优解
• 上述代码采用枚举算法
• 上述代码采用分治算法

14. 关于下述C++代码的快速排序算法，说法错误的是（ ）。

    int randomPartition(std::vector<int>& arr, int low, int high) {
        int random = low + rand() % (high - low + 1);
        std::swap(arr[random], arr[high]);
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        return i + 1;
    }
    void quickSort(std::vector<int>& arr, int low, int high) {
        if (low < high) {
            int pi = randomPartition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
    

    {{ select(14) }}

• 在randomPartition函数中，变量i的作用是记录大于基准值的元素的边界
• randomPartition函数随机选择基准值，可以避免输入数据特定模式导致的最坏情况下时间复杂度(O(n^2))
• 快速排序平均时间复杂度是(O(n\log n))
• 快速排序是稳定排序算法

15. 小杨编写了一个如下的高精度除法函数，则横线上应填写的代码为（ ）。

    r.d[0] = a.d[i];
    r.len = 1;
    

    {{ select(15) }}

• r.d[0] = a.d[i]; r.len++;
• r.d[i] = a.d[i]; r.len++;
• r.d[i] = a.d[i]; r.len = 1;
• r.d[0] = a.d[i]; r.len = 1;

判断题

1. 下面 C++代码是用欧几里得算法（辗转相除法）求两个正整数的最大公约数，a 大于 b 还是小于 b 都适用。

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

   {{ select(16) }}

• 对
• 错

2. 假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 len() 函数能相应两数的最小公倍数。

   int len(int a, int b) {
       return a * b / gcd(a, b);
   }
   

   {{ select(17) }}

• 对
• 错

3. 下面的C++代码用于输出每个数对应的质因数列表，输出形如：{5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]}。

   int main() {
       int n, m;
       cin >> n >> m;
       if (n > m) swap(n, m);
       map<int, vector<int>> prime_factor;
       for (int i = n; i <= m; ++i) {
           int j = 2, k = i;
           while (k != 1) {
               if (k % j == 0) {
                   prime_factor[i] = prime_factor[i] + j;
                   k / = j;
               } else {
                   ++j;
               }
           }
       }
       for (auto& p : prime_factor) {
           cout << p.first << ":";
           for (int v : p.second) cout << v << " ";
           cout << endl;
       }
       return 0;
   }
   

   {{ select(18) }}

• 对
• 错

4. 下面的C++代码实现归并排序。代码在执行时，将输出一次HERE字符串，因为merge()函数仅被调用一次。

   void merge(std::vector<int>& arr, int left, int mid, int right) {
       std::vector<int> temp(right - left + 1);
       int i = left;
       int j = mid + 1;
       int k = 0;
       while (i <= mid && j <= right) {
           if (arr[i] <= arr[j]) temp[k++] = arr[i++];
           else temp[k++] = arr[j++];
       }
       while (i <= mid) temp[k++] = arr[i++];
       while (j <= right) temp[k++] = arr[j++];
       for (int p = 0; p < k; ++p) arr[left + p] = temp[p];
   }
   void mergeSort(std::vector<int>& arr, int left, int right) {
       if (left >= right) return;
       int mid = left + (right - left) / 2;
       mergeSort(arr, left, mid);
       mergeSort(arr, mid + 1, right);
       std::cout << "HERE";
       merge(arr, left, mid, right);
   }
   

   {{ select(19) }}

• 对
• 错

5. 归并排序的最好、最坏和平均时间复杂度均为 ( O(n \log n) )。

   {{ select(20) }}

• 对
• 错

6. 查字典这个小学生必备技能，可以把字典视为一个已排序的数组。假设小杨要查找一个音首字母为g的单词，他首先翻到字典的一半的页数，发现该页的首字母是m，由于字母表中g位于m之前，所以排除字典后半部分，查找范围缩小到前半部分；不断重复上述步骤，直至找到首字母为g的页码。这种查字典的一系列操作可看作二分查找。

   {{ select(21) }}

• 对
• 错

7. 求解下图中A点到D点最短路径，其中A到B之间的12可以理解为距离。求解这样的问题常用Dijkstra算法，其思路是通过逐步选择当前距离起点最近的中点来求解非负权重图（如距离不能为负值）单源最短路径的算法。从该算法的描述可以看出，Dijkstra算法是贪心算法。

   {{ select(22) }}

• 对
• 错

8. 分治算法将原问题可以分解成规模更小的子问题，使得求解问题的难度降低。但由于分治算法需要将问题进行分解，并且需要将多个子问题的解合并为原问题的解，所以分治算法的效率通常比直接求解原问题的效率低。

   {{ select(23) }}

• 对
• 错

9. 函数puzzle定义如下，则调用puzzle(7)程序会无限递归。

   int puzzle(int n) {
       if (n == 1) return 1;
       if (n % 2 == 0) return puzzle(n / 2);
       return puzzle(3 * n + 1);
   }
   

   {{ select(24) }}

• 对
• 错

10. 如下为线性筛选，用于高效生成素数表，其核心思想是每个含数只被它的最小质因数筛掉一次，时间复杂度为 ( O(n) )。

    vector<int> linearSieve(int n) {
        vector<bool> is_prime(n + 1, true);
        vector<int> primes;
        for (int i = 2; i <= n; ++i) {
            if (is_prime[i]) primes.push_back(i);
            for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
                is_prime[i * primes[j]] = false;
                if (i % primes[j] == 0) break;
            }
        }
        return primes;
    }
    

    {{ select(25) }}

• 对
• 错