2024年3月CCF-GESP编程能力等级认证C++编程五级真题

唯一分解定理描述的内容是（ ）？

贪心算法的核心思想是（ ）？

下面的 C 代码片段用于计算阶乘。请在横线处填入（ ），实现正确的阶乘计算。

int factorial(int n) {\tif (n == 0 || n == 1) {\t\treturn 1;\t} else {\t\t_________________________________ // 在此处填入代码\t}}

下面的代码片段用于在双向链表中删除一个节点。请在横线处填入（ ），使其能正确实现相应功能。

void deleteNode(DoublyListNode*& head, int value) {\tDoublyListNode* current = head;\twhile (current != nullptr && current->val != value) {\t\tcurrent = current->next;\t}\tif (current != nullptr) {\t\tif (current->prev != nullptr) {\t\t\t____________________________________ // 在此处填入代码\t\t} else {\t\t\thead = current->next;\t\t}\t\tif (current->next != nullptr) {\t\t\tcurrent->next->prev = current->prev;\t\t}\t\tdelete current;\t}}

辗转相除法也被称为（ ）

下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是（ ）？

int fibonacci(int n) {\tif (n <= 1) {\t\treturn n;\t} else {\t\treturn fibonacci(n - 1)   fibonacci(n - 2);\t}}

下面的代码片段用于将两个高精度整数进行相加。请在横线处填入（ ），使其能正确实现相应功能。

string add(string num1, string num2) {\tstring result;\tint carry = 0;\tint i = num1.size() - 1, j = num2.size() - 1;\twhile (i >= 0 || j >= 0 || carry) {\t\tint x = (i >= 0) ? num1[i--] - '0' : 0;\t\tint y = (j >= 0) ? num2[j--] - '0' : 0;\t\tint sum = x   y   carry;\t\tcarry = sum / 10;\t\t_______________________________________\t}\treturn result;}

给定序列：1，3，6，9，17，31，39，52，61，79，81，90，96。使用以下代码进行二分查找查找元素 82时，需要循环多少次，即最后输出的 times 值为（ ）。

int binarySearch(const std::vector& arr, int target) {\tint left = 0;\tint right = arr.size() - 1;\tint times = 0;\twhile (left <= right) {\t\ttimes   ;\t\tint mid = left   (right - left) / 2;\t\tif (arr[mid] == target) {\t\t\tcout << times << endl;\t\t\treturn mid;\t\t} else if (arr[mid] < target) {\t\t\tleft = mid   1;\t\t} else {\t\t\tright = mid - 1;\t\t}\t}\tcout << times << endl;\treturn -1;}

下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改，使其能正确实现相应功能。（ ）

bool isPrime(int num) {\tif (num < 2) {\t\treturn false;\t}\tfor (int i = 2; i * i < num;   i) {\t\tif (num % i == 0) {\t\t\treturn false;\t\t}\t}\treturn true;}

在埃拉托斯特尼筛法中，要筛选出不大于 n 的所有素数，最外层循环应该遍历什么范围（ ）？

vector sieveOfEratosthenes(int n) {\tstd::vector isPrime(n   1, true);\tstd::vector primes;\t_______________________ {\t\tif (isPrime[i]) {\t\t\tprimes.push_back(i);\t\t\tfor (int j = i * i; j <= n; j  = i) {\t\t\t\tisPrime[j] = false;\t\t\t}\t\t}\t}\tfor (int i = sqrt(n)   1; i <= n;   i) {\t\tif (isPrime[i]) {\t\t\tprimes.push_back(i);\t\t}\t}\treturn primes;}

素数的线性筛法时间复杂度为（ ）。

归并排序的基本思想是（ ）。

在快速排序中，选择的主元素（pivot）会影响算法的（ ）。

递归函数在调用自身时，必须满足（ ），以避免无限递归？

假设给定链表为: ，若调用 searchValue(head, 5) ，函数返回值为（ ）。

int searchValue(ListNode* head, int target) {\twhile (head != nullptr) {\t\tif (head->val == target) {\t\t\treturn 1;\t\t}\t\thead = head->next;\t}\treturn 0;}

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

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

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

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

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

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

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

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

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

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

成绩排序

问题描述

有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

6140 140 150140 149 140148 141 140141 148 140145 145 1390 0 0

样例输出 1

134426

数据规模

对于30的测试点，保证N≤100，且所有同学的总分各不相同。

对于所有测试点，保证2≤N≤10⁴。

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≤10⁶，1≤B≤10⁶。