2025年厦门市小学生计算机C++语言竞赛（初赛）模拟试卷

三．程序阅读选择题(1～9题，每题2分，共18分)

程序一：约瑟夫环问题

#include<iostream>
using namespace std;
int josephus(int n, int k) {
    int survivor = 0;
    for (int i = 2; i <= n; i++) {
        survivor = (survivor + k) % i;
    }
    return survivor + 1;
}
int main() {
    int n, k;
    cin >> n >> k;
    cout << josephus(n, k) << endl;
    return 0;
}

1. 当输入数据为"5 2"时，输出结果是：{{ select(1) }}

• 1
• 2
• 3
• 4

2. 当输入数据为"7 3"时，输出结果是：{{ select(2) }}

• 4
• 5
• 6
• 7

3. 该算法的时间复杂度是：{{ select(3) }}

• O(n)
• O(n²)
• O(k)
• O(nk)

程序二：汉诺塔问题

#include<iostream>
using namespace std;
int count = 0;
void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        count++;
        return;
    }
    hanoi(n-1, from, aux, to);
    count++;
    hanoi(n-1, aux, to, from);
}
int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'C', 'B');
    cout << count << endl;
    return 0;
}

4. 当输入数据为3时，输出结果是：{{ select(4) }}

• 3
• 5
• 7
• 9

5. 当输入数据为4时，输出结果是：{{ select(5) }}

• 8
• 12
• 15
• 16

6. n个盘子的汉诺塔问题最少需要移动的次数公式是：{{ select(6) }}

• 2ⁿ - 1
• 2ⁿ
• n²
• n!

程序三：组合数计算

#include<iostream>
using namespace std;
int combination(int n, int m) {
    if (n == 0 || n == m) return 1;
    if (n > m) return 0;
    return combination(n-1, m-1) + combination(n, m-1);
}
int main() {
    int n, m;
    cin >> n >> m;
    cout << combination(n, m) << endl;
    return 0;
}

7. 当输入数据为"2 5"时，输出结果是：{{ select(7) }}

• 5
• 10
• 15
• 20

8. 当输入数据为"3 6"时，输出结果是：{{ select(8) }}

• 10
• 15
• 20
• 25

9. 该程序使用的方法是：{{ select(9) }}

• 递归
• 迭代
• 动态规划
• 数学公式

四．完善程序选择题(10～19题，每题2分，共20分)

程序四：快速排序算法

#include<iostream>
using namespace std;
void quickSort(int arr[], int left, int right) {
    if (left >= right) return;
    
    int pivot = arr[(left + right) / 2];
    int i = left, j = right;
    
    while (i <= j) {
        while (①) i++;
        while (②) j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    
    quickSort(arr, left, ③);
    quickSort(arr, ④, right);
}

int main() {
    int arr[] = {5, 3, 8, 4, 2, 7, 1, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

10. 第①空应填写：{{ select(10) }}

• arr[i] < pivot
• arr[i] > pivot
• arr[i] <= pivot
• arr[i] >= pivot

11. 第②空应填写：{{ select(11) }}

• arr[j] > pivot
• arr[j] < pivot
• arr[j] <= pivot
• arr[j] >= pivot

12. 第③空应填写：{{ select(12) }}

• j
• i
• j-1
• i+1

13. 第④空应填写：{{ select(13) }}

• j
• i
• j+1
• i-1

14. 快速排序的平均时间复杂度是：{{ select(14) }}

• O(nlogn)
• O(n²)
• O(n)
• O(logn)

程序五：筛选法求质数

#include<iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    bool isPrime[n+1];
    
    for (int i = 2; i <= n; i++) {
        ①;
    }
    
    for (int i = 2; i * i <= n; i++) {
        if (②) {
            for (int j = i * i; j <= n; j += i) {
                ③;
            }
        }
    }
    
    cout << "质数: ";
    for (int i = 2; i <= n; i++) {
        if (④) {
            cout << i << " ";
        }
    }
    return 0;
}

15. 第①空应填写：{{ select(15) }}

• isPrime[i] = true
• isPrime[i] = false
• isPrime[i] = i
• isPrime[i] = 0

16. 第②空应填写：{{ select(16) }}

• isPrime[i]
• !isPrime[i]
• isPrime[i] == false
• isPrime[i] == 0

17. 第③空应填写：{{ select(17) }}

• isPrime[j] = false
• isPrime[j] = true
• isPrime[j] = j
• isPrime[j] = 0

18. 第④空应填写：{{ select(18) }}

• isPrime[i]
• !isPrime[i]
• isPrime[i] == false
• isPrime[i] == 0

19. 当输入为30时，程序输出的质数个数是：{{ select(19) }}

• 8
• 9
• 10
• 11