首页 › 题库 › GESP编程能力等级认证 › GESP-C++五级

GESP-C++五级 题库

共 297 道题 ,第 4 / 15 页 · 按题型筛选,点「查看答案」核对解析
61 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

下面关于链表和数组的描述,错误的是( )。

A
当数据数量不确定时,为了应对各种可能的情况,需要申请一个较大的数组,可能浪费空间;此时用链表比较合适,大小可动态调整。
B
在链表中访问节点的效率较低,时间复杂度为 O(n)。
C
链表插入和删除元素效率较低,时间复杂度为 O(n)。
D
链表的节点在内存中是分散存储的,通过指针连在一起。
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
62 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

在循环单链表中,节点的 next 指针指向下一个节点,最后一个节点的 next 指针指向( )。

A
当前节点
B
nullptr
C
第一个节点
D
上一个节点
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
63 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

为了方便链表的增删操作,一些算法生成一个虚拟头节点,方便统一删除头节点和其他节点。下面代码实现了删除链表中值为 val 的节点,横线上应填的最佳代码是( )。

struct LinkedNode {
	int val;
	LinkedNode* next;
	LinkedNode(int val):val(val), next(nullptr){}
};

void removeElements(LinkedNode* head, int val) {
	if (head == nullptr) {
		return;
	}
	LinkedNode* cur;
	LinkedNode* dummyHead = new LinkedNode(0); //虚拟头节点
	________________________________ // 在此处填入代码
	while(cur ->next != nullptr) {
		if(cur->next->val == val) {
			LinkedNode* tmp = cur->next;
			cur->next = cur->next->next;
			delete tmp;
			tmp = nullptr;
		}
		else {
			cur = cur ->next;
		}
	}
	head = dummyHead->next;
	delete dummyHead;
	dummyHead = nullptr;
}
A
dummyHead->next = head; cur = dummyHead;
B
dummyHead->next = head->next; cur = dummyHead;
C

dummyHead->next = head; cur = dummyHead->next;

D

dummyHead->next = head->next; cur = dummyHead->next;

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
64 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

对下面两个函数,说法错误的是( )。

int fibA(int n) {
	if (n <= 1) return n;
	
	int f1 = 0, f2 = 1;
	for (int i = 2; i <= n; ++i) {
		int temp = f2;
		f2 = f1 + f2;
		f1 = temp;
	}
	return f2;
}
int fibB(int n) {
if (n <= 1) return n;
return fibB(n - 1) + fibB(n - 2);
}
A
两个函数的实现的功能相同。
B
fibA采用递推方式。
C
fibB采用的是递归方式。
D
fibA时间复杂度为 O(n),fibB的时间复杂度为 O(n)。
答案与解析
正确答案:D
这道题暂未补解析。
题目详情

两块长方形土地的长宽分别为 24 和 36 米,要将它们分成正方形的小块,使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24, 36) 来求正方形分块的边长,则函数 gcd 调用顺序为( )。

int gcd(int a, int b) {
	int big = a > b ? a : b;
	int small = a < b ? a : b;
	if (big % small == 0) {
		return small;
	}
	return gcd(small, big % small);
}
A
gcd(24, 36)、gcd(24, 12)、gcd(12, 0)
B
gcd(24, 36)、gcd(12, 24)、gcd(0, 12)
C
gcd(24, 36)、gcd(24, 12)
D
gcd(24, 36)、gcd(12, 24)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
66 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

唯一分解定理表明,每个大于1的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数 n 的所有质因素找出来,横线上能填写的最佳代码是( )。

#include <vector>
vector<int> get_prime_factors(int n) {
	vector<int> factors;
	if (n <= 1) {
		cout << "输入的数必须是大于1的正整数" << endl;
		return;
	}
	while (n % 2 == 0) {
		factors.push_back(2);
		n /= 2;
	}
	
	________________________________ { // 在此处填入代码
		while (n % i == 0) {
			factors.push_back(i);
			n /= i;
		}
	}
	
	if (n > 2) {
		factors.push_back(n);
	}
	
	return factors;
}
A
for (int i = 3; i <= n; i ++)
B
for (int i = 3; i * i <= n; i ++)
C
for (int i = 3; i <= n; i += 2)
D
for (int i = 3; i * i <= n; i += 2)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
67 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的埃拉托色尼(埃氏)筛法,筛选出所有小于等于 n 的素数。

vector<int> sieve_Eratosthenes(int n) {
	vector<bool> is_prime(n +1, true);
	vector<int> primes;
	
	for (int i = 2; i * i <= n; i++) {
		if (is_prime[i]) {
			primes.push_back(i);
			
			for (int j = i * i; j <= n; j += i) {
				is_prime[j] = false;
			}
		}
	}
	
	for (int i = sqrt(n) + 1; i <= n; i++) {
		if (is_prime[i]) {
			primes.push_back(i);
		}
	}
	
	return primes;
}

