CCF GESP C++ 一级 (2024 年 03 月)

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

1. 唯一分解定理描述的内容是（）？

{{ select(1) }}

• 任意整数都可以分解为素数的乘积
• 每个合数都可以唯一分解为一系列素数的乘积
• 两个不同的整数可以分解为相同的素数乘积
• 以上都不对

2. 贪心算法的核心思想是（）？

{{ select(2) }}

• 在每一步选择中都做当前状态下的最优选择
• 在每一步选择中都选择局部最优解
• 在每一步选择中都选择全局最优解
• 以上都对

3. 下面的C++代码片段用于计算阶乘。请在横线处填入（），实现正确的阶乘计算。

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        ___________________// 在此处填入代码
    }
}

{{ select(3) }}

• return n * factorial(n - 1);
• return factorial(n - 1) / n;
• return n * factorial(n);
• return factorial(n / 2) *

4. 下面的代码片段用于在双向链表中删除一个节点。请在横线处填入（），使其能正确实现相应功能。

void deleteNode(DoublyListNode* &head,int value) {
  DoublyListNode* current = head;
  while (current != nullptr && current->val != value) {
    current = current->next;
}
if (current != nullptr) {
    if (current->prev != nullptr) {
        ________________// 在此处填入代码
    } else {
      head = current->next;
    }
    if (current->next != nullptr) {
      current->next->prev = current->prev;
    }
    delete current;
  }
}

{{ select(4) }}

• if (current->next != nullptr) current->next->prev = current->prev;
• current->prev->next = current->next;
• delete current->next;
• current->prev = current->next;

5. 辗转相除法也被称为（）？

{{ select(5) }}

• 高斯消元法
• 费马定理
• 欧几里德算法
• 牛顿迭代法

6. 面的代码片段用于计算斐波那契数列。该代码的时间复杂度是（）？

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

{{ select(6) }}

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

7. 下面的代码片段用于将两个高精度整数进行相加。请在横线处填入（），使其能正确实现相应功能。

string add(string num1, string num2) {
    string result;
    int carry = 0;
    int i = num1.size() - 1, j = num2.size() - 1;
    while (i >= 0 || j >= 0 || carry) {
        int x = (i >= 0) ? num1[i--] - '0' : 0;
        int y = (j >= 0) ? num2[j--] - '0' : 0;
        int sum = x + y + carry;
        carry = sum / 10;
        _______________________________________
    }
    return result;
}

{{ select(7) }}

• result = to_string(sum % 10) + result;
• result = to_string(carry % 10) + result;
• result = to_string(sum / 10) + result;
• result = to_string(sum % 10 + carry) + result;

8. 给定序列：1，3，6，9，17，31，39，52，61，79，81，90，96。使用以下代码进行二分查找查找元素 82时，需要循环多少次，即最后输出的 times 值为（ ）。

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    int times = 0;
    while (left <= right) {
        times ++;
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            cout << times << endl;
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << times << endl;
    return -1;
}

{{ select(8) }}

• 2
• 5
• 3
• 4

9. 下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改，使其能正确实现相应功能。（）

bool isPrime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i * i < num; ++i) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

{{ select(9) }}

• num < 2 应该改为 num <= 2
• 循环条件 i * i < num 应该改为 i * i <= num
• 循环条件应该是 i <= num
• 循环体中应该是 if (num % i != 0)

10. 在埃拉托斯特尼筛法中，要筛选出不大于n的所有素数，最外层循环应该遍历什么范围（）？

vector<int> sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    std::vector<int> primes;
    _______________________ {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

{{ select(10) }}

• for (int i = 2; i <= n; ++i)
• for (int i = 1; i < n; ++i)
• for (int i = 2; i <= sqrt(n); ++i)
• for (int i = 1; i <= sqrt(n); ++i)

11. 素数的线性筛法时间复杂度为（）。

{{ select(11) }}

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

12. 归并排序的基本思想是（）？

{{ select(12) }}

• 动态规划
• 分治
• 贪心算法
• 回溯算法

13. 在快速排序中，选择的主元素（pivot）会影响算法的（）？

{{ select(13) }}

• 不影响
• 时间复杂度
• 空间复杂度
• 时间复杂度和空间复杂度

14. 递归函数在调用自身时，必须满足（），以避免无限递归？

{{ select(14) }}

• 有终止条件
• 函数参数递减（或递增）
• 函数返回值固定
• 以上都对

15. 假设给定链表为: 1 -> 3 -> 5 -> 7 -> nullptr，若调用 searchValue(head, 5)，函数返回值为（）。

int searchValue(ListNode* head, int target) {
  while (head != nullptr) {
    if (head->val == target) {
      return 1;
    }
    head = head->next;
  }
  return 0;
}

{{ select(15) }}

• 返回1
• 返回0
• 死循环, 无法返回
• 返回-1

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

1. 辗转相除法用于求两个整数的最大公约数。

{{ select(16) }}

• 对
• 错

2. 插入排序的时间复杂度是 O(NlogN)。####

{{ select(17) }}

• 对
• 错

3. 二分查找要求被搜索的序列是有序的，否则无法保证正确性。

{{ select(18) }}

• 对
• 错

4. 使用贪心算法解决问题时，每一步的局部最优解一定会导致全局最优解。

{{ select(19) }}

• 对
• 错

5. 分治算法的核心思想是将一个大问题分解成多个相同或相似的子问题进行解决，最后合并得到原问题的解。

{{ select(20) }}

• 对
• 错

6. 分治算法的典型应用之一是归并排序，其时间复杂度为 O(NlogN)。

{{ select(21) }}

• 对
• 错

7. 素数表的埃氏筛法和线性筛法的时间复杂度都是 O(NloglogN)。

{{ select(22) }}

• 对
• 错

8. 贪心算法是一种可以应用于所有问题的通用解决方案。####

{{ select(23) }}

• 对
• 错

9. 单链表和双链表都可以在常数时间内实现在链表头部插入或删除节点的操作。####

{{ select(24) }}

• 对
• 错

10. 在C语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。

{{ select(25) }}

• 对
• 错