GESP C++ 5级 2025.12

对如下定义的循环单链表，横线处填写（ ）。

// 循环单链表的结点
struct Node {
 int data; // 数据域
 Node* next; // 指针域

 Node(int d) : data(d), next(nullptr) {}
};

// 创建一个只有一个结点的循环单链表
Node* createList(int value) {
 Node* head = new Node(value);
 head->next = head;
 return head;
}

// 在循环单链表尾部插入新结点
void insertTail(Node* head, int value) {
 Node* p = head;
 while (p->next != head) {
 p = p->next;
 }
 Node* node = new Node(value);
 node->next = head;
 p->next = node;
}

// 遍历并输出循环单链表
void printList(Node* head) {
 if (head == nullptr) return;

 Node* p = head;
 _______________________ //在此处填入代码 
 cout << endl;
}

区块链技术是比特币的基础。在区块链中，每个区块指向前一个区块，构成链式列表，新区块只能接在链尾，不允许在中间插入或删除。下面代码实现插入区块添加函数，则横线处填写（ ）。

//区块（节点）
struct Block {
 int index; // 区块编号（高度）
 string data; // 区块里保存的数据
 Block* prev; // 指向前一个区块

 Block(int idx, const string& d, Block* p) : index(idx), data(d), prev(p) {}
};

// 区块链
struct Blockchain {
 Block* tail;

 // 初始化
 void init() {
 tail = new Block(0, "Genesis Block", nullptr);
 }

 // 插入新区块
 void addBlock(const string& data) {
 _______________________ //在此处填入代码 
 }
 // 释放内存

 void clear() {
 Block* cur = tail;
 while (cur != nullptr) {
 Block* p = cur->prev;
 delete cur;
 cur = p;
 }
 tail = nullptr;
 }
};

下面关于单链表和双链表的描述中，正确的是（ ）。

struct DNode {
 int data;
 DNode* prev;
 DNode* next;
};

// 在双链表中删除指定节点
void deleteNode(DNode* node) {
 if (node->prev) {
 node->prev->next = node->next;
 }
 if (node->next) {
 node->next->prev = node->prev;
 }
 delete node;
}

struct SNode {
 int data;
 SNode* next;
};

// 在单链表中删除指定节点
void deleteSNode(SNode* head, SNode* node) {
 SNode* prev = head;
 while (prev->next != node) {
 prev = prev->next;
 }
 prev->next = node->next;
 delete node;
}

假设我们有两个数 $a=38$ 和 $b=14$，它们对模 $m$ 同余，即 $a \equiv b \pmod m$。以下哪个值不可能是 $m$？

下面代码实现了欧几里得算法。下面有关说法，错误的是（ ）。

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

int gcd2(int a, int b) {
 while (b != 0) {
 int temp = b;
 b = a % b;
 a = temp;
 }
 return a;
}

唯一分解定理描述的内容是（ ）。

下述代码实现素数表的线性筛法，筛选出所有小于等于 $n$ 的素数，则横线上应填的代码是( )。

vector linear_sieve(int n) {
 vector is_prime(n +1, true);
 vector primes;

 is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
 for (int i = 2; i <= n; ++i) {
 if (is_prime[i]) {
 primes.push_back(i);
 }
 ________________________________ { // 在此处填入代码 
 is_prime[ i * primes[j] ] = 0;
 if (i % primes[j] == 0)
 break;
 }
 }

 return primes;
}

下列关于排序的说法，正确的是( )。

下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ）。

void merge(vector& arr, vector& temp, int l, int mid, int r) {
 int i = l, j = mid + 1, k = l;
 while (i & arr, vector& temp, int l, int r) {
 if (l >= r) return;
 int mid = l + (r - l) / 2;
 mergeSort(arr, temp, l, mid);
 mergeSort(arr, temp, mid + 1, r);
 merge(arr, temp, l, mid, r);
}

下述 C++ 代码实现了快速排序算法，最坏情况的时间复杂度是（ ）。

int partition(vector& arr, int low, int high) {
 int i = low, j = high;
 int pivot = arr[low]; // 以首元素为基准
 while (i = pivot) j--;
 while (i & arr, int low, int high) {
 if (low >= high) return;
 int p = partition(arr, low, high);
 quickSort(arr, low, p - 1);
 quickSort(arr, p + 1, high);
}