该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

提高组 CSP-S 2026 初赛模拟卷7

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

1. 表达式 a*(b+c)-d/f 转后缀表达式的结果是（ ） {{ select(1) }}

• abc*+df-/
• abc+*df/-
• bc+a*df/-
• abc+x-df/

2. 以下字符串中，字典序最小的是（ ） {{ select(2) }}

• NOIP2017
• NOIPC
• NOIPC++
• NOIPP

3. 在 C++ 中，表达式 ('O'-'I')^13%9+5 的值是（ ） {{ select(3) }}

• 7
• 8
• 14
• 15

4. 已知数组 A 中，每个元素 A[i,j] 在存储时要占3字节，设 i 从1变化到8，j 从1变化到10，分配内存时是从地址 SA 开始连续按行存储分配的。A[5,8] 的起始地址为（ ） {{ select(4) }}

• SA+141
• SA+180
• SA+222
• SA+225

5. 在 TCP/IP 协议族中，最核心的网络协议是（ ） {{ select(5) }}

• UDP
• HTTP
• TCP
• IP

6. 应用快速排序的分治思想可以实现一个求第 K 大数的程序。假定不考虑极端的最坏情况，在平均情况下算法的期望时间复杂度为（ ） {{ select(6) }}

• O(n²)
• O(logn)
• O(n)
• O(n log n)

7. 为解决计算机主机与外设之间速度不匹配的问题，通常会设置一个缓冲池。主机将输出数据依次写入该缓冲池，而外设从该缓冲池中依次取出数据。该缓冲池应该是一个（ ）结构。 {{ select(7) }}

• 栈
• 队列
• 二叉树
• 链表

8. (1E34)₁₆ - (676)₈ 的结果是（ ） {{ select(8) }}

• (1110001111110)₂
• (7276)₁₀
• (1C6C)₁₆
• (16166)₈

9. 一棵二叉树的前序遍历序列为 ABDECFGH，后序遍历序列为 EDBGFHCA。下列选项中，（ ）不是可能的中序遍历序列。 {{ select(9) }}

• DEBAFGCH
• EDBAGFCH
• DBEAFGCH
• BEDAFGCH

10. 一个栈的输入序列为 1 2 3 4 5，下列序列中，（ ）不可能是栈的输出序列。 {{ select(10) }}

• 5 4 3 2 1
• 2 4 1 3 5
• 3 2 5 4 1
• 1 3 5 4 2

11. Linux 是一个用 C 语言写成的开源计算机操作系统内核，有大量的操作系统是基于 Linux 内核创建的。以下操作系统中，（ ）使用的不是 Linux 内核。 {{ select(11) }}

• Android
• CentOS
• Windows
• Ubuntu

12. 下列关于计算机算法的说法中，正确的是（ ） {{ select(12) }}

• 对于一个问题，我们能通过优化算法，不断降低算法复杂度
• 判断一个算法的好坏，主要依据它在某台计算机上具体实现时的运行时间
• 一个算法必须至少有一个输入
• 算法复杂度理论中，P=NP 问题（NP 完全问题）仍是一个未解之谜

13. 以下关于二叉树性质的描述中，正确的是（ ） {{ select(13) }}

• 在任意非空二叉树中，若叶节点的个数为 n₀，度为2的节点数为 n₂，则 n₀ = n₂ + 1
• 深度为 k 的二叉树至多有 2k 个节点
• 没有一棵二叉树的前序遍历序列与后序遍历序列相同
• 具有 n 个节点的完全二叉树的深度为 ⌊log₂(n+1)⌋

14. 排序算法是稳定的，这句话的意思是，排序前后，关键码相同的记录的相对位置不发生改变。以下排序算法不稳定的是（ ） {{ select(14) }}

• 插入排序
• 快速排序
• 冒泡排序
• 归并排序

15. 给定 m 种颜色和有 n 个点的手环，要求用这 m 种颜色给这条手环着色。若两种着色方案可通过旋转或翻转相互得到，则视为同一种着色方案，如对于有3个点的手环，ABC 的着色方案与 BCA（旋转）、ACB（翻转）视为同一种方案。当 m=2 且 n=2 时，一共有3种着色方案，分别为 AA、AB、BB。那么当 m=5 且 n=4 时，一共有（ ）种着色方案。 {{ select(15) }}

