Today, we bring you an analysis of the C++ Level 5 certification exam paper from December 2023.
The CCF Programming Ability Level Certification, known in English as the Grade Examination of Software Programming (hereinafter referred to as GESP), is initiated and hosted by the China Computer Federation (CCF). It provides a platform for academic ability verification for young learners in computer science and programming. GESP covers all grades of primary and secondary schools, and eligible young people can participate in the certification. The aim of GESP is to enhance the level of computer and programming education for young people, promoting and popularizing computer and programming education.
GESP assesses programming in graphical (Scratch) programming, Python programming, and C++ programming, mainly examining students’ mastery of relevant programming knowledge and operational ability, familiarity with basic programming knowledge and theoretical frameworks. By setting different levels of exam objectives, it enables students to develop programming capabilities from simple programs to complex program designs, laying a good foundation for future specialized programming studies.
This time we present the analysis of the C++ Level 5 certification exam paper from December 2023.
1. Multiple Choice Questions (2 points each, total 30 points)
1. The following C++ code is used to calculate the Fibonacci sequence, where the first two items are 1, and subsequent items are the sum of the previous two. Which of the following statements is incorrect ( )?
A. fiboA( ) uses recursion, while fiboB() uses iteration.
B. fiboA( ) is more in line with the mathematical definition of the Fibonacci sequence, intuitive and easy to understand, while fiboB() needs to convert the mathematical definition into a computer program.
C. fiboA( ) is not only more in line with the mathematical definition, intuitive and easy to understand, but also has higher execution efficiency due to less code.
D. fiboB( ) has more code, but its execution efficiency is higher.
[Answer] C
[Knowledge Points] Algorithm Knowledge Points
[Analysis] fiboA is easy to understand, but its execution efficiency is not high, as some calculations are repeated, leading to low efficiency.
2. The following C++ code implements merge sort recursively, assuming that the merge (int T[], int R[], int s, int m, int t) function merges the ordered (with the same sorting rule) T[s..m] and T[m+1..t] into R[s..t]. The code that should be filled in the blank is ( ).
A. mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m,t,len)
B. mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m+1,t,len)
C. mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m+1,t,len)
D. mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m-1,t,len)
[Answer] C
[Knowledge Points] Algorithm Knowledge Points
[Analysis] This question examines merge sort. Merge sort requires first splitting the sorted sequence into two, where the left element’s interval is [s,m] and the right element’s interval is [m+1,t]. Then, after recursively sorting the two subsequences, the ordered subsequences are merged.
3. Read the following C++ code; after execution, its output is ( ).
A. 1->120<===>2->120
B. 1->120<===>1->120
C. 1->120<===>1->2->3->4->5->120
D. 1->120<===>2->3->4->5->6->120
[Answer] D
[Knowledge Points] Algorithm Knowledge Points
[Analysis] This question examines the recursive algorithm. The output of the fracA function first outputs 1, then outputs the factorial of 5, which is 120; on line 23, the fracB function is executed, where stepCount starts counting from 2, outputting 2/3/4/5/6, followed by the output of 5’s factorial, 120.
4. The following C++ code is used to sort lstA such that even numbers come first and odd numbers come last. The code to be filled in the blank is ( ).
A. isEven(lstA[j]) && !isEven(lstA[j+1])
B. !isEven(lstA[j]) && isEven(lstA[j+1])
C. lstA[j] > lstA[j+1]
D. lstA[j] < lstA[j+1]
[Answer] A
[Knowledge Points] Sorting Algorithm Knowledge Points
[Analysis] This question examines sorting algorithms. The previous number, the number at index j, is even, and the following number at index j+1 is odd. According to the requirement, even numbers should be placed after odd numbers, so they need to be swapped. A meets the conditions of the question.
5. The following C++ code is used to store strings in a doubly linked list with a head node, counting duplicates, and placing the latest accessed string’s node at the head for easy retrieval. The code to be filled in the blank is ( ).
A. if(pHead) {p->next = pHead->next, pHead->next->prev = p;}
B. if(pHead->next) {p->next = pHead->next, pHead->next->prev = p;}
C. p->next = pHead->next, pHead->next->prev = p;
D. An exception is triggered; operations cannot be performed on a null pointer.
[Answer] B
[Knowledge Points] Pointer Knowledge Points
[Analysis] This question examines the knowledge points of doubly linked lists. Each node requires two pointers, pointing to the previous node and the next node. According to the requirement, the new node needs to be inserted at the head of the list. Both the head node and the newly inserted node need to be modified. Option B can complete the insertion of the new node.
6. Which of the following statements about the following C++ code is correct ( ).
A. If x is less than 10, rc will not exceed 20.
B. foo may recurse infinitely.
C. foo can find the greatest common prime factor of x and y.
D. foo can find the least common multiple of x and y.
[Answer] A
[Knowledge Points] Mathematical Knowledge Points
[Analysis] This question examines mathematical algorithms for finding the greatest common divisor. This is a typical variant of the greatest common divisor writing. Excluding options, A is correct.
7. The following C++ code implements quick sort for a list, and which statement is incorrect ( ).
A. qSort(less) + qSort(greater) + (vector<int>)pivot
B. (vector<int>)pivot + (qSort(less) + qSort(greater))
C. (qSort(less) + (vector<int>)pivot + qSort(greater))
D. qSort(less) + pivot + qSort(greater)
[Answer] C
[Knowledge Points] Sorting Algorithm Knowledge Points
[Analysis] This question examines quick sort. The less array stores elements less than or equal to pivot, then adds the pivot element, and then adds the array greater than or equal to pivot.
8. The following C++ code is used to determine whether parameter N is prime, and the correct statement about its time complexity is ( ).
[Answer] B
[Knowledge Points] Mathematical Knowledge Points
[Analysis] This question examines mathematical knowledge for determining prime numbers. The time complexity of function A is O(n/2), while function B’s algorithm is O(sqrt(n)), making the latter more efficient in most cases.
9. The following C++ code is used for binary search on an ordered list, and which statement is incorrect ( ).
A. The code implements binary search on an ordered list.
B. The code implements divide-and-conquer algorithm for searching an ordered list.
C. The code implements recursive method to search an ordered list.
D. The code implements dynamic programming algorithm for searching an ordered list.
[Answer] D
[Knowledge Points] Algorithm Knowledge Points
[Analysis] This question examines algorithm knowledge points. The binary method reduces the scale by half each time, with an average time complexity of B for searching.
10. In the above _binarySearch algorithm, if there are N elements in the list, its time complexity is ( ).
A. O(N)
B. O(logN)
C. O(NlogN)
D. O(N²)
[Answer] B
[Knowledge Points] Algorithm Knowledge Points
[Analysis] This question examines algorithm knowledge points. The binary method reduces the scale by half each time, with an average time complexity of B for word searching.
11. The following C++ code simulates integer addition using arrays, capable of handling addition operations that exceed the range of large integers. The code to be filled in the blank is ( ) .
A. c.push_back(t % 10), t = t % 10;
B. c.push_back(t / 10), t = t % 10;
C. c.push_back(t / 10), t = t / 10;
D. c.push_back(t % 10), t = t / 10;
[Answer] D
[Knowledge Points] Algorithm Knowledge Points
[Analysis] This question examines knowledge points on high precision. Each time the lowest bit digit of the sum is saved, the lowest bit digit is removed while maintaining the carry, and the process is repeated.
12. Which of the following statements about the following C++ code is correct ( ).
A. The above code forms a singly linked list.
B. The above code forms a doubly linked list.
C. The above code forms a circular linked list.
D. The above code forms a pointer linked list.
[Answer] B
[Knowledge Points] Linked List Knowledge Points
[Analysis] This question examines linked list knowledge points. Each node points to its previous node and next node, thus it is a doubly linked list.
13. Communication satellites mainly play a role in the communication network system of ( ).
A. Information filtering
B. Signal relay
C. Avoiding attacks
D. Data encryption
[Answer] B
[Knowledge Points] Basic Computer Knowledge
[Analysis] This question examines basic computer knowledge. Communication satellites can forward radio signals, achieving wireless communication between ground stations or between ground stations and spacecraft, thus serving as a signal relay. Select B.
14. Xiao Yang wants to write a program to determine whether any input integer N is a prime number. Which method is inappropriate? ( )
A. Sieve of Eratosthenes
B. Linear Sieve Method
C. Binary Answer
D. Enumeration Method
[Answer] C
[Knowledge Points] Mathematical Knowledge
[Analysis] This question examines mathematical knowledge. Both linear sieve and Eratosthenes can determine primes, enumeration can also work, but binary reduces the scale and cannot reasonably determine.
15. Among the following sorting algorithms that handle multiple passes of data, which sorting algorithm cannot guarantee to select the maximum or minimum data from the data to be processed in the next pass? ( )
A. Selection Sort
B. Quick Sort
C. Heap Sort
D. Bubble Sort
[Answer] B
[Knowledge Points] Sorting Algorithm Knowledge
[Analysis] This question examines sorting algorithm knowledge. It is important to understand the characteristics of each sorting algorithm. Quick sort selects a number, each time putting those smaller than it on the left and those greater than it on the right, and cannot determine the extreme value.
2. True/False Questions (2 points each, total 20 points)
1. The time complexity of merge sort is O(N log N). ( )
[Answer] Correct
[Knowledge Points] Sorting Algorithm Knowledge
[Analysis] This question examines sorting algorithm knowledge. The description of the time complexity of the merge sort algorithm is correct.
2. Xiao Yang, at his birthday party, takes a piece of H*W chocolate to treat K friends, ensuring that each friend can receive at least one piece of the same size of chocolate. Xiao Yang can use binary search to find the largest side length of chocolate he can distribute. ( )
[Answer] Incorrect
[Knowledge Points] Algorithm Knowledge
[Analysis] Because the syllabus lists both “binary search” and “binary answer (or binary enumeration)”.
3. The following C++ code can implement the Fibonacci sequence recursively, where the first two items are 1, and subsequent items are the sum of the previous two. ( )
[Answer] Incorrect
[Knowledge Points] Algorithm Knowledge
[Analysis] This question examines recursive algorithm knowledge. The recursive function must call itself.
4. The greedy algorithm can achieve local optimality, but it may not be the global optimal solution. ( )
[Answer] Correct
[Knowledge Points] Algorithm Knowledge
[Analysis] This question examines greedy algorithm knowledge. Greediness achieves local optimality.
5. Xiao Yang designed a decomposition program that can convert any non-prime natural number N into several prime factors; this program can be designed. ( )
[Answer] Correct
[Knowledge Points] Mathematical Knowledge
[Analysis] This question examines mathematical knowledge. The prime decomposition theorem states that any integer can be decomposed into a product of prime factors (more rigorously, integers greater than 1).
6. Insertion sort sometimes has a lower time complexity than quicksort. ( )
[Answer] Correct
[Knowledge Points] Sorting Knowledge
[Analysis] This question examines sorting algorithm knowledge. When the data is initially ordered, the fastest time complexity of insertion sort is O(n), while the worst time complexity of quicksort is O(N²).
7. The following C++ code can convert a positive integer N from decimal to octal and output it. ( )
[Answer] Incorrect
[Knowledge Points] Basic Computer Knowledge
[Analysis] This question examines base conversion knowledge. The converted content should be output in reverse order and start with 0.
8. Executing sort(arr, arr+10) on the array int arr[] = {2, 6, 3, 5, 4, 8, 1, 0, 9, 10} will adjust the data in arr to {0, 1, 2, 3, 4, 5, 6, 8, 9, 10}. ( )
[Answer] Correct
[Knowledge Points] Sorting Knowledge
[Analysis] This question examines sorting algorithm knowledge. The sort function defaults to sorting from smallest to largest.
9. Xiao Yang wants to write a program to calculate how many factors the positive integer N has, and after thinking, he wrote a loop that does not exceed N/2 times to calculate. ( )
[Answer] Correct
[Knowledge Points] Mathematical Knowledge
[Analysis] This question examines mathematical knowledge. It is possible to loop through half of N to find all factors.
10. The same integer sequence stored in a singly linked list and a doubly linked list has the same complexity for simple bubble sorting. ( )
[Answer] Correct
[Knowledge Points] Sorting Algorithm Knowledge
[Analysis] This question examines sorting algorithm knowledge. Bubble sort involves swapping adjacent data, and modifying the node chain operation does not change the complexity.
3. Programming Questions (25 points each, total 50 points)
1. Xiao Yang’s Lucky Numbers
Problem Description
Xiao Yang believes that all perfect square numbers greater than or equal to a are his super lucky numbers.
Xiao Yang also believes that all multiples of super lucky numbers are his lucky numbers. Naturally, all of Xiao Yang’s super lucky numbers are also lucky numbers.
For a non-lucky number, Xiao Yang stipulates that it can be continuously incremented by 1 until it becomes a lucky number. We call this process lucky transformation. For example, if a=4, then 4 is the smallest lucky number, while 1 is not, but we can continuously perform +1 on 1 for 3 times to make it 4, so we can say that the result after lucky transformation is 4.
Now, Xiao Yang gives N numbers, please first determine whether they are lucky numbers; then, for non-lucky numbers, please lucky transform them.
Input Description
The first line contains 2 positive integers a, N.
In the next N lines, each line contains one positive integer x, indicating the number to be judged (lucky transformed).
Output Description
Output N lines; for each given x, if it is a lucky number, please output lucky, otherwise please output the result after lucky transformation.
Special Reminder
In regular programs, it is good practice to provide hints in input and output. However, in this exam, due to system limitations, please do not include any prompt information in the input and output.
Sample Input 1
Sample Output 1
Sample Explanation 1
1 is not a super lucky number because it is less than a, so it is not a lucky number. After performing +1 three times, it finally becomes the lucky number 4.
4 is a lucky number, so it directly outputs lucky.
5 is not a lucky number, and after performing +1 three times, it finally becomes the lucky number 8.
9 is a lucky number, so it directly outputs lucky.
Sample Input 2
Sample Output 2
Sample Explanation 1
The numbers 1, 4, 5, and 9 are processed similarly as in Sample Input 1.
Data Scale
For 30% of test points, ensure a,x≤ 100, N ≤ 100.
For 60% of test points, ensure a, x≤ 106.
For all test points, ensure a ≤1,000,001; ensure N ≤2×105; ensure 1 ≤ x ≤1,000,001.
[Problem Summary] Given a standard for perfect square numbers, deduce which are super lucky numbers, then determine which of the N numbers are super lucky numbers, output “lucky” if they are, or output the nearest larger number if they are not.
[Knowledge Points] Mathematical Knowledge, Sieve of Eratosthenes Knowledge, Loop Knowledge
[Solution Idea] Perfect square numbers, by definition, include 1, 4, 9, 16, 25, etc. Super lucky numbers can also be multiples of perfect squares, thus 8, 12, 18, etc. are also super lucky numbers. The data range is large, up to 1e6, using the Sieve of Eratosthenes template to determine if each number is a lucky number. For non-lucky numbers, retain the nearest lucky number as the answer. Finally, complete the entire query.
[Reference Program]
2. Cooking Problem
Problem Description
There are N types of ingredients, numbered from 0 to N – 1, where the i-th ingredient has a deliciousness of ai.
Different combinations of ingredients may produce wonderful chemical reactions. Specifically, if two ingredients have deliciousness x and y, then their compatibility is x and y. The and operation is a bitwise AND operation, which requires converting both operands to binary, padding with 0 in higher bits, and performing AND operation bit by bit. For example, 12 and 6 are represented in binary as 1100 and 0110, respectively. Performing AND operation bit by bit yields 0100, which converts to decimal as 4, therefore 12 and 6 = 4. In C++ or Python, you can directly use the & operator to represent the AND operation.
Now, please find the two ingredients with the highest compatibility and output their compatibility.
Input Description
The first line contains one integer N, indicating the number of ingredients.
The next line contains N integers separated by spaces, representing the deliciousness of each ingredient.
Output Description
Output a single integer indicating the highest compatibility.
Special Reminder
In regular programs, it is good practice to provide hints in input and output. However, in this exam, due to system limitations, please do not include any prompt information in the input and output.
Sample Input 1
Sample Output 1
Sample Explanation 1
The compatibility between ingredients numbered 1 and 2 is 2 and 3 = 2, which is the highest compatibility among all pairs of ingredients.
Sample Input 2
Sample Output 2
Sample Explanation 1
The compatibility between the ingredients numbered 3 and 4 is 10 and 13 = 8, which is the highest compatibility among all pairs of ingredients.
Data Scale
For 40% of test points, ensure N ≤ 1, 000;
For all test points, ensure N ≤ 106, 0 ≤ ai ≤ 2,147,483,647.
[Problem Summary] Select two numbers and find the maximum result of the operation between these two numbers.
[Knowledge Points] Bitwise Operation Knowledge, Loop Knowledge, Sorting Knowledge
[Solution Idea] Two numbers can be selected using double loops to enumerate the two numbers and take the maximum value to get the answer. This is feasible for the first 40% of test points. However, when the data volume is large, it will time out. We know that the two numbers corresponding to the binary representation, the higher the bit that is 1, the more likely it is to be the answer. Therefore, from the highest bit, count whether at least two numbers have the highest bit as 1, keep the highest bit result, and delete the numbers whose highest bit is not 1; then check whether the next highest bit has at least two numbers with binary bits as 1, and so on, to find which two numbers yield the maximum result. Using quicksort, put the remaining numbers with the current bit as 1 at the front, with a time complexity of O(N*log(a_i max value)).
[Reference Program]
[Contact Us]
1. GESP WeChat: Follow the “CCF GESP” public account, and leave a message in text form to get a reply.
2. GESP Email: [email protected]
Please describe the inquiry in detail in the email and leave the examinee’s contact information, name, and ID number for timely and effective processing.
3. GESP Phone: 0512-67656856
Consultation hours: Monday to Friday (excluding legal holidays): morning 8:30-12:00; afternoon 13:00-17:30
The registration for the fifth session of GESP certification has started. Scan the QR code below to follow the GESP public account to register.
Click “Read the original text” to join CCF.