CCF编程能力等级认证GESP—C++5级—20240316

单选题（每题 2 分，共 30 分）

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{
        }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(2^n)$
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(inti=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(n^2)$

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

判断题（每题 2 分，共 20 分）

1、辗转相除法用于求两个整数的最大公约数。

2、插入排序的时间复杂度是O(NlogN) 。

3、二分查找要求被搜索的序列是有序的，否则无法保证正确性。

4、使用贪心算法解决问题时，每一步的局部最优解一定会导致全局最优解。

5、分治算法的核心思想是将一个大问题分解成多个相同或相似的子问题进行解决，最后合并得到原问题的解。

6、分治算法的典型应用之一是归并排序，其时间复杂度为O(NlogN) 。

7、素数表的埃氏筛法和线性筛法的时间复杂度都是O(NloglogN) 。

8、贪心算法是一种可以应用于所有问题的通用解决方案。

9、单链表和双链表都可以在常数时间内实现在链表头部插入或删除节点的操作。

10、在C语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。

编程题 (每题 25 分，共 50 分)

成绩排序

【问题描述】
有 N 名同学，每名同学有语文、数学、英语三科成绩。你需要按如下规则对所有同学的成绩从高到低排序:
1.比较总分，高者靠前;
2.如果总分相同，则比较语文和数学两科总分，高者靠前;
3.如果仍相同，则比较语文和数学两科的最高分，高者靠前;
4.如果仍相同，则二人并列。
你需要输出每位同学的排名，如遇 x人并列，则他们排名相同，并留空后面的x - 1 个名次。例如，有 3名同学并列第1 ，则后一名同学自动成为第4 名。

【输入描述】
第一行一个整数N，表示同学的人数。
接下来N行，每行三个非负整数$c_i,m_i,e_i$分别表示该名同学的语文、数学、英语成绩。
保证$0<=c_i,m_i,e_i<=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<=10^4$

B-smooth 数

【问题描述】
小杨同学想寻找一种名为 B-smooth 数的正整数。
如果一个正整数的最大质因子不超过B ，则该正整数为B-smooth 数。
小杨同学想知道，对于给定的 n和B ，有多少个不超过n的B-smooth 数。
【输入描述】
第一行包含两个正整数n，B ，含义如题面所示。
【输出描述】
输出一个非负整数，表示不超过n的B-smooth 数的数量。
【样例输入 1】
10 3
【样例输出 1】
7
【样例解释】
在不超过10的正整数中，3-smooth数有{1, 2, 3, 4, 6, 8, 9}，共7个。
【数据范围】

对于全部数据，保证有$1<=n<=10^6,1<=B<=10^6$。

参考答案

单选题

判断题

编程题1

编程题2