下面说法,正确的是( )。

A
代码的时间复杂度是 O(nn)。
B
在标记非素数时,代码从 i2开始,可以减少重复标记。
C
代码会输出所有小于等于 n 的奇数。
D
调用函数 sieve_Eratosthenes(10) ,函数返回值的数组中包含的元素有: 2, 3, 5, 7, 9 。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
68 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数。下面说法正确的是( )。

vector<int> sieve_linear(int n) {
	vector<bool> is_prime(n +1, true);
	vector<int> primes;
	
	for (int i = 2; i <= n/2; 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;
		}
	}
	
	for (int i = n/2 +1; i <= n; i++) {
		if (is_prime[i])
			primes.push_back(i);
	}
	
	return primes;
}
A
线性筛的时间复杂度是 O(n)。
B
每个合数会被其所有的质因子标记一次。
C
线性筛和埃拉托色尼筛的实现思路完全相同。
D
以上都不对
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
69 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

考虑以下C++代码实现的快速排序算法:

int partition(vector<int>& arr, int left, int right) {
	int pivot = arr[right]; // 基准值
	int i = left - 1;
	
	for (int j = left; j < right; j++) {
		if (arr[j] < pivot) {
			i++;
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[i + 1], arr[right]);
	return i + 1;
}

// 快速排序
void quickSort(vector<int>& arr, int left, int right) {
	if (left < right) {
		int pi = partition(arr, left, right);
		quickSort(arr, left, pi - 1);
		quickSort(arr, pi + 1, right);
	}
}

以下关于快速排序的说法,正确的是( )。

A
快速排序通过递归对子问题进行求解。
B
快速排序的最坏时间复杂度是 O(nlogn)。
C
快速排序是一个稳定的排序算法。
D
在最优情况下,快速排序的时间复杂度是 O(n)。
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
70 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下面关于归并排序,描述正确的是( )。

A
归并排序是一个不稳定的排序算法。
B
归并排序的时间复杂度在最优、最差和平均情况下都是 (nlogn)。
C
归并排序需要额外的 O(1) 空间。
D
对于输入数组 {12, 11, 13, 5, 6, 7},代码输出结果为:7 6 5 13 12 11。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
71 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

给定一个长度为 n 的有序数组 nums ,其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索引。

int binarySearch(vector<int> &nums, int target, int left, int right) {
	if (left > right) {
		return -1;
	}
	
	int middle = left + ((right - left) / 2);
	if (nums[middle] == target) {
		return middle;
	}
	else if (nums[middle] < target) {
		return binarySearch(nums, target, middle + 1, right);
	}
	else
		return binarySearch(nums, target, left, middle - 1);
	}
}

int Find(vector<int> &nums, int target) {
	int n = nums.size();
	return binarySearch(nums, target, 0, n - 1);
}

关于上述函数,描述不正确的是( )。

A
函数采用二分查找,每次计算搜索当前搜索区间的中点,然后根据中点的元素值排除一半搜索区间。
B
函数采用递归求解,每次问题的规模减小一半。
C
递归的终止条件是中间元素的值等于 target ,若数组中不包含该元素,递归不会终止。
D
算法的复杂度为 O(logn).
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
72 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

给定一个长度为 的有序数组 nums ,其中可能包含重复元素。下面的函数返回数组中某个元素 target 的左边界,若数组中不包含该元素,则返回 −1 。例如在数组 nums = [5,7,7,8,8,10] 中查找 target=8 ,函数返回 8 88 在数组中的左边界的索引为 3 33。则横线上应填写的代码为( )。

int getLeftBoundary(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	
	while (left < right) {
		int middle = left + ((right - left) / 2);
		if (target <= nums[middle])
			________________________________ // 在此处填入代码
		else
			left = middle+1;
	}
	
	return nums[left]==target?left:-1;
}
A
right = middle - 1;
B
right = middle;
C
right = middle + 1;
D
以上都不对
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
73 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

假设有多个孩子,数组 g 保存所有孩子的胃口值。有多块饼干,数组 s 保存所有饼干的尺寸。小杨给孩子们发饼干,每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩子的胃口时,孩子才能得到满足。小杨的目标是尽可能满足越多数量的孩子,因此打算采用贪心算法来找出能满足的孩子的数目,则横线上应填写的代码为( )。

