GESP-C++五级 题库
印度古老的汉诺塔传说:创世时有三根金刚柱,其中一柱从下往上按照大小顺序摞着64片黄金圆盘,当圆盘逐一从一柱借助另外一柱全部移动到另外一柱时,宇宙毁灭。移动规则:在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。下面的C++代码以递归方式实现汉诺塔,横线处应填入代码是( )。

根据下面C++代码的注释,两个横线处应分别填入( )。

有关下面代码正确的是( )。

有关下面C++代码正确的是( )。

下面代码执行后的输出是( D )。

下面代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数 N 是否素数,有关其时间复杂度的正确说法是( )。

在上题的归并排序算法中, mergeSort(listData, start, middle); 和 mergeSort(listData, middle+ 1, end); 涉及到的算法为( )。
归并排序算法的基本思想是( )。(2023.9C++五级)
将数组分成两个子数组,分别排序后再合并。
随机选择一个元素作为枢轴,将数组划分为两个部分。
从数组的最后一个元素开始,依次与前一个元素比较并交换位置。
比较相邻的两个元素,如果顺序错误就交换位置。
有关下面代码的说法正确的是( )。

关于单链表、双链表和循环链表,下列说法正确的是( )。
双向循环链表中要在结点 p 之前插入新结点 s (均非空),以下指针操作正确的是( )。
下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点。横线处应填( )。
struct Node{
int val;
Node* next;
Node(int v):val(v),next(nullptr){}
};
Node* eraseAll(Node* head, int x){
Node dummy(0);
dummy.next = head;
Node* cur = &dummy;
while(cur->next){
if(cur->next->val == x){
Node* del = cur->next;
cur->next = del->next; // 空白处:让当前节点跳过待删除节点,直接指向后一个节点
delete del;
}else cur = cur->next;
}
return dummy.next;
}对如下代码实现的欧几里得算法(辗转相除法),执行 gcd(48, 18) 得到的调用序列为( )。
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}下面代码实现了欧拉(线性)筛,横线处应填写( )。
vector<int> euler_sieve(int n) {
vector<bool> is_composite(n + 1, false);
vector<int> primes;
for (int i = 2; i <= n; i++) {
if (!is_composite[i])
primes.push_back(i);
for (int j = 0; j < primes.size() && (long long)i * primes[j] <= n; j++) {
is_composite[i * primes[j]] = true;
if (i % primes[j] == 0)
break;
}
}
return primes;
}埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是( )。
vector<int> eratosthenes_sieve(int n) {
vector<bool> is_composite(n + 1, false);
vector<int> primes;
for (int i = 2; i <= n; i++) {
if (is_composite[i]) continue;
primes.push_back(i);
for (long long j = (long long)i * i; j <= n; j += i)
is_composite[j] = true;
}
return primes;
}下面程序的运行结果为( )。
bool check(int n, int a[], int k, int dist) {
int cnt = 1;
int last = a[0];
for (int i = 1; i < n; i++) {
if (a[i] - last >= dist) {
cnt++;
last = a[i];
}
}
return cnt >= k;
}
int solve(int n, int a[], int k) {
std::sort(a, a + n);
int l = 0;
int r = a[n - 1] - a[0];
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(n, a, k, mid))
l = mid;
else
r = mid - 1;
}
return l;
}
int main() {
int a[] = {1, 2, 8, 4, 9};
int n = 5;
int k = 3;
std::cout << solve(n, a, k) << std::endl;
return 0;
}在升序数组中查找第一个大于等于 x 的位置,下面循环中横线应填( )。
int lowerBound(const vector<int>& a, int x){
int L=0, r=a.size();
while(L<r){
int mid = L + (r - l)/2;
if(a[mid] >= x) r = mid;
else L = mid + 1;
}
return L;
}关于递归函数调用,下列说法错误的是( )。
给定 n 根木头,第 i 根长度为 a[i] 。要切成不少于 m 段等长木段,求最大可能长度,则横线上应填 写( )。
const int MAXN = 100005;
Long Long a[MAXN];
int n, m;
bool check(Long Long x){
Long Long cnt = 0;
for(int i = 1; i <= n; i++){
if(x == 0) return true;
cnt += a[i] / x;
if(cnt >= m) return true;
}
return false;
}
int main(){
cin >> n >> m;
Long Long mx = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
mx = max(mx, a[i]);
}
Long Long L = 1, r = mx;
Long Long ans = 0;
while(L <= r){
Long Long mid = L + (r - l) / 2;
if(check(mid)){
ans = mid;
----------------------
}else{
----------------------
}
}
cout << ans << endl;
return 0;
}