5347：[GESP202412五级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：1
解决：0
题目描述
**一.单选题(每题2分，共30分)**
1. 下⾯关于链表和数组的描述，错误的是（ ）。
- 当数据数量不确定时，为了应对各种可能的情况，需要申请⼀个较⼤的数组，可能浪费空间；此时⽤链表⽐ 较合适，⼤⼩可动态调整。
- 在链表中访问节点的效率较低，时间复杂度为O(n) 。
- 链表插⼊和删除元素效率较低，时间复杂度为O(n)。
- 链表的节点在内存中是分散存储的，通过指针连在⼀起。
2. 在循环单链表中，节点的next 指针指向下⼀个节点，最后⼀个节点的next 指针指向（ ）。
- 当前节点
- nullptr
- 第⼀个节点
- 上⼀个节点
3. 为了⽅便链表的增删操作，⼀些算法⽣成⼀个虚拟头节点，⽅便统⼀删除头节点和其他节点。下⾯代码实现 了删除链表中值为 val 的节点，横线上应填的最佳代码是
```cpp
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;
}
```
- `dummyHead->next = head; cur = dummyHead;`
- `dummyHead->next = head->next; cur = dummyHead;`
- `dummyHead->next = head; cur = dummyHead->next;`
- `dummyHead->next = head->next; cur = dummyHead->next;`
4. 对下⾯两个函数，说法错误的是
```cpp
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);
}
- 两个函数的实现的功能相同。
- fibA采⽤递推⽅式。
- fibB采⽤的是递归⽅式。
- fibA时间复杂度为O(n) ，fibB的时间复杂度为$O(n^2)$
5. 两块长⽅形⼟地的长宽分别为 24和 36⽶，要将它们分成正⽅形的⼩块，使得正⽅形的尺⼨尽可能⼤。⼩杨 采⽤如下的辗转相除函数 gcd(24, 36) 来求正⽅形分块的边长，则函数 gcd 调⽤顺序为（ ）。
```cpp
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);
}
- `gcd(24, 36)、gcd(24, 12)、gcd(12, 0)`
- `gcd(24, 36)、gcd(12, 24)、gcd(0, 12)`
- ` gcd(24, 36)、gcd(24, 12)`
- `gcd(24, 36)、gcd(12, 24)`
6. 唯⼀分解定理表明，每个⼤于1的⾃然数可以唯⼀地写成若⼲个质数的乘积。下⾯函数将⾃然数 的所有质因 素找出来，横线上能填写的最佳代码是 （ ）。
```cpp
#include
vector get_prime_factors(int n) {
vector 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;
}
```
- `for (int i = 3; i <= n; i ++)`
- `for (int i = 3; i * i <= n; i ++)`
- `for (int i = 3; i <= n; i += 2)`
- `for (int i = 3; i * i <= n; i += 2)`
7. 下述代码实现素数表的埃拉托⾊尼(埃⽒)筛法，筛选出所有⼩于等于n的素数 （ ）。
```cpp
vector sieve_Eratosthenes(int n) {
vector is_prime(n +1, true);
vector 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;
}
- 代码的时间复杂度是$O(n\sqrt{n})$
- 在标记⾮素数时，代码从$i^2$开始，可以减少重复标记。
- 代码会输出所有⼩于等于 n的奇数。
- 调⽤函数sieve_Eratosthenes(10)，函数返回值的数组中包含的元素有：2, 3, 5, 7, 9。
8. 下述代码实现素数表的线性筛法，筛选出所有⼩于等于n的素数。下⾯说法正确的是（ ）。
```cpp
vector sieve_linear(int n) {
vector is_prime(n +1, true);
vector 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;
}
```
- 线性筛的时间复杂度是$O(n)$。
- 每个合数会被其所有的质因⼦标记⼀次。
- 线性筛和埃拉托⾊尼筛的实现思路完全相同。
- 以上都不对
9. 考虑以下C++代码实现的快速排序算法：
```cpp
int partition(vector& 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& arr, int left, int right) {
if (left < right) {
int pi = partition(arr, left, right);
quickSort(arr, left, pi - 1);
quickSort(arr, pi + 1, right);
}
}
```
以下关于快速排序的说法，正确的是（ ）。
- 快速排序通过递归对⼦问题进⾏求解。
- 快速排序的最坏时间复杂度是$O(nlogn)$ 。
- 快速排序是⼀个稳定的排序算法
- 在最优情况下，快速排序的时间复杂度是O(n)
10. 下⾯关于归并排序，描述正确的是（ ）。
- 归并排序是⼀个不稳定的排序算法。
- 归并排序的时间复杂度在最优、最差和平均情况下都是$O(nlogn)$
- 归并排序需要额外的O(1)的空间
- 对于输⼊数组 {12, 11, 13, 5, 6, 7}，代码输出结果为：7 6 5 13 12 11。
11. 给定⼀个长度为的有序数组nums，其中所有元素都是唯⼀的。下⾯的函数返回数组中元素target的索 引。
```cpp
int binarySearch(vector &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 &nums, int target) {
int n = nums.size();
return binarySearch(nums, target, 0, n - 1);
}
关于上述函数，描述不正确的是（ ）。
- 函数采⽤⼆分查找，每次计算搜索当前搜索区间的中点，然后根据中点的元素值排除⼀半搜索区间。
- 函数采⽤递归求解，每次问题的规模减⼩⼀半。
- 递归的终⽌条件是中间元素的值等于target ，若数组中不包含该元素，递归不会终⽌。
- 算法的复杂度为O(logn)
12. 给定⼀个长度为 的有序数组 nums ，其中可能包含重复元素。下⾯的函数返回数组中某个元素target左边界，若数组中不包含该元素，则返回−1。例如在数组 target 的 nums = [5,7,7,8,8,10] 中查找 target=8 ，函数返回8在数组中的左边界的索引为3。则横线上应填写的代码为（ ）。
```cpp
int getLeftBoundary(vector& 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;
}
```
- `right = middle - 1;`
- `right = middle;`
- `right = middle + 1;`
- 以上都不对
13. 假设有多个孩⼦，数组 g 保存所有孩⼦的胃⼝值。有多块饼⼲，数组s保存所有饼⼲的尺⼨。⼩杨给孩⼦ 们发饼⼲，每个孩⼦最多只能给⼀块饼⼲。饼⼲的尺⼨⼤于等于孩⼦的胃⼝时，孩⼦才能得到满⾜。⼩杨的⽬标是 尽可能满⾜越多数量的孩⼦，因此打算采⽤贪⼼算法来找出能满⾜的孩⼦的数⽬，则横线上应填写的代码为（ ）。
```cpp
int cooki4children(vector& g, vector& 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;
}
```
- `result++; index--;`
- `result--; index--;`
- ` result--; index++;`
- `result++; index++;`
14. 关于分治算法，以下说法中不正确的是
- 分治算法将问题分成⼦问题，然后分别解决⼦问题，最后合并结果。
- 归并排序采⽤了分治思想。
- 快速排序采⽤了分治思想。
- 冒泡排序采⽤了分治思想。
15. ⼩杨编写了⼀个如下的⾼精度减法函数：
```cpp
vector highPrecisionSubtract(vector a, vector b) {
vector 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表⽰的整数⼩于b表⽰的整数，代码会正确返回⼆者的差为负数。
- 代码假设输⼊数字是以倒序存储的，例如 500存储为{0, 0, 5} 。
- 代码的时间复杂度为`O(a.size()+b.size())`
- 当减法结果为0时，结果数组仍然会存储很多个元素0。
**二.判断题(每题2分，共20分)**
16. 单链表只⽀持在表头进⾏插⼊和删除操作。
- 正确
- 错误
17. 线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最⼩质因数筛去⼀次，因此效率更⾼。
- 正确
- 错误
18. 任何⼀个⼤于1的⾃然数都可以分解成若⼲个不同的质数的乘积，且分解⽅式是唯⼀的。
- 正确
- 错误
19. 贪⼼算法通过每⼀步选择当前最优解，从⽽⼀定能获得全局最优解。
- 正确
- 错误
20. 递归算法必须有⼀个明确的结束条件，否则会导致⽆限递归并可能引发栈溢出。
- 正确
- 错误
21. 快速排序和归并排序的平均时间复杂度均为，且都是稳定排序。
- 正确
- 错误
22. 快速排序的时间复杂度总⽐插⼊排序的时间复杂度低。
- 正确
- 错误
23. ⼆分查找仅适⽤于数组⽽不适合链表，因为⼆分查找需要跳跃式访问元素，链表中执⾏跳跃式访问的效率 低。
- 正确
- 错误
24. 对有序数组 {5,13,19,21,37,56,64,75,88,92,100} 进⾏⼆分查找，成功查找元素 19 的⽐较次数是2。
- 正确
- 错误
25. 递归函数每次调⽤⾃⾝时，系统都会为新开启的函数分配内存，以存储局部变量、调⽤地址和其他信息 等，导致递归通常⽐迭代更加耗费内存空间。
- 正确
- 错误