GESP C++ 5级 2025.06
与数组相比，链表在（ ）操作上通常具有更高的效率。
随机访问元素
查找指定元素
在已知位置插入或删除节点
遍历所有元素
下面 C++ 代码实现双向链表。函数 is_empty() 判断链表是否为空，如链表为空返回 true，否则返回 false。横线处不能填写（ ）。
// 节点结构体
struct Node {
int data;
Node* prev;
Node* next;
};
// 双向链表结构体
struct DoubleLink {
Node* head;
Node* tail;
int size;
DoubleLink() {
head = nullptr;
tail = nullptr;
size = 0;
}
~DoubleLink() {
Node* curr = head;
while (curr) {
Node* next = curr->next;
delete curr;
curr = next;
}
}
// 判断链表是否为空
bool is_empty() const {
______________// 横线处代码
}
};
return head == nullptr;
return tail == nullptr;
return head.data == 0;
return size == 0;
基于上题代码正确的前提下，填入相应代码完善 append()，用于在双向链表尾部增加新节点，横线上应填写（ ）。
void append(int data) {
Node* newNode = new Node{data, nullptr, nullptr};
if (is_empty()) {
head = tail = newNode;
} else {
____________
}
++size;
}
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
tail = newNode;
newNode->prev = tail;
tail->next = newNode;
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
下列 C++ 代码用循环链表解决约瑟夫问题，即假设 个人围成一圈，从第一个人开始数，每次数到第 个人就出圈，输出最后留下的那个人的编号。横线上应填写（ ）。
struct Node {
int data;
Node* next;
};
Node* createCircularList(int n) {
Node* head = new Node{1, nullptr};
Node* prev = head;
for (int i = 2; i next = node;
prev = node;
}
prev->next = head;
return head;
}
int findLastSurvival(int n, int k) {
Node* head = createCircularList(n);
Node* p = head;
Node* prev = nullptr;
while (p->next != p) {
for (int count = 1; count next;
}
________________// 横线处代码
}
cout data << endl;
delete p;
return 0;
}
prev->next = p->next;
delete p;
p = prev->next;
delete p;
prev->next = p->next;
p = prev->next;
delete p;
p = prev->next;
prev->next = p->next;
prev->next = p->next;
p = prev->next;
delete p;
下列 C++ 代码判断一个正整数是否是质数，说法正确的是（ ）。
bool is_prime(int n) {
if (n <= 1) return false;
if (n == 2 || n == 3 || n == 5)
return true;
if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0)
return false;
int i = 7;
int step = 4;
int finish_number = sqrt(n) + 1;
while (i <= finish_number) {
if (n % i == 0)
return false;
i += step;
step = 6 - step;
}
return true;
}
代码存在错误，比如 是质数，但因为 余数是 返回了 false
finish_number 的值应该是 ，当前写法将导致错误
当前 while 循环正确的前提是：所有大于 的质数都符合 形式
while 循环修改如下，其执行效果和执行时间相同。
for (int i = 2; i < finish_number; i++) {
if (n % i == 0)
return false;
}
return true;
下列 C++ 代码用两种方式求解两个正整数的最大公约数，说法错误的是（ ）。
int gcd0(int big, int small) {
if (big = 1; --i) {
if (big % i == 0 && small % i == 0)
return i;
}
return 1;
}
gcd0() 函数的时间复杂度为
gcd1() 函数的时间复杂度为
一般说来，gcd0() 的效率高于 gcd1()
gcd1() 中的代码 for (int i = small; i >= 1; --i) 应该修改为 for (int i = small; i > 1; --i)
下面的代码用于判断整数 是否是质数，错误的说法是（ ）。
bool is_prime(int n) {
if (n (sqrt(n)) + 1;
for (int i = 2; i < finish_number; ++i) {
if (n % i == 0)
return false;
}
return true;
}
埃氏筛算法相对于上面的代码效率更高
线性筛算法相对于上面的代码效率更高
上面的代码有很多重复计算，因为不是判断单个数是否为质数，故而导致筛选出连续数中质数的效率不高
相对而言，埃氏筛算法比上面代码以及线性筛算法效率都高
唯一分解定理描述了关于正整数的什么性质？
任何正整数都可以表示为两个素数的和
任何大于 的合数都可以唯一分解为有限个质数的乘积
两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积
所有素数都是奇数
下面的 C++ 代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。
int find_max_recursive(const vector& nums, int left, int right) {
if (left == right)
return nums[left];
int mid = left + (right - left) / 2;
int left_max = find_max_recursive(nums, left, mid);
int right_max = find_max_recursive(nums, mid + 1, right);
return max(left_max, right_max);
}
int find_max(const vector& nums) {
if (nums.empty()) {
throw invalid_argument("输入数组不能为空");
}
return find_max_recursive(nums, 0, nums.size() - 1);
}
该算法采用分治算法
该算法是递归实现
该算法采用贪心算法
该算法不是递推算法
下面的 C++ 代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。
int find_max(const vector& nums) {
if (nums.empty()) {
throw invalid_argument("输入数组不能为空");
}
int max_value = nums[0];
for (int num : nums) {
if (num > max_value) {
max_value = num;
}
}
return max_value;
}
本题 find_max() 函数采用的是迭代算法
本题 find_max() 函数的时间复杂度为
和上一题的 find_max() 相比，因为没有递归，所以没有栈的创建和销毁开销
本题 find_max() 函数和上一题的 find_max() 时间复杂度相同