int cooki4children(vector<int>& g, vector<int>& s) {
	sort(g.begin(), g.end());
	sort(s.begin(), s.end());
	
	int index = s.size() - 1; // 饼干数组下标
	int result = 0;
	for (int i = g.size() - 1; i >= 0; i--) {
		if (index >= 0 && s[index] >= g[i]) {
			________________________________ // 在此处填入代码
		}
	}
	return result;
}
A
result++; index–;
B
result–; index–;
C
result–; index++;
D
result++; index++;
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
74 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

关于分治算法,以下说法中不正确的是( )。

A
分治算法将问题分成子问题,然后分别解决子问题,最后合并结果。
B
归并排序采用了分治思想。
C
快速排序采用了分治思想。
D
冒泡排序采用了分治思想。
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
75 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 3.1 高精度加法

小杨编写了一个如下的高精度减法函数:

vector<int> highPrecisionSubtract(vector<int> a, vector<int> b) {
	vector<int> result;
	int borrow = 0;
	
	for (int i = 0; i < a.size(); ++i) {
		int digitA = a[i];
		int digitB = i < b.size() ? b[i] : 0;
		
		int diff = digitA - digitB - borrow;
		if (diff < 0) {
			diff += 10;
			borrow = 1;
		}
		else {
			borrow = 0;
		}
		result.push_back(diff);
	}
	
	while (result.size() > 1 && result.back() == 0) {
		result.pop_back();
	}
	
	return result;
}

下面说法,正确的是( )。

A
如果数组 a 表示的整数小于 b 表示的整数,代码会正确返回二者的差为负数。
B
代码假设输入数字是以倒序存储的,例如 500 存储为 {0, 0, 5} 。
C
代码的时间复杂度为 O(a.size()+b.size())
D
当减法结果为 0 时,结果数组仍然会存储很多个元素 0。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
76 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

下面关于链表和数组的描述,错误的是( )。

A
数组大小固定,链表大小可动态调整。
B
数组支持随机访问,链表只能顺序访问。
C
存储相同数目的整数,数组比链表所需的内存多。
D

数组插入和删除元素效率低,链表插入和删除元素效率高。

答案与解析
正确答案:C

存储相同数目的整数的时候,数组用的内存应该是更少的,因为数组不需要记录下一个值的地址。

题目详情
77 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

通过( )操作,能完成在双向循环链表结点 p 之后插入结点 s 的功能(其中 next 域为结点的直接后继,prev 域为结点的直接前驱)。

A
p->next->prev = s; s->prev = p; p->next = s; s->next = p->next;
B
p->next->prev = s; p->next = s; s->prev = p; s->next = p->next;
C
s->prev = p; s->next = p->next; p->next = s; p->next->prev = s;
D
s->next = p->next; p->next->prev = s; s->prev = p; p->next = s;
答案与解析
正确答案:D

A选项最后一句,此时p->next已经变成了s,所以错了

B选项最后一句,此时p->next已经变成了s,所以错了

C选项最后一句,应该是s->next->prev = s;

题目详情
78 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

对下面两个函数,说法错误的是( )。

int sumA(int n) {
	int res = 0;
	for (int i = 1; i <= n; i++) {
		res += i;
	}
	return res;
}

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


A
sumA体现了迭代的思想。
B
SumB采用的是递归方式。
C
SumB函数比SumA的时间效率更高。
D
两个函数的实现的功能相同。
答案与解析
正确答案:C

sumA函数是递推,sumB函数是递归,两个函数都是求的1~n的和,两个函数的时间复杂度基本一致,都是O(n)。

题目详情
79 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

有如下函数 fun ,则 fun(20, 12) 的返回值为( )。

int fun(int a, int b) {
	if (a % b == 0)
		return b;
	else
		return fun(b, a % b);
}


A
20
B
12
C
4
D
2
答案与解析
正确答案:C

函数为辗转相除求两数的最大公约数,结果为4,如果没有看出函数作用,也可以手动模拟递归过程。

题目详情
80 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的埃拉托斯特尼筛法,筛选出所有小于等于 n 的素数,则横线上应填的最佳代码是( )。

void sieve_Eratosthenes(int n) {
	vector<bool> is_prime(n + 1, true);
	vector<int> primes;
	
	for (int i = 2; i * i <= n; i++) {
		if (is_prime[i]) {
			primes.push_back(i);
			________________________________ { // 在此处填入代码
				is_prime[j] = false;
			}
		}
	}
	
	for (int i = sqrt(n) + 1; i <= n; i++) {
		if (is_prime[i]) {
			primes.push_back(i);
		}
	}
	
	return primes;
}


A
for (int j = i; j <= n; j++)
B
for (int j = i * i; j <= n; j++)
C
for (int j = i * i; j <= n; j += i)
D
for (int j = i; j <= n; j += i)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情