一、单选题
1、唯一分解定理描述的内容是（ ）？
A 任意整数都可以分解为素数的乘积
B 每个合数都可以唯一分解为一系列素数的乘积
C 两个不同的整数可以分解为相同的素数乘积
D 以上都不对
2、贪心算法的核心思想是（ ）？
A 在每一步选择中都做当前状态下的最优选择
B 在每一步选择中都选择局部最优解
C 在每一步选择中都选择全局最优解
D 以上都对
3、下面的 C++ 代码片段用于计算阶乘。请在横线处填入（ ），实现正确的阶乘计算。
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
_________________________________ // 在此处填入代码
}
}A return n * factorial(n - 1);
B return factorial(n - 1) / n;
C return n * factorial(n);
D return factorial(n / 2) * factorial(n / 2);
4、下面的代码片段用于在双向链表中删除一个节点。请在横线处填入（ ），使其能正确实现相应功能。
void deleteNode(DoublyListNode*& head, int value) {
DoublyListNode* current = head;
while (current != nullptr && current->val != value) {
current = current->next;
}
if (current != nullptr) {
if (current->prev != nullptr) {
____________________________________ // 在此处填入代码
} else {
head = current->next;
}
if (current->next != nullptr) {
current->next->prev = current->prev;
}
delete current;
}
}A if (current->next != nullptr) current->next->prev = current->prev;
B current->prev->next = current->next;
C delete current->next;
D current->prev = current->next;
5、辗转相除法也被称为（ ）
A 高斯消元法
B 费马定理
C 欧几里德算法
D 牛顿迭代法
6、下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是（ ）？
int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}A O(1)
B O(n)
C O(2n)
D O(logn)
7、下面的代码片段用于将两个高精度整数进行相加。请在横线处填入（ ），使其能正确实现相应功能。
string add(string num1, string num2) {
string result;
int carry = 0;
int i = num1.size() - 1, j = num2.size() - 1;
while (i >= 0 || j >= 0 || carry) {
int x = (i >= 0) ? num1[i--] - '0' : 0;
int y = (j >= 0) ? num2[j--] - '0' : 0;
int sum = x + y + carry;
carry = sum / 10;
_______________________________________
}
return result;
}A result = to_string(sum % 10) + result;
B result = to_string(carry % 10) + result;
C result = to_string(sum / 10) + result;
D result = to_string(sum % 10 + carry) + result;
8、给定序列：1，3，6，9，17，31，39，52，61，79，81，90，96。使用以下代码进行二分查找查找元素 82时，需要循环多少次，即最后输出的 times 值为（ ）。
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
int times = 0;
while (left <= right) {
times ++;
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
cout << times << endl;
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << times << endl;
return -1;
}A 2
B 5
C 3
D 4
9、下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改，使其能正确实现相应功能。（ ）
bool isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i * i < num; ++i) {
if (num % i == 0) {
return false;
}
}
return true;
}A num < 2 应该改为 num <= 2
B 循环条件 i * i < num 应该改为 i * i <= num
C 循环条件应该是 i <= num
D 循环体中应该是 if (num % i != 0)
10、在埃拉托斯特尼筛法中，要筛选出不大于 n 的所有素数，最外层循环应该遍历什么范围（ ）？
vector<int> sieveOfEratosthenes(int n) {
std::vector<bool> isPrime(n + 1, true);
std::vector<int> primes;
_______________________ {
if (isPrime[i]) {
primes.push_back(i);
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
for (int i = sqrt(n) + 1; i <= n; ++i) {
if (isPrime[i]) {
primes.push_back(i);
}
}
return primes;
}A for (int i = 2; i <= n; ++i)
B for (int i = 1; i < n; ++i)
C for (int i = 2; i <= sqrt(n); ++i)
D for (int i = 1; i <= sqrt(n); ++i)
11、素数的线性筛法时间复杂度为（ ）。
A O(n)
B O(nloglogn)
C O(nlogn)
D O(n2)
12、归并排序的基本思想是（ ）。
A 动态规划
B 分治
C 贪心算法
D 回溯算法
13、在快速排序中，选择的主元素（pivot）会影响算法的（ ）。
A 不影响
B 时间复杂度
C 空间复杂度
D 时间复杂度和空间复杂度
14、递归函数在调用自身时，必须满足（ ），以避免无限递归？
A 有终止条件
B 函数参数递减（或递增）
C 函数返回值固定
D 以上都对
15、假设给定链表为: ，若调用 searchValue(head, 5) ，函数返回值为（ ）。
int searchValue(ListNode* head, int target) {
while (head != nullptr) {
if (head->val == target) {
return 1;
}
head = head->next;
}
return 0;
}A 返回 1
B 返回 0
C 死循环，无法返回
D 返回 -1
二、判断题
16、辗转相除法用于求两个整数的最大公约数。( )
A 正确
B 错误
17、插入排序的时间复杂度是O(NlogN)。( )
A 正确
B 错误
18、二分查找要求被搜索的序列是有序的，否则无法保证正确性。( )
A 正确
B 错误
19、使用贪心算法解决问题时，每一步的局部最优解一定会导致全局最优解。( )
A 正确
B 错误
20、分治算法的核心思想是将一个大问题分解成多个相同或相似的子问题进行解决，最后合并得到原问题的解。( )
A 正确
B 错误
21、分治算法的典型应用之一是归并排序，其时间复杂度为O(NlogN)。( )
A 正确
B 错误
22、素数表的埃氏筛法和线性筛法的时间复杂度都是O(NloglogN)。( )
A 正确
B 错误
23、贪心算法是一种可以应用于所有问题的通用解决方案。( )
A 正确
B 错误
24、单链表和双链表都可以在常数时间内实现在链表头部插入或删除节点的操作。( )
A 正确
B 错误
25、在C语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。( )
A 正确
B 错误
三、实操题
26、成绩排序
问题描述
有N名同学，每名同学有语文、数学、英语三科成绩。你需要按如下规则对所有同学的成绩从高到低排序：
1. 比较总分，高者靠前；
2. 如果总分相同，则比较语文和数学两科总分，高者靠前；
3. 如果仍相同，则比较语文和数学两科的最高分，高者靠前；
4. 如果仍相同，则二人并列。
你需要输出每位同学的排名，如遇x人并列，则他们排名相同，并留空后面的x-1个名次。例如，有3名同学并列第1，则后一名同学自动成为第4名。
输入描述
第一行一个整数N，表示同学的人数。
接下来N行，每行三个非负整数ci,mi,ei分别表示该名同学的语文、数学、英语成绩。
保证0≤ci,mi,ei≤150。
输出描述
输出N行，按输入同学的顺序，输出他们的排名。
注意：请不要按排名输出同学的序号，而是按同学的顺序输出他们各自的排名
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任
何提示信息。
样例输入 1
6 140 140 150 140 149 140 148 141 140 141 148 140 145 145 139 0 0 0
样例输出 1
1 3 4 4 2 6
数据规模
对于30的测试点，保证N≤100，且所有同学的总分各不相同。
对于所有测试点，保证2≤N≤104。
参考答案：对于输入的每名同学，我们按照题目中给出的规则进行比较，然后确定他们的排名。1. 首先，我们计算每名同学的总分。2. 如果总分相同，则比较语文和数学两科总分。3. 如果语文和数学两科总分仍然相同，则比较语文和数学两科的最高分。4. 如果仍然相同，则他们并列。按照以上规则，我们可以得出每位同学的排名。
27、B-smooth 数
题面描述
小杨同学想寻找一种名为B-smooth 数的正整数。
如果一个正整数的最大质因子不超过B，则该正整数为B-smooth 数。
小杨同学想知道，对于给定的n和B，有多少个不超过n的B-smooth 数。
输入格式
第一行包含两个正整数n,B，含义如题面所示。
输出格式
输出一个非负整数，表示不超过n的B-smooth 数的数量。
样例输入
10 3
样例输出
7
样例解释
在不超过10的正整数中，3-smooth 数有{1,2,3,4,6,8,9}，共7个。
数据范围
对于全部数据，保证有1≤n≤106，1≤B≤106。
参考答案：对于每个正整数x，我们需要找到它的最大质因子。如果最大质因子不超过B，则x是一个B-smooth数。我们可以通过遍历从1到n的所有整数，并检查它们的最大质因子是否不超过B来找到所有的B-smooth数。然而，这种方法的时间复杂度为O(n*sqrt(n))，对于n=10^6的情况，这种方法是不可接受的。我们可以使用更高效的算法来解决这个问题。我们可以使用筛法来预处理出每个数的最大质因子。具体地，我们可以从2开始，对于每个数i，如果i是质数，则它的最大质因子就是它本身。否则，我们可以找到i的最小质因子p，并将i的所有倍数（除了i本身）的最大质因子都设为p。这样，我们就可以在O(n*log(log(n)))的时间复杂度内预处理出每个数的最大质因子。然后，我们可以遍历从1到n的所有数，并检查它们的最大质因子是否不超过B。对于每个数，如果它的最大质因子不超过B，则它是一个B-smooth数。我们可以使用一个计数器来记录B-smooth数的数量。最终，我们可以输出计数器的值作为答案。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