• 625
• 160
• 60
• 120

---

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题2分，选择题每题3分，共计40分）

(1)

#include <iostream>
using namespace std;
unsigned short tot;
void Hanoi(int n, char A, char B, char C){
    ++tot;
    if(n == 1){
        cout << A << "->" << C << "/";
        return;
    }
    Hanoi(n-1, A, C, B);
    cout << A << "->" << C << "/";
    Hanoi(n-1, B, A, C);
}
int main(){
    int n;
    cin >> n;
    Hanoi(n, 'A', 'B', 'C');
    cout << '\n' << tot << 'n' << tot << '\n';
    return 0;
}

判断题（每题2分）

16. 将 ++tot 移到 Hanoi() 函数返回之前的最后一行，输出结果不会发生变化。（ ） {{ select(16) }}

• 正确
• 错误

17. 输入的 n=2 时，输出的第一行为 A->B/B->C/A->C/。（ ） {{ select(17) }}

• 正确
• 错误

18. 输入的 n=3 时，输出的第二行为 8。（ ） {{ select(18) }}

• 正确
• 错误

19. 本程序的含义可以是：有三根柱子，第一根柱子从上到下依次套有编号为1~n的圆环，现在每次可以移动某根柱子顶部的圆环到另一根柱子的顶部，并要求编号较大的圆环始终不能在编号较小的上面，输出一种操作次数最少的方案以及对应的操作次数。（ ） {{ select(19) }}

• 正确
• 错误

---

(2)

#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;
const int N = 105;
int a[N][N];
int main(){
    int n, x, y, count;
    cin >> n;
    memset(a, 0, sizeof(a));
    count = a[x=0][y=n-1] = 1;
    while(count < n*n){
        while(x+1 < n && !a[x+1][y]) a[++x][y] = ++count;
        while(y-1 >= 0 && !a[x][y-1]) a[x][--y] = ++count;
        while(x-1 >= 0 && !a[x-1][y]) a[--x][y] = ++count;
        while(y+1 < n && !a[x][y+1]) a[x][++y] = ++count;
    }
    for(x=0; x<n; x++){
        for(y=0; y<n; y++){
            cout << setw(5) << a[x][y];
        }
        cout << endl;
    }
    return 0;
}

判断题（每题2分）

20. 删除 memset(a, 0, sizeof(a));，不影响程序运行结果。（ ） {{ select(20) }}

• 正确
• 错误

21. 将 while(count < n*n) 改为 while(count <= n*n)，不影响程序运行结果。（ ） {{ select(21) }}

• 正确
• 错误

22. 输入的 n=4 时，程序输出的 a[3][2] 的值为15。（ ） {{ select(22) }}

• 正确
• 错误

选择题（每题3分）

23. 本程序的时间复杂度为（ ） {{ select(23) }}

• O(n)
• O(n²)
• O(n³)
• O(n²logn)

24. 输入的 n=100 时，a[33][66] 的值为（ ） {{ select(24) }}

• 8779
• 8707
• 10957
• 8845

---

(3)

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
string s;
int main(){
    int k; // 保证输入 0≤k<26
    cin >> k >> s;
    int n = s.length();
    for(int i=0; i<n; i++){
        if(s[i] <= 'Z' && s[i] + k > 'Z')
            s[i] = (s[i] + k) % 'Z' + 'A' - 1;
        else if('A' <= s[i] && s[i] <= 'Z')
            s[i] += k;
    }
    char pre;
    int st = -1;
    for(int i=0; i<n; i++){
        if(s[i] < 'A' || s[i] > 'Z'){
            if(st == -1){
                st = i;
                pre = s[i];
            }else{
                char tmp = s[i];
                s[i] = pre;
                pre = tmp;
            }
        }
    }
    if(st != -1) s[st] = pre;
    cout << s << endl;
    return 0;
}

判断题（每题2分）

25. 删除 if(st != -1) s[st] = pre;，不影响程序运行结果。（ ） {{ select(25) }}

• 正确
• 错误

26. 如果输入的 s 不含大写字母，则输出结果与 k 的值无关。（ ） {{ select(26) }}

• 正确
• 错误

27. 如果知道输出结果，能够反推出唯一的输入。（ ） {{ select(27) }}

• 正确
• 错误

