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;
}
2分
登录后查看选项
06
唯一分解定理描述的内容是（ ）。
2分
登录后查看选项
07
下述代码实现素数表的线性筛法，筛选出所有小于等于 的素数，则横线上应填的代码是( )。
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;
}
2分
登录后查看选项
08
下列关于排序的说法，正确的是( )。
2分
登录后查看选项
09
下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ）。
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);
}
2分
登录后查看选项
10
下述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);
}
2分
登录后查看选项
11
下面代码尝试在有序数组中查找第一个大于等于 x 的元素位置。如果没有大于等于 x 的元素，返回arr.size() 。以下说法正确的是（ ）。
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;
}
2分
登录后查看选项
12
小杨要把一根长度为 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;
}
2分
登录后查看选项
13
下面给出了阶乘计算的两种方式。以下说法正确的是（ ）。
int factorial1(int n) {
if (n <= 1) return 1;
return n * factorial1(n - 1);
}
int factorial2(int n) {
int acc = 1;
while (n > 1) {
acc = n * acc;
n = n - 1;
}
return acc;
}
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;
}
2分
登录后查看选项
15
下面代码实现了对两个数组表示的正整数的高精度加法（数组低位在前），则横线上应填写（ ）。
vector<int> add(vector<int> a, vector<int> b) {
vector<int> c;
int carry = 0;
for (int i = 0; i < a.size() || i < b.size(); i++) {
if (i < a.size()) carry += a[i];
if (i < b.size()) carry += b[i];
_______________________ //在此处填入代码
}
if (carry) c.push_back(carry);
return c;
}
2分
登录后查看选项
判断题 共10道
16
数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。
2分
登录后查看选项
17
假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm(a，b) 函数能正确找到两个正整数 a 和 b 的最小公倍数。
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
2分
登录后查看选项
18
在单链表中，已知指针 p 指向要删除的结点（非尾结点），想在 删除 p ，可行做法是用 p->next 覆盖 p 的值与 next ，然后删除 p->next 。
2分
登录后查看选项
19
在求解所有不大于 n 的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为 O(n)，低于埃氏筛法的 O(n log log n)。