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

// 循环单链表的结点
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;
}

假设我们有两个数x和y，它们对模m同余，即x≡y(mod 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<int> linear_sieve(int n) {
vector<bool> is_prime(n +1, true);
vector<int> 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<int>& arr, vector<int>& temp, int l, int mid, int r) {
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
for (int p = l; p <= r; p++) arr[p] = temp[p];
}
void mergeSort(vector<int>& arr, vector<int>& 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<int>& arr, int low, int high) {
int i = low, j = high;
int pivot = arr[low]; // 以首元素为基准
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
while (i < j && arr[i] <= pivot) i++;
if (i < j) swap(arr[i], arr[j]);
}
swap(arr[i], arr[low]);
return i;
}
void quickSort(vector<int>& 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);
}

下面代码尝试在有序数组中查找第一个大于等于x的元素位置。以下说法正确的是（ ）。

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

小杨要把一根长度为L的木头切成K段，使得每段长度小于等于x。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小x（x为正整数），则横线处应填写（

// 判断：在不超过 K 次切割内，是否能让每段长度 <= x
bool check(int L, int K, int x) {
int cuts = (L - 1) / x;
return cuts <= K;
}
// 二分查找最小可行的 x
int binary_cut(int L, int K) {
int l = 1, r = L;
while (l < r) {
int mid = l + (r - l) / 2;
________________________________ // 在此处填入代码
}
return l;
}
int main() {
int L = 10; // 木头长度
int K = 2; // 最多切 K 刀
cout << binary_cut(L, K) << endl;
return 0;
}

下面给出了阶乘计算的两种方式。以下说法正确的是（ ）。

给定n个任务，每个任务有截止时间和利润，每个任务耗时1个时间单位。为了在规定时间内获得最大利润，可以采用贪心策略，即按利润从高到低排序，尽量安排，则横线处应填写

struct Task {
int deadline; //截止时间
int profit; //利润
};
void sortByProfit(vector<Task>& tasks) {
sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.profit > b.profit;
});
}
int maxProfit(vector<Task>& tasks) {
sortByProfit(tasks);
int maxTime = 0;
for (auto& t : tasks) {
maxTime = max(maxTime, t.deadline);
}
vector<bool> slot(maxTime + 1, false);
int totalProfit = 0;
for (auto& task : tasks) {
for (int t = task.deadline; t >= 1; t--) {
if (!slot[t]) {
_______________________ //在此处填入代码
break;
}
}
}
return totalProfit;
}

下面代码实现了对两个数组表示的正整数的高精度加法（数组低位在前），则横线上应填写（ ）。

数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。

假设函数gcd()函数能正确求两个正整数的最大公约数，则下面的lcm(a, b)函数能正确找到两个正整数a和b的最小公倍数。

在单链表中，已知指针p指向要删除的结点（非尾结点），想在O(1)删除p，可行做法是用p->next覆盖p的值与next，然后删除p->next。

在求解所有不大于n的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为O(n)，低于埃氏筛法的O(n log log n)。

二分查找仅适用于有序数据。若输入数据无序，当仅进行一次查找时，为了使用二分而排序通常不划算。

通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴（比较基准），快速排序算法可降低落入最坏情况的概率。

贪心算法在每一步都做出当前看来最优的局部选择，并且一旦做出选择就不再回溯；而分治算法将问题分解为若干子问题分别求解，再将子问题的解合并得到原问题的解。

以下fib函数计算第n项斐波那契数（fib(0)=0, fib(1)=1），其时间复杂度为O(2^n)。

递归函数一定要有终止条件，否则可能会造成栈溢出。

使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。

数字移动

小A有一个包含n个正整数的序列A，序列A恰好包含n/2对不同的正整数。形式化地，对于任意i，存在唯一一个j满足Ai=Aj。
小A希望每对相同的数字在序列中相邻，为了实现这一目的，小A每次操作会选择任意i(i>1)，将当前序列的第i个数字移动到任意位置，并花费对应数字的体力。
小A可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小A希望你能帮他计算出一个最小的k，使得他能够在每次花费的体力均不超过k的情况下令每对相同的数字在序列中相邻。

第一行一个正整数n，代表序列长度，保证n为偶数。
第二行包含n个正整数A1,A2,...,An，代表序列A。

输出一行，代表满足要求的k的最小值。

【样例输入】

6
1 2 1 3 2 3
【样例输出】

2
对于40%的测试点，保证n<=1000。
对于所有测试点，保证2<=n<=10^5。

相等序列

小A有一个包含n个正整数的序列A。小A每次可以花费1个金币执行以下任意一种操作：
1. 选择序列中一个正整数Ai（Ai>1），将Ai变为Ai/p，p为任意质数，要求Ai能被p整除；
2. 选择序列中一个正整数Ai，将Ai变为Ai*p，p为任意质数。
小A想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。

第一行一个正整数n，含义如题面所示。
第二行包含n个正整数A1,A2,...,An，代表序列A。

输出一行，代表最少需要花费的金币数量。

【样例输入】

5
10 6 35 105 42
【样例输出】

8
对于60%的测试点，保证n<=1000。
对于所有测试点，保证1<=n<=10^5，1<=Ai<=10^5。