#G107. GESP level5 2024年6月

GESP level5 2024年6月

GESP level5 - 2024年6月

  1. 下面C++代码用于求斐波那契数列,该数列第1、2项为1,以后各项均是前两项之和。函数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) }}
  • 枚举算法
  • 贪心算法
  • 迭代算法
  • 递归算法
  1. 下面C++代码用于将输入金额换成最少币种组合方案,其实现算法是( )
    #include 
    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];
    }
    }
    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) }}
  • 枚举算法
  • 贪心算法
  • 迭代算法
  • 递归算法
  1. 小杨采用如下双链表结构保存他喜欢的歌曲列表:
    struct dl_node {
    string song;
    dl_node* next;
    dl_node* prev;
    };
    小杨想在头指针为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(n²)
  • O(log n)
  1. 小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲,他将其作为链表的第一首歌曲,则下面横线上应填入的代码为( )
    void insert(dl_node* head, string my_song) {
    dl_node* 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;
  • 触发异常,不能对空指针进行操作。
  1. 下面是根据欧几里得算法编写的函数,它计算的是a与b的( )
    int gcd(int a, int b) {
    while (b != 0) {
    int temp = b;
    b = a % b;
    a = temp;
    }
    return a;
    }
    {{ select(5) }}
  • 最小公倍数
  • 最大公共质因子
  • 最大公约数
  • 最小公共质因子
  1. 欧几里得算法还可以写成如下形式:
    int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
    }
    下面有关说法,错误的是( ) {{ select(6) }}
  • 本题的gcd()实现为递归方式。
  • 本题的gcd()代码量少,更容易理解其辗转相除的思想。
  • 当a、b较大时,本题的gcd()实现会多次调用自身,需要较多额外的辅助空间。
  • 当a、b较大时,相比上题中的gcd()的实现,本题的gcd()执行效率更高。
  1. 下述代码实现素数表的线性筛法,筛选出所有小于等于n的素数,则横线上应填的代码是( )
    vector linear_sieve(int n) {
    vector is_prime(n + 1, true);
    vector 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);
    }
    // 在此处填入代码
    for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
    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++)
  1. 上题代码的时间复杂度是( ) {{ select(8) }}
  • O(n)
  • O(n log n)
  • O(n log log n)
  • O(n²)
  1. 为了正确实现快速排序,下面横线上的代码应为( )
    void qsort(vector& arr, int left, int right) {
    int i, j, pivot;
    i = left; j = right;
    pivot = arr[(left + right) / 2]; // 选择中间元素作为基准值
    do {
    while (arr[i] < pivot) i++;
    while (arr[j] > pivot) j--;
    if (i <= j) {
    swap(arr[i], arr[j]); // 交换两个元素
    i++;
    j--;
    }
    } // 在此处填入代码
    while (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)
  1. 关于分治算法,以下哪个说法正确? {{ select(10) }}
  • 分治算法将问题分成子问题,然后分别解决子问题,最后合并结果。
  • 归并排序不是分治算法的应用。
  • 分治算法通常用于解决小规模问题。
  • 分治算法的时间复杂度总是优于O(n log n)。
  1. 根据下述二分查找法,在排好序的数组1,3,6,9,17,31,39,52,61,79,81,90,96中查找数值82,和82比较的数组元素分别是( )
    int binary_search(vector& 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;
    }
    {{ select(11) }}
  • 52, 61, 81, 90
  • 52, 79, 90, 81
  • 39, 79, 90, 81
  • 39, 79, 90
  1. 要实现一个高精度减法函数,则下面代码中加划线应该填写的代码为( )
    // 假设a和b均为正数,且a表示的数比b大
    vector minus(vector a, vector b) {
    vector 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]);
    }
    int len3 = c.size();
    while (c[len3 - 1] == 0) {
    c.pop_back();
    len3--;
    }
    return c;
    }
    {{ select(12) }}
  • a[i + 1]--;
  • a[i]--;
  • b[i + 1]--;
  • b[i]--;
  1. 设A和B是两个长度为n的有序数组,现将A和B合并成一个有序数组,归并排序算法在最坏情况下至少要做( )次比较。 {{ select(13) }}
  • n-1
  • n
  • 2n-1
  • 2n
  1. 给定如下函数:
    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
  1. 给定如下函数(函数功能同上题,增加输出打印):
    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
  1. 如果将双向链表的最后一个结点的下一项指针指向第一个结点,第一个结点的前一项指针指向最后一个结点,则该双向链表构成循环链表。 {{ select(16) }}
  • 正确
  • 错误
  1. 数组和链表都是线性表,链表的优点是插入删除不需要移动元素,并且能随机查找。 {{ select(17) }}
  • 正确
  • 错误
  1. 链表的存储空间物理上可以连续,也可以不连续。 {{ select(18) }}
  • 正确
  • 错误
  1. 找出自然数n以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中埃氏筛法效率更高。 {{ select(19) }}
  • 正确
  • 错误
  1. 唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积,即质因数分解是唯一的。 {{ select(20) }}
  • 正确
  • 错误
  1. 贪心算法通过每一步选择局部最优解来获得全局最优解,但并不一定能找到最优解。 {{ select(21) }}
  • 正确
  • 错误
  1. 归并排序和快速排序都采用递归实现,也都是不稳定排序。 {{ select(22) }}
  • 正确
  • 错误
  1. 插入排序有时比快速排序时间复杂度更低。 {{ select(23) }}
  • 正确
  • 错误
  1. 在进行全国人口普查时,将其分解为对每个省市县乡来进行普查和统计。这是典型的分治策略。 {{ select(24) }}
  • 正确
  • 错误
  1. 在下面C++代码中,由于删除了变量ptr,因此ptr所对应的数据也随之删除,故执行下述代码时,将报错。
    int* ptr = new int(10);
    cout << *ptr << endl;
    delete ptr;
    cout << ptr << endl;
    {{ select(25) }}
  • 正确
  • 错误