28. 当 k 的值确定时，不存在两个不同的输入使得输出相同。（ ） {{ select(28) }}

• 正确
• 错误

选择题（每题3分）

29. 如果输入是 6 KU96APY5，则输出为（ ） {{ select(29) }}

• QB96GWE5
• QA59GVE6
• PA59GWF6
• PB96GWE5

30. 如果输出是 ab1287F2Tguz，则输入可能为（ ） {{ select(30) }}

• 0 ab1287F2Tguz
• 3 b1287BgTuza
• 16 b12872PgDuza
• 13 b12872MgAuza

---

三、完善程序（单选题，每小题3分，共计30分）

(1) 拓扑排序

在我们所学的课程中，部分课程之间可能存在依赖关系，如我们在学习图论知识之前，需要先学习离散数学的基础知识。一门课可能有若干先修课程。现在老师需要安排一些课程的授课计划，排课需要遵从一定的规则，即只有修习完某课程的全部先修课程后，才能修习该课程。在本例中，用 1~n 表示 n 门课程，用 x y 表示 x 是 y 的先修课程。输入数据保证图中没有环与重边。要求输出任意一个可行的授课顺序。图用邻接矩阵方法存储。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 105;
int a[N][N];
int in[N], s[N];
int n, m, u, v;
void Topo(){
    queue<int> q;
    int cnt = 0;
    for(int i=1; i<=n; i++)
        if( ① ) q.push(i);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        s[cnt++] = ②;
        for(int i=1; i<=n; i++){
            if( ③ ){
                ④;
                if(in[i] == 0) q.push(i);
            }
        }
    }
}
int main(){
    memset(in, 0, sizeof(in));
    memset(a, 0, sizeof(a));
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> u >> v;
        in[v]++;
        ⑤;
    }
    Topo();
    for(int i=0; i<n; i++){
        if(i) cout << ' ';
        cout << s[i];
    }
    cout << endl;
    return 0;
}

31. ①处应填（ ） {{ select(31) }}

• in[i] == 0
• in[i] == 1
• a[1][u] == 0
• a[1][u] == 1

32. ②处应填（ ） {{ select(32) }}

• q.front()
• cur
• q.back()
• s[cur]

33. ③处应填（ ） {{ select(33) }}

• !--in[i]
• a[u][v] == 1
• a[cur][i] == 1
• !in[i]

34. ④处应填（ ） {{ select(34) }}

• in[i]++
• in[i]--
• q.pop()
• q.push(cur)

35. ⑤处应填（ ） {{ select(35) }}

• in[u]++
• in[u]--
• a[u][v] = 1
• a[v][u] = 1

---

(2) 八皇后问题

要求用回溯法求解八皇后问题：在 8×8 的棋盘上放置八个皇后，确保任意两个皇后都不在同一行、同一列或同一斜线上。请输出八皇后问题的所有可行解。

#include <iostream>
#include <cmath>
using namespace std;

bool Place(int k, int i, int *x){
    for(int j=0; j<k; j++)
        if(x[j] == i || ①)
            return false;
    return true;
}

void NQueens(int k, int n, int *x){
    for(int i=0; i<n; i++)
        if(Place(k, i, x)){
            ②;
            if( ③ ){
                for(int j=0; j<n; j++)
                    cout << x[j] << " ";
                cout << endl;
            }else{
                ④;
            }
        }
}

int main(){
    int x[8];
    for(int i=0; i<8; i++) x[i] = -1;
    ⑤;
    return 0;
}

36. ①处应填（ ） {{ select(36) }}

• x[j] == i-1
• abs(x[j]-i) <= 1
• abs(x[j]-k) == i-j
• abs(x[j]-i) == k-j

37. ②处应填（ ） {{ select(37) }}

• x[i] = k
• x[k] = n-i
• x[k] = i
• x[i] = x[k]

38. ③处应填（ ） {{ select(38) }}

• k > n-1
• k >= n-1
• k == n
• k > n

39. ④处应填（ ） {{ select(39) }}

• NQueens(k, n-1, x)
• NQueens(k+1, n, x)
• NQueens(k+1, n-1, x)
• cout << x[k] << " "

40. ⑤处应填（ ） {{ select(40) }}

• NQueens(1, 8, x)
• NQueens(0, 7, x+1)
• NQueens(0, 8, x)
• NQueens(1, 8, x+1)