综合知识点（栈溢出、约瑟夫问题、循环链表、数学性质等）（共 12 题）

单选题

1. 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。
   {{ select(1) }}

• 系统分配的栈空间溢出
• 系统分配的堆空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出

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

   int findLastSurvival(int n, int k) {
       Node* head = createCircularList(n);
       Node* p = head;
       Node* prev = nullptr;
       while (p->next != p) {
           for (int count = 1; count < k; ++count) {
               prev = p;
               p = p->next;
           }
           __________________;
       }
       return p->data;
   }
   

   {{ select(2) }}

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

3. 通讯卫星在通信网络系统中主要起到（ ）的作用。
   {{ select(3) }}

• 信息过滤
• 信号中继
• 避免攻击
• 数据加密

4. 小杨认为，所有大于等于 a 的完全平方数都是他的超级幸运数。小杨还认为，所有超级幸运数的倍数都是他的幸运数。自然地，小杨的所有超级幸运数也都是幸运数。对于一个非幸运数，小杨规定，可以将它一直 +1，直到它变成一个幸运数。我们把这个过程叫做幸运化。例如，如果 a = 4，那么 4 是最小的幸运数，而 1 不是，但我们可以连续对 1 做 3 次 +1 操作，使其变为 4，所以我们可以说，1 幸运化后的结果是 4。对于给定的 a 和多个 x，需要判断 x 是否为幸运数，若不是则输出幸运化后的结果。解决这个问题可以采用（ ）。
   {{ select(4) }}

• 埃氏筛思想预处理幸运数
• 贪心算法
• 动态规划
• 分治算法

5. 下面的 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].push_back(j);
                   k /= j;
               } else ++j;
           }
       }
       // 输出...
   }
   

   {{ select(5) }}

• 唯一分解定理的应用
• 贪心算法
• 动态规划
• 分治算法

6. 小杨想写一个程序来算出正整数 N 有多少个因数，经过思考他写出了一个重复没有超过 N/2 次的循环就能够算出来了。这个循环的范围应该是（ ）。
   {{ select(6) }}

• 1 到 N
• 1 到 N/2
• 1 到 √N
• 2 到 N/2

7. 小杨设计了一个拆数程序，它能够将任意的非质数自然数 N 转换成若干个质数的乘积，这个程序是可以设计出来的。这是基于（ ）。
   {{ select(7) }}

• 唯一分解定理
• 费马小定理
• 欧拉定理
• 威尔逊定理

8. 下面的代码用于判断一个正整数是否为完全数（该数是否等于它的真因子之和），则横线上应填写（ ）。
   一个正整数 n 的真因子包括所有小于 n 的正因子，如 28 的真因子为 1，2，4，7，14。

   bool isPerfectNumber(int n) {
       if (n <= 1) return false;
       int sum = 1;
       for (int i = 2; __________________; i++) {
           if (n % i == 0) {
               sum += i;
               if (i != n / i) sum += n / i;
           }
       }
       return sum == n;
   }
   

   {{ select(8) }}

• i <= n
• i * i <= n
• i <= n / 2
• i < n

9. 小杨编写了一个如下的高精度除法函数，其中需要将余数的下一位加入，则横线上应填写的代码为（ ）。

   // 高精度除法 (a/b, 返回商和余数)
   pair<BigInt, BigInt> div(BigInt a, BigInt b) {
       // ... 初始化
       for (int i = a.len - b.len; i >= 0; i--) {
           // 把下一位加入余数
           if (r.len > 1 || r.d[0] != 0) {
               for (int j = r.len; j > 0; j--) {
                   r.d[j] = r.d[j-1];
               }
               __________________;
           } else {
               __________________;
           }
           // 计算当前位的商...
       }
   }
   

   {{ select(9) }}

• 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;

10. 下面代码实现了欧几里得算法。下面有关说法，错误的是（ ）。

    int gcd(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) return small;
        return gcd(small, big % small);
    }
    

    {{ select(10) }}

• 该算法可以求出最大公约数
• 该算法的时间复杂度为 O(log min(a,b))
• 如果 a 和 b 都是质数，该算法会递归一次
• 该算法在 a 和 b 相差很大时效率较低

判断题

11. 递归函数必须具有一个终止条件，以防止无限递归。
    {{ select(11) }}

• 正确
• 错误

12. 小杨有 100 元去超市买东西，每个商品有各自的价格，每种商品只能买 1 个，小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买，这体现了分治思想。
    {{ select(12) }}

• 正确
• 错误