#G109. GESP level5 2025年3月

GESP level5 2025年3月

GESP level5 - 2025年3月

  1. 链表不具备的特点是( )。 {{ select(1) }}
  • 可随机访问任何一个元素
  • 插入、删除操作不需要移动元素
  • 无需事先估计存储空间大小
  • 所需存储空间与存储元素个数成正比
  1. 双向链表中每个结点有两个指针域prev和next,分别指向该结点的前驱及后继结点。设p指向链表中的一个结点,它的前驱结点和后继结点均非空。要删除结点p,则下述语句中错误的是( )。 {{ select(2) }}
  • p->next->prev = p->next; p->prev->next = p->prev; delete p;
  • p->prev->next = p->next; p->next->prev = p->prev; delete p;
  • p->next->prev = p->prev; p->next->prev->next = p->next; delete p;
  • p->prev->next = p->next; p->prev->next->prev = p->prev; delete p;
  1. 假设双向循环链表包含头尾哨兵结点(不存储实际内容),分别为head和tail,链表中每个结点有两个指针域prev和next,分别指向该结点的前驱及后继结点。下面代码实现了一个空的双向循环链表,横线上应填的最佳代码是( )。 {{ select(3) }}
  • list->head->prev = list->head; list->tail->prev = list->head;
  • list->head->next = list->tail; list->tail->prev = list->head;
  • list->head->next = list->tail; list->tail->next = list->head;
  • list->tail->next = nullptr; list->head->next = list->tail;
  1. 用以下辗转相除法(欧几里得算法)求gcd(84, 60)的步骤中,第二步计算的数是( )。 {{ select(4) }}
  • 84和60
  • 60和24
  • 24和12
  • 12和0
  1. 根据唯一分解定理,下面整数的唯一分解是正确的( )。 {{ select(5) }}
  • 18=3 × 6
  • 28=4 × 7
  • 36=2 × 3 × 6
  • 30=2 × 3 × 5
  1. 下述代码实现素数表的线性筛法,筛选出所有小于等于n的素数,横线上应填的最佳代码是( )。 {{ select(6) }}
  • j < primes.size()
  • i * primes[j] <= n
  • j < primes.size() && i * primes[j] <= n
  • j <= n
  1. 在程序运行过程中,如果递归调用的层数过多,会因为( )引发错误。 {{ select(7) }}
  • 系统分配的栈空间溢出
  • 系统分配的堆空间溢出
  • 系统分配的队列空间溢出
  • 系统分配的链表空间溢出
  1. 对下面两个函数,说法错误的是( )。 {{ select(8) }}
  • 两个函数的实现的功能相同。
  • 两个函数的时间复杂度均为O(n)。
  • factorialA采用递归方式。
  • factorialB采用递归方式。
  1. 下列算法中,( )是不稳定的排序。 {{ select(9) }}
  • 选择排序
  • 插入排序
  • 归并排序
  • 冒泡排序
  1. 考虑以下C++代码实现的快速排序算法,将数据从小到大排序,则横线上应填的最佳代码是( )。 {{ select(10) }}
  • if (arr[j] > pivot) { i++; swap(arr[i], arr[j]); }
  • if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); }
  • if (arr[j] < pivot) { swap(arr[i], arr[j]); i++; }
  • if (arr[j] == pivot) { i++; swap(arr[i], arr[j]); }
  1. 若用二分法在[1, 100]内猜数,最多需要猜( )次。 {{ select(11) }}
  • 100
  • 10
  • 7
  • 5
  1. 下面代码实现了二分查找算法,在数组arr找到目标元素target的位置,则横线上能填写的最佳代码是( )。 {{ select(12) }}
  • int mid = left + (right - left) / 2;
  • int mid = left;
  • int mid = (left + right) / 2;
  • int mid = right;
  1. 贪心算法的核心特征是( )。 {{ select(13) }}
  • 总是选择当前最优解
  • 回溯尝试所有可能
  • 分阶段解决子问题
  • 总能找到最优解
  1. 函数int findMax(int arr[], int low, int high)计算数组中最大元素,其中数组arr从索引low到high,( )正确实现了分治逻辑。 {{ select(14) }}
  • if (low == high) return arr[low]; int mid = (low + high) / 2; return arr[mid];
  • if (low >= high) return arr[low]; int mid = (low + high) / 2; int leftMax = findMax(arr, low, mid - 1); int rightMax = findMax(arr, mid, high); return leftMax + rightMax;
  • if (low > high) return 0; int mid = low + (high - low) / 2; int leftMax = findMax(arr, low, mid); int rightMax = findMax(arr, mid + 1, high); return leftMax * rightMax;
  • if (low == high) return arr[low]; int mid = low + (high - low) / 2; int leftMax = findMax(arr, low, mid); int rightMax = findMax(arr, mid + 1, high); return (leftMax > rightMax) ? leftMax : rightMax;
  1. 小杨编写了一个如下的高精度乘法函数,则横线上应填写的代码为( )。 {{ select(15) }}
  • int temp = c[k];
  • int temp = c[k] + carry;
  • int temp = c[k] - carry;
  • int temp = c[k] * carry;
  1. 单链表中删除某个结点p(非尾结点),但不知道头结点,可行的操作是将p的值设为p->next的值,然后删除p->next。 {{ select(16) }}
  • 正确
  • 错误
  1. 链表存储线性表时要求内存中可用存储单元地址是连续的。 {{ select(17) }}
  • 正确
  • 错误
  1. 线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。 {{ select(18) }}
  • 正确
  • 错误
  1. 贪心算法通过每一步选择当前最优解,从而一定能获得全局最优解。 {{ select(19) }}
  • 正确
  • 错误
  1. 递归函数必须具有一个终止条件,以防止无限递归。 {{ select(20) }}
  • 正确
  • 错误
  1. 快速排序算法的时间复杂度与输入是否有序无关,始终稳定为O(n log n)。 {{ select(21) }}
  • 正确
  • 错误
  1. 归并排序算法的时间复杂度与输入是否有序无关,始终稳定为O(n log n)。 {{ select(22) }}
  • 正确
  • 错误
  1. 二分查找适用于对无序数组和有序数组的查找。 {{ select(23) }}
  • 正确
  • 错误
  1. 小杨有100元去超市买东西,每个商品有各自的价格,每种商品只能买1个,小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买,这体现了分治思想。 {{ select(24) }}
  • 正确
  • 错误
  1. 归并排序算法体现了分治算法,每次将大的待排序数组分成大小大致相等的两个小数组,然后分别对两个小数组进行排序,最后对排好序的两个小数组合并成有序数组。 {{ select(25) }}
  • 正确
  • 错误