E1088 2026-09 CCF-GESP C++五级真题-练习

小杨用单链表保存任务序列，并同时维护头指针head 和尾指针tail。在链表非空且已知tail 的情况下，在表尾插入新结点的时间复杂度是（）。

struct Node {
	int value;
	Node *next;
};
Node *head ;
Node *tail;

在不带哨兵结点的双向链表中，结点p 既不是头结点也不是尾结点。删除p 的正确代码是（）。

struct Node {
	int value;
	Node *prev;
	Node *next;
};

下面函数使用快慢指针查找单链表的中间结点。横线处应填写（）。

struct Node {
	int value;
	Node *next;
};
Node *middle(Node *head) {
	Node *slow = head;
	Node *fast = head;
	while (fast != nullptr && fast->next != nullptr) {
		slow = slow->next;
		_______________
	}
	return slow;
}

函数gcd(int a , int b) 定义如下，则gcd(105 , 45) 的结果是（）。

int gcd(int a , int b) {
	return b == 0 ? a : gcd(b , a % b);
}

下面函数用于判断正整数n 是否为质数。横线处的最佳写法是（）。

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

下面代码实现线性筛法。为了保证每个合数只被其最小质因子筛去一次，横线处应填写（）。

vector<int> linearSieve(int n) {
	vector<bool> composite(n + 1 , false);
	vector<int> primes ;
	for (int i = 2; i <= n ; i++) {
		if (!composite [i])
			primes .push_back(i);
		for (int p : primes) {
			if ((long long)i * p > n)
				break;
			composite [i * p] = true ;
			if (__________)
				break;
		}
	}
	return primes ;
}

根据唯一分解定理，整数的正确质因数分解是（）。

函数f (int n) 定义如下，则f (4) 的结果是（）。

int f (int n) {
	if (n == 1)
		return 1;
	return n + f (n - 1);
}

在升序数组中查找第一个严格大于x 的元素位置，下面代码中的横线应填写（）。

int upperBound(const vector<int> &a , int x) {
	int l = 0 , r = (int)a .size();
	while (l < r) {
		int mid = l + (r - l) / 2;
		if ( __________ ) {
			l = mid + 1;
		} else {
			r = mid ;
		}
	}
	return l;
}

小杨需要把若干箱货物按原顺序分配到days 天中，每天运输连续的若干箱，求能够完成任务的最小载重量。函数check(cap) 判断载重量为cap 时能否在规定天数内运完。横线处应填写（）。

long long l = maxWeight;
long long r = totalWeight;
while (l < r) {
	long long mid = l + (r - l) / 2;
	if (check(mid)) {
		_______________ 
	} else {
		_______________
	}
}
cout << l;

下面是归并排序中合并两个有序区间（升序排序）的部分代码。若希望排序保持稳定，横线处应填写（）。

while (i <= mid && j <= right) {
	if (_______________) {
		temp .push_back(a [i++]);
	} else {
		temp .push_back(a [j++]);
	}
}

下面快速排序的划分函数以a [right] 为枢轴，并把不大于枢轴的元素移动到左侧。横线处应填写（）。

int partition(int a [], int left , int right) {
	int pivot = a [right];
	int i = left - 1;
	for (int j = left ; j < right ; j++) {
		if (_________________) {
			i++;
			swap(a [i], a [j]);
		}
	}
	swap(a [i + 1], a [right]);
	return i + 1;
}

小杨要在一个教室安排尽可能多场活动，每场活动具有开始时间start 和结束时间end 。采用贪心算法时，正确的选择策略是（）。

struct Activity {
	int start ;
	int end ;
};

下面函数使用迭代方法求最大连续子段和。对于数组{-2 , 3 , -1 , 5 , -6 , 2 }，函数返回值是（）。

int maxSubArray(const vector<int> &a) {
	int best = a [0];
	int current = a [0];
	for (int i = 1; i < (int)a .size(); i++) {
		current = max (a [i], current + a [i]);
		best = max (best , current);
	}
	return best ;
}

数组a 和b 按低位在前的顺序保存两个非负大整数。下面代码实现高精度加法，横线处应填写（）。

vector<int> add(const vector<int> &a , const vector<int> &b) {
	vector<int> c;
	int carry = 0 ;
	int n = max (a.size(), b.size());
	for (int i = 0 ; i < n ; i++) {
		int sum = carry;
		if (i < a.size())
			sum += a [i];
		if (i < b.size())
			sum += b [i];
		c.push_back(sum % 10);
		_____________________
	}
	if (carry)
		c.push_back(carry);
	return c;
}

下面代码在已知结点p 的情况下，能够以的时间在单链表的p 结点之后插入新结点s 。

s->next = p->next ;
p->next = s ;

下面代码可以安全地删除单链表的头结点，并使head 指向删除后的新头结点。

Node *p = head ;
delete p ;
head = p->next ;

下面欧几里得算法既适用于a > b，也适用于a < b，只要a、b 是正整数。

int gcd(int a , int b) {
	while (b != 0) {
		int r = a % b ;
		a = b ;
		b = r;
	}
	return a ;
}

下面埃氏筛从i * i 开始标记，是因为i * i 之前的i 的合数倍数已经被更小的质因子标记过。

for (int i = 2; (long long)i * i <= n ; i++) {
	if (isPrime [i]) {
		for (int j = i * i; j <= n ; j += i) {
			isPrime [j] = false ;
		}
	}
}

下面程序的时间复杂度为O(n)。

for (int i = 1; i <= n ; i *= 2) {
	cout << i << endl;
}

若数组a 已按升序排列，下面函数能够返回最后一个小于等于x 的元素下标；如果不存在，则返回 -1 。

int findLastLE(const vector<int> &a , int x) {
	int l = 0 , r = (int)a .size() - 1;
	int ans = -1;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (a [mid] <= x) {
			ans = mid ;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return ans ;
}

快速排序中如果选取区间第一个元素作为枢轴。当输入数组已经升序排列时，其最坏时间复杂度仍为 O(n log n)。

归并排序的递推式为 T(n) = 2T(n/2) + O(n)，对应的时间复杂度为 O(n log n)。

下面的贪心代码一定能对任意硬币面值集合coins 求出money 所需的最少硬币数。

int count = 0 ;
for (int coin : coins) { // coins 按面值从大到小排列
	count += money / coin;
	money %= coin;
}

假设两个非负高精度整数分别存储在数组a 和b 中，且。数组采用低位在前的方式存储，即 a [0] 表示个位。下面代码中的c 可以正确保存a - b 的各位数字。

int borrow = 0 ;
for (int i = 0 ; i < len ; ++i) {
	int t = a [i] - b [i] + borrow;
	if (t < 0) {
		t += 10 ;
		borrow = 1;
	} else {
		borrow = 0 ;
	}
	c [i] = t ;
}