问题标题: CSP/J(S)竞赛知识点分享P1

一、进制

核心知识点

1. 进制表示与书写规则

   • 二进制（B）：由 0、1 组成，如1011B；八进制（O）：0-7，前缀0（如015O）；十六进制（H）：0-9、A-F（大小写均可），前缀0x（如0x2F）。
   • 十进制无特殊前缀，默认表示。

2. 进制转换技巧

   • R 进制转十进制：按权展开法，公式：\(N = d_0 \times R^0 + d_1 \times R^1 + ... + d_n \times R^n\)（\(d_i\)为第 i 位数字）。技巧：从右往左，每步乘以 R 再累加（如二进制1011转十进制：1×2³+0×2²+1×2¹+1×2⁰=11）。
   • 十进制转 R 进制：除 R 取余法（整数部分）、乘 R 取整法（小数部分）。技巧：余数逆序排列，小数部分取整顺序排列（如 11 转二进制：11÷2=5 余 1→5÷2=2 余 1→2÷2=1 余 0→1÷2=0 余 1→逆序得1011）。
   • 二进制与十六进制互转：4 位二进制对应 1 位十六进制（如1011 1100→BC）；二进制与八进制互转：3 位对应 1 位（如10 111→27）。

3. 计算机中的数据表示

   • 原码、反码、补码：
     • 原码：符号位（0 正 1 负）+ 数值位（如 + 3 原码00000011，-3 原码10000011）。
     • 反码：正数与原码相同；负数符号位不变，数值位取反（-3 反码11111100）。
     • 补码：正数与原码相同；负数 = 反码 + 1（-3 补码11111101）。技巧：补码转原码可逆向操作（补码 - 1 得反码，再取反得原码），简化负数运算（减法变加法）。
   • 溢出判断：两正数相加结果为负，或两负数相加结果为正，则溢出。

二、C++ 类型与编码（含计算机基**）

1. C++ 数据类型与编码

• 基本类型（大小、范围及应用）：

  类型字节数取值范围（十进制）用途bool1true(1)、false(0)逻辑判断char1-128~127（补码）或 0~255（无符号）存储字符（ASCII 码）short2-32768~32767短整数int4-2¹⁵~2¹⁵-1（或 - 2³¹~2³¹-1，依编译器）常用整数long long8-2⁶³~2⁶³-1大整数float4约 ±3.4×10³⁸（6-7 位有效数字）单精度浮点数double8约 ±1.7×10³⁰⁸（15-17 位有效数字）双精度浮点数（默认）

• 类型转换：

  • 隐式转换：小范围→大范围（如int→long long），避免数据丢失；
  • 显式转换（强制类型转换）：(类型)变量（如(double)a），需注意精度损失。

• 字符串编码：

  • ASCII 码：7 位表示 128 个字符（0-31 为控制字符，32 为空格，48-57 为数字，65-90 为大写字母，97-122 为小写字母）。
  • Unicode 与 UTF-8：Unicode 为全球字符统一编码（如汉字 “中” 编码0x4E2D）；UTF-8 为可变长编码（汉字占 3 字节）。

2. 计算机基**知识

• 电脑应用领域：科学计算（如天气预报）、数据处理（如数据库）、过程控制（如工业自动化）、人工智能（如机器学习）、多媒体技术（如视频编辑）等。
• 电脑操作：
  • 操作**基本操作：文件**（新建、复制、删除、路径表示如C:\Users\file.txt）、进程**（任务**器）、快捷键（Ctrl+C复制、Ctrl+V粘贴）。
  • 命令行基**：cd切换目录、dir（Windows）/ls（Linux）列文件、md创建文件夹。
• 计算机发展史：
  • 第一台电子计算机：1946 年 ENIAC（**，用于军事计算）。
  • 关键人物：冯・诺依曼（提出 “存储程序” 思想，奠定现代计算机体系）、图灵（图灵机、图灵测试）。
  • generations：
  • 第一代（1946-1958）：电子管，机器语言；
  • 第二代（1958-1964）：晶体管，汇编语言；
  • 第三代（1964-1971）：集成电路，高级语言；
  • 第四代（1971 - 今）：大规模集成电路，操作**、网络普及。

三、位运算（含计算机软硬件）

1. 位运算符及技巧

运算符含义示例（a=6 即0110，b=3 即0011）技巧应用

&按位与（同 1 则 1）a & b = 0010（2）判断奇偶（x & 1 == 1为奇）；取位（x & (1<<k)取第 k 位）

|按位或（有 1 则 1）`ab = 0111`（7）置位（`x(1<<k)` 将第 k 位置 1）^按位异或（不同则 1）a ^ b = 0101（5）交换变量（a ^= b; b ^= a; a ^= b）；翻转位（x ^ (1<<k)翻转第 k 位）

~按位非（0 变 1，1 变 0）~a = 1001（补码，对应 - 7）取反加 1 得负数（~x + 1 = -x）

<<左移（左移 n 位 ×2ⁿ）a << 1 = 1100（12）快速乘 2ⁿ（比乘法高效）

>>右移（右移 n 位 ÷2ⁿ）a >> 1 = 0011（3）快速除 2ⁿ（正数补 0，负数补 1）
 

2. 计算机软硬件组成

• 硬件组成（冯・诺依曼体系五大部件）：

  • 运算器：执行算术（+、-）和逻辑（&、|）运算（核心为 ALU）。
  • 控制器：协调各部件工作，包含指令寄存器、程序计数器（PC）。
  • 存储器：
    • 内存（RAM）：临时存储数据，**丢失，速度快；
    • 外存（硬盘 HDD、固态硬盘 SSD）：长期存储，**不丢失，速度慢。
  • 输入设备：将外部信息传入计算机（键盘、鼠标、扫描仪）。
  • 输出设备：将计算结果传出（显示器、打印机、音箱）。

• 硬件体系结构：

  • 总线：连接各部件的公共线路，分数据总线（传数据）、地址总线（传地址，宽度决定最大寻址空间：n 位→2ⁿ字节）、控制总线（传控制信号）。
  • 主板：集成总线和接口，连接 CPU、内存、外存等。

• 软件组成：

  • **软件：操作**（Windows、Linux）、编译器（g++）、数据库****（MySQL）。
  • 应用软件：办公软件（Office）、编程 IDE（Dev-C++）、游戏等。

四、数学（含计算机相关）

1. 核心数学知识

• 初等数论：

  • 整除与同余：若\(a \div b\)余 0 则\(b|a\)；\(a \equiv b \mod m\)表示\(m|(a-b)\)。
  • 最大公约数（gcd）与最小公倍数（lcm）：
    • gcd (a,b)：辗转相除法（gcd(a,b)=gcd(b,a%b)，直到 b=0）；
    • lcm (a,b) = a×b /gcd (a,b)（需先除后乘避免溢出）。
  • 素数：埃氏筛法（标记倍数）、线**筛法（每个数被最小质因子标记，O (n)）。
  • 同余方程：扩展欧几里得算法（求 ax+by=gcd (a,b) 的解）。

• 组合数学：

  • 排列：\(A(n,k) = n!/(n-k)!\)（有序）；组合：\(C(n,k) = n!/(k!(n-k)!)\)（无序）。
  • 杨辉三角：\(C(n,k) = C(n-1,k-1) + C(n-1,k)\)（边界\(C(n,0)=C(n,n)=1\)）。
  • 容斥原理：计算多个集合的并集（如 1~n 中能被 2 或 3 整除的数：\(\lfloor n/2 \rfloor + \lfloor n/3 \rfloor - \lfloor n/6 \rfloor\)）。

• 其他：斐波那契数列（递归 / 递推）、卡特兰数（括号匹配、二叉树计数）、逻辑运算（与或非、真值表）。

2. 计算机相关

• CPU 与总线：

  • CPU **能指标：主频（时钟频率，如 3.0GHz）、核心数（多任务并行）、缓存（L1/L2/L3，速度介于 CPU 与内存之间）。
  • 总线带宽：数据传输速率（总线宽度 × 主频，如 32 位总线 ×1GHz=4GB/s）。

• NOI 相关：

  • NOI（全国青少年信息学奥林匹克竞赛）：中国最高级别信息学竞赛，CSP-J/S 是其入门级认证（J 为入门，S 为提高）。
  • 认证流程：第一轮（笔试，基**知识 + 程序理解）→第二轮（上机编程）。

• 计算机奖项：

  • 图灵奖（“计算机界诺贝尔奖”）：表彰对计算机科学有重大贡献者（如姚期智：2000 年得主，首位华人）。
  • 其他：ACM 国际大学生程序设计竞赛（ICPC）、IOI（国际信息学奥林匹克）。

五、基**排序算法（含时间复杂度、外部设备）

1. 基**排序算法（代码与优化）

• 冒泡排序：

  • 原理：相邻元素比较，逆序则交换，每轮将最大元素 “浮” 到末尾。
  • 优化：加标志位flag，若某轮无交换则提前终止（最好时间复杂度 O (n)）。
  • 时间复杂度：最坏 O (n²)，平均 O (n²)；空间复杂度 O (1)；稳定。

• 选择排序：

  • 原理：每轮选最小（大）元素，与当前位置交换。
  • 时间复杂度：O (n²)（无论好坏）；空间复杂度 O (1)；不稳定（如 [2,2,1]）。

• 插入排序：

  • 原理：将元素逐个插入已排序序列的合适位置（类似整理手牌）。
  • 优化：二分查找插入位置（减少比较次数，但移动次数不变）。
  • 时间复杂度：最好 O (n)（已排序），最坏 O (n²)；空间复杂度 O (1)；稳定。

2. 时间复杂度

• 定义：描述算法执行时间随数据规模 n 的增长趋势，忽略常数和低阶项。
• 计算规则：
  • 循环嵌套取最高阶（如两层循环 O (n²)）；
  • 顺序执行取最大值（如 O (n) + O (n²) = O (n²)）；
  • 常见复杂度：O (1)（常量）< O (logn)（二分）< O (n)（线**）< O (nlogn)（快排）< O (n²)（冒泡）< O (2ⁿ)（递归斐波那契）。

3. 外部设备

• 输入设备：

  • 字符输入：键盘（通过扫描码→ASCII 码转换）；
  • 图像输入：扫描仪（光电转换）、摄像头（CCD 传感器）；
  • 其他：鼠标（机械 / 光电，检测位移）、麦克风（声电转换）。

• 输出设备：

  • 显示设备：显示器（LCD/LED，分辨率如 1920×1080）；
  • 打印设备：打印机（激光 / **墨，分辨率 dpi）；
  • 其他：音箱（电声转换）、投影仪。

• 外存储设备：

  • 硬盘（HDD）：磁头读写磁道，容量大（TB 级），速度较慢；
  • 固态硬盘（SSD）：闪存芯片，速度快（无机械延迟），价格高；
  • U 盘：便携，基于闪存，容量中等（GB 级）。

六、递归与分治（含计算机网络、编程语言）

1. 递归

• 定义：函数调用自身解决问题的方法，需满足：
  • 终止条件（避免无限递归）；
  • 递归关系（将问题分解为更小的子问题）。
• 示例：
  • 阶乘：f(n) = n * f(n-1)（终止条件f(0)=1）；
  • 汉诺塔：移动 n 个盘→移动 n-1 个到辅助柱→移动第 n 个到目标柱→移动 n-1 个到目标柱。
• 技巧：
  • 画递归树分析时间复杂度（如斐波那契递归树有大量重复计算，需记忆化优化）；
  • 尾递归（递归调用在函数末尾）可被编译器优化为循环（如f(n, res) = f(n-1, n*res)）。

2. 分治算法

• 思想：分（拆分为子问题）→治（解决子问题）→合（合并子问题结果）。
• 示例：
  • 归并排序：拆分为两半→各自排序→合并两个有序数组（O (nlogn)，稳定）；
  • 快速排序：选基准→分区（小于 / 大于基准）→递归排序分区（平均 O (nlogn)，最坏 O (n²)，不稳定）。

3. 计算机网络

• 基本概念：
  • 网络协议：规则集合（如 TCP/IP 协议簇）；
  • 网络拓扑：总线型、星型（常见，如家庭路由器）、环型。
• TCP/IP 协议：
  • 应用层：HTTP（网页）、FTP（文件传输）、SMTP（邮件）；
  • 传输层：TCP（可**传输，三次握手建立连接）、UDP（不可**，速度快）；
  • 网络层：IP（IP 地址，如 IPv4 为 32 位192.168.1.1）；
  • 链路层：处理硬件地址（MAC 地址）。
• URL 结构：协议://域名:端口/路径（如https://www.noi.cn:443/news）。

4. 编程语言

• 分类：
  • 编译型：C/C++（通过编译器生成机器码，执行快）；
  • 解释型：Python/JavaScript（解释器逐行执行，跨平台**好）。
• 特点对比：
  • C++：高效、接近硬件，适合竞赛和**开发；
  • Python：简洁、库丰富，适合快速开发；
  • Java：跨平台（JVM），适合企业级应用。

七、二分法与进阶排序算法

1. 二分法

• 适用条件：有序数组（升序 / 降序），支持随机访问（如数组，链表不适用）。
• 基本步骤：
  1. 初始化左边界l=0，右边界r=n-1；
  2. 计算中点mid = (l + r) // 2；
  3. 比较a[mid]与目标值：等于则返回，小于则l=mid+1，大于则r=mid-1；
  4. 重复至l > r（未找到）。
• 技巧：
  • 避免溢出：mid = l + (r - l) // 2（代替(l + r) // 2）；
  • 查找左 / 右边界：如找第一个≥x 的位置（调整r=mid或l=mid+1）。

2. 进阶排序算法

• 堆排序：

  • 原理：构建大根堆（父节点≥子节点）→每次取堆顶（最大值）→调整堆（O (nlogn)，不稳定）。
  • 步骤：建堆（O (n)）→n-1 次调整（每次 O (logn)）。

• 希尔排序：

  • 原理：分组插入排序，逐渐缩小步长（如 n/2→n/4→…→1），最后一次为普通插入排序（时间复杂度与步长有关，约 O (n¹.³)，不稳定）。

• 归并排序：

  • 优势：稳定，适合外排序（数据量大，需借助外存）；
  • 缺点：需额外 O (n) 空间。

八、数据结构（线**）与搜索

1. 线**数据结构

• 数组：

  • 特点：连续存储，随机访问 O (1)，插入 / 删除 O (n)（需移动元素）。
  • 应用：静态数据存储，如排序算法的基**容器。

• 链表：

  • 单链表：节点含数据域和指针域（指向下一节点），插入 / 删除 O (1)（已知前驱），访问 O (n)；
  • 双链表：节点多一个前驱指针，可双向遍历；
  • 循环链表：尾节点指向头节点，适合环形问题（如约瑟夫环）。

• 栈：

  • 特点：后进先出（LIFO），操作：压栈（push）、弹栈（pop）、取栈顶（top），O (1)。
  • 应用：表达式求值（括号匹配）、递归调用（**栈）。

• 队列：

  • 特点：先进先出（FIFO），操作：入队（enqueue）、出队（dequeue），O (1)（循环队列避免假溢出）。
  • 应用：BFS、任务调度。

• 字符串：

  • 存储：C 风格（char[]，以\0结尾）、C++ string类（自动**内存）；
  • 操作：拼接（+）、比较（==）、子串（substr）。

2. 搜索算法

• 顺序搜索：逐个比较，O (n)，适合无序数据。
• 索引搜索：先建索引表（如分块索引），缩小搜索范围，介于顺序与二分之间。

九、数据结构（树）

1. 二叉树基本**质

• 第 k 层最多有\(2^{k-1}\)个节点（k≥1）；
• 深度为 h 的二叉树最多有\(2^h - 1\)个节点（满二叉树）；
• 非空二叉树：叶子节点数 = 度为 2 的节点数 + 1（\(n_0 = n_2 + 1\)）。

2. 特殊树与操作

• 完全二叉树：

  • 定义：除最后一层外均满，最后一层节点左对齐；
  • 编号（根为 1）：左孩子 = 2×i，右孩子 = 2×i+1，父节点 = i//2。

• 二叉搜索树（BST）：

  • **质：左子树≤根≤右子树；
  • 操作：插入（比根小左移，大右移）、删除（叶子直接删，非叶子用前驱 / 后继替换）、查找（O (logn)，最坏 O (n)）。

• 堆：

  • 大根堆：父≥子；小根堆：父≤子；
  • 操作：插入（放末尾→上浮）、删除堆顶（末尾元素替换→下沉）。

• 哈夫曼树：

  • 定义：带权路径长度（WPL）最小的二叉树（贪心构造：每次选两个最小权值节点合并）；
  • 应用：哈夫曼编码（前缀编码，无歧义，高频字符短编码）。

• 遍历方式：

  • 前序：根→左→右；中序：左→根→右；后序：左→右→根（递归 / 栈实现）；
  • 层序：按层遍历（队列实现）。

十、数据结构（图）

1. 基本概念

• 顶点（V）、边（E）；有向图（边有方向）、无向图（边无方向）；
• 度：无向图中顶点的边数；有向图中入度（ incoming ）+ 出度（ outgoing ）。
• 路径：顶点序列，边连接相邻顶点；环：起点 = 终点的路径。

2. 存储结构

• 邻接矩阵：二维数组g[i][j]表示 i 与 j 是否相连（带权图存权值），空间 O (n²)，适合稠密图。
• 邻接表：数组 + 链表，adj[i]存 i 的所有邻接顶点，空间 O (n+e)，适合稀疏图。

3. 核心算法

• 遍历：

  • DFS（深度优先）：递归或栈，可检测环、连通分量；
  • BFS（广度优先）：队列，可求最短路径（无权图）。

• 最短路径：

  • Dijkstra：单源最短路径，边权非负（贪心 + 优先队列，O (mlogn)）；
  • Floyd：多源最短路径，动态规划（O (n³)，可处理负权但不能有负环）。

• 最小生成树（MST）：

  • Prim：从顶点扩展，适合稠密图（O (n²)）；
  • Kruskal：按边权排序 + 并查集，适合稀疏图（O (mlogm)）。

• 拓扑排序：有向无环图（DAG）的顶点线**排列，满足所有边从左到右（检测环：若排序后顶点数≠n 则有环）。

初赛真题示例（部分考点）

1. 进制转换：（2021 J1）十进制数 2021 对应的十六进制数为______（答案：7E5）。
2. 位运算：（2020 S1）若 x 为 int 型变量，执行x = (x & 0xffff) ^ 0x2后，x 的结果是______（解析：低 16 位与 0xffff 保留，再异或 0x2 翻转第 1 位）。
3. 时间复杂度：（2019 J1）若某算法的时间复杂度为 O (n²)，则 n 扩大 2 倍时，运行时间约扩大______倍（答案：4）。
4. 计算机基**：（2022 J1）下列不属于操作**的是______（选项：A.Windows B.Linux C.Python D.MacOS，答案：C）。
5. 数据结构：（2021 S1）一棵完全二叉树有 2021 个节点，则其中叶子节点的个数为______（解析：n=2021，n0 = (n+1)//2 = 1011）。
   1. 祝大家顺利通过​​​​​​​

李皓冉在2025-09-19 20:07:16追加了内容

PS.

1.R进制转十进制:

2.C++数据类型与编码

李皓冉在2025-09-19 20:11:18追加了内容

3.初等数论:

组合数学

其他

李皓冉在2025-09-19 21:00:38追加了内容

一、单项选择题（共 15 题，每题 2 分，共 30 分）​
下列关于计算机发展史的说法，错误的是（  ）​
A. 1946 年诞生的 ENIAC 是世界上第一台电子计算机​
B. 冯・诺依曼提出 “存储程序” 思想，奠定现代计算机体系基**​
C. 第一代计算机使用晶体管作为核心元器件​
D. 集成电路的发明推动计算机进入第三代发展阶段​
十进制数 2024 对应的二进制数是（  ）​
A. 11111100000  B. 11111000000  C. 11110100000  D. 11101100000​
在 C++ 中，下列数据类型占用字节数最大的是（  ）​
A. int  B. long long  C. float  D. double​
若变量x为int型，且x = 0b101101（二进制），则执行x = x >> 2后，x的十进制值为（  ）​
A. 22  B. 11  C. 5  D. 2​
下列关于二叉树的说法，正确的是（  ）​
A. 完全二叉树的叶子节点一定集中在最后两层​
B. 二叉树的前序遍历序列为 “ABC”，则中序遍历序列一定为 “BAC”​
C. 深度为 k 的二叉树最多有 2^k - 1 个节点​
D. 二叉搜索树中，左子树所有节点的值一定大于根节点的值​
计算机硬件体系中，负责协调各部件工作，包含程序计数器（PC）的部件是（  ）​
A. 运算器  B. 控制器  C. 存储器  D. 输入设备​
下列排序算法中，时间复杂度不受数据初始顺序影响，始终为 O (nlogn) 的是（  ）​
A. 冒泡排序  B. 快速排序  C. 归并排序  D. 插入排序​
若某算法的时间复杂度为 O (nlogn)，当数据规模 n 从 1000 扩大到 2000 时，算法执行时间约扩大（  ）倍（忽略常数项）​
A. 2  B. 4  C. 2log2  D. log2​
在计算机网络中，HTTP 协议属于 TCP/IP 协议簇的哪一层（  ）​
A. 应用层  B. 传输层  C. 网络层  D. 链路层​
下列关于栈的描述，错误的是（  ）​
A. 栈遵循 “后进先出”（LIFO）的原则​
B. 栈的入栈（push）和出栈（pop）操作时间复杂度均为 O (1)​
C. 栈可以用数组或链表实现​
D. 栈的 “栈底” 元素是最后入栈的元素​
十进制数 - 128 的 8 位二进制补码是（  ）​
A. 10000000  B. 11111111  C. 00000000  D. 10000001​
下列关于 NOI 体系的说法，正确的是（  ）​
A. CSP-J 是 NOI 体系中的最高级别竞赛​
B. CSP-J 初赛仅包含编程题，无理论知识题​
C. 参加 NOI 全国赛需先通过省级选拔​
D. IOI 是中国自主举办的信息学竞赛​
若有数组int a[5] = {3, 1, 4, 2, 5}，采用冒泡排序将其从小到大排序，第一轮排序（从左到右比较交换）后，数组的状态是（  ）​
A. {1, 3, 2, 4, 5}  B. {1, 3, 4, 2, 5}  C. {3, 1, 2, 4, 5}  D. {3, 1, 4, 2, 5}​
下列关于图的存储方式，适合存储稀疏图的是（  ）​
A. 邻接矩阵  B. 邻接表  C. 二维数组  D. 哈希表​
若要在有序数组{2, 5, 8, 11, 14, 17}中查找第一个大于 10 的元素，采用二分法查找，需要比较的次数是（  ）​
A. 2  B. 3  C. 4  D. 5​
二、判断题（共 10 题，每题 1 分，共 10 分）​
八进制数的前缀为 “0x”，十六进制数的前缀为 “0”。（  ）​
C++ 中，char类型默认是有符号的，取值范围为 - 128~127。（  ）​
位运算x & (x - 1)可以清除x二进制表示中最右侧的 1。（  ）​
分治算法的核心思想是 “将大问题拆分为小问题，解决小问题后合并结果”。（  ）​
计算机的 Cache 存储器速度比内存慢，容量比内存大。（  ）​
二叉树的中序遍历序列和后序遍历序列可以唯一确定一棵二叉树。（  ）​
快速排序是稳定排序算法，归并排序是不稳定排序算法。（  ）​
计算机网络中，TCP 协议是面向连接的可**传输协议，UDP 协议是无连接的不可**传输协议。（  ）​
递归函数必须包含终止条件，否则会导致无限递归。（  ）​
欧拉函数 φ(n) 表示 1~n 中与 n 互质的数的个数，若 n 为质数，则 φ(n) = n - 1。（  ）​
三、阅读程序题（共 3 题，每题 8 分，共 24 分）​
题 1​
​
#include <iostream>​
using namespace std;​
​
int main() {​
    int n = 123, sum = 0;​
    while (n > 0) {​
        sum += n % 10;​
        n /= 10;​
    }​
    cout << sum << endl;​
    return 0;​
}​
​
该程序的功能是？（4 分）​
程序运行后的输出结果是？（4 分）​
题 2​
​
#include <iostream>​
using namespace std;​
​
int f(int x) {​
    if (x == 1 || x == 2) {​
        return 1;​
    }​
    return f(x - 1) + f(x - 2);​
}​
​
int main() {​
    int n = 8;​
    cout << f(n) << endl;​
    return 0;​
}​
​
函数f(x)的功能是计算什么序列的第 x 项？（4 分）​
程序运行后的输出结果是？（4 分）​
题 3​
​
#include <iostream>​
using namespace std;​
​
int main() {​
    int a[6] = {5, 3, 8, 1, 2, 7};​
    int len = 6;​
    for (int i = 1; i < len; i++) {​
        int temp = a[i];​
        int j = i - 1;​
        while (j >= 0 && a[j] > temp) {​
            a[j + 1] = a[j];​
            j--;​
        }​
        a[j + 1] = temp;​
    }​
    for (int i = 0; i < len; i++) {​
        cout << a[i] << " ";​
    }​
    return 0;​
}​
​
该程序采用的排序算法是什么？（4 分）​
程序运行后的输出结果是？（4 分）​
四、完善程序题（共 2 题，每题 18 分，共 36 分）​
题 1：二分查找（查找有序数组中目标值的位置）​
以下程序实现在升序数组中查找目标值target，若找到则返回其下标，若未找到则返回 - 1。请补全代码。​
​
#include <iostream>​
using namespace std;​
​
int binarySearch(int arr[], int n, int target) {​
    int left = 0;​
    int right = ______;  // ① 补全右边界初始值（4分）​
    while (______) {     // ② 补全循环条件（4分）​
        int mid = left + (right - left) / 2;  // 避免溢出​
        if (arr[mid] == target) {​
            return mid;​
        } else if (arr[mid] < target) {​
            ______;      // ③ 目标值在右侧，调整左边界（5分）​
        } else {​
            ______;      // ④ 目标值在左侧，调整右边界（5分）​
        }​
    }​
    return -1;  // 未找到​
}​
​
int main() {​
    int arr[] = {2, 5, 8, 11, 14, 17};​
    int n = sizeof(arr) / sizeof(arr[0]);​
    int target = 11;​
    cout << binarySearch(arr, n, target) << endl;​
    return 0;​
}​
​
题 2：二叉树前序遍历（递归实现）​
以下程序实现二叉树的前序遍历（根→左→右），并输出节点值。请补全代码。​
​
    // 构造函数​
    TreeNode(int x) : val(x), left(______), right(______) {}  // ① 补全初始值（6分）​
};​
​
// 前序遍历函数​
void preOrder(TreeNode* root) {​
    if (______) {  // ② 补全递归终止条件（6分）​
        return;​
    }​
    // 访问根节点​
    cout << root->val << " ";​
    // 递归遍历左子树​
    ______;  // ③ 补全左子树遍历代码（3分）​
    // 递归遍历右子树​
    ______;  // ④ 补全右子树遍历代码（3分）​
}​
​
int main() {​
    // 构建一棵简单二叉树​
    TreeNode* root = new TreeNode(1);​
    root->left = new TreeNode(2);​
    root->right = new TreeNode(3);​
    root->left->left = new TreeNode(4);​
    root->left->right = new TreeNode(5);​
    // 前序遍历​
    preOrder(root);​
    return 0;​
}​
​

 

李皓冉在2025-09-19 21:03:02追加了内容

参考答案及解析​

一、单项选择题​

1. C（第一代计算机用电子管，第二代用晶体管）​

2. A（2024÷2 取余逆序：2024→1012→506→253→126→63→31→15→7→3→1→0，余数为 0,0,0,0,0,1,1,1,1,1,1，逆序得 11111100000）​

3. B（long long 占 8 字节，int 占 4 字节，float 占 4 字节，double 占 8 字节？注：此处需修正，long long 和 double 均为 8 字节，题目可调整选项，若严格按常见考点，选 B 或 D 均可，建议将选项 D 改为 float，避免歧义）​

4. B（0b101101=45，45>>2=11）​

5. C（A 选项完全二叉树叶子在最后一层或两层；B 选项前序 ABC，中序可能为 ABC（左子树为空）；D 选项二叉搜索树左子树小于根）​

6. B（控制器负责协调，含 PC）​

7. C（归并排序时间复杂度稳定 O (nlogn)，快速排序最坏 O (n²)）​

8. A（n 从 1000→2000，nlogn 从 1000×10→2000×11≈22000，约 2 倍）​

9. A（HTTP 属于应用层）​

10. D（栈底是最先入栈的元素）​

11. A（8 位补码中，-128 的补码是 10000000）​

12. C（A 选项 NOI 最高；B 选项初赛有理论题；D 选项 IOI 是国际竞赛）​

13. A（冒泡第一轮：3 和 1 交换→3 和 4 不换→4 和 2 交换→4 和 5 不换，结果 {1,3,2,4,5}）​

14. B（邻接表适合稀疏图，邻接矩阵适合稠密图）​

15. B（第一次 mid=2（8），8<10→left=3；第二次 mid=4（14），14>10→right=3；第三次 mid=3（11），11>10→找到，共 3 次）​

二、判断题​

1. ×（八进制前缀 “0”，十六进制前缀 “0x”）​

2. √（默认有符号 char 范围 - 128~127）​

3. √（如 x=6 (110)，x-1=5 (101)，x&(x-1)=4 (100)）​

4. √（分治核心思想）​

5. ×（Cache 速度比内存快，容量小）​

6. √（中序 + 前序 / 后序可唯一确定二叉树）​

7. ×（快速排序不稳定，归并排序稳定）​

8. √（TCP 可**连接，UDP 无连接不可**）​

9. √（无终止条件会栈溢出）​

10. √（质数的互质数是 1~n-1，共 n-1 个）​

三、阅读程序题​

题 1​

1. 功能：计算十进制数 123 的各位数字之和（2 分）​

2. 输出结果：1+2+3=6（4 分）​

题 2​

1. 斐波那契序列（前两项为 1，从第三项起为前两项和）（4 分）​

2. 输出结果：f (8)=21（斐波那契序列：1,1,2,3,5,8,13,21）（4 分）​

题 3​

1. 插入排序（从第二个元素开始，向前插入到合适位置）（4 分）​

2. 输出结果：1 2 3 5 7 8（插入排序后数组升序）（4 分）​

四、完善程序题​

题 1​

① n-1（右边界为数组最后一个元素下标）（4 分）​

② left <= right（循环条件：左边界不超过右边界）（4 分）​

③ left = mid + 1（目标在右侧，左边界右移）（5 分）​

④ right = mid - 1（目标在左侧，右边界左移）（5 分）​

题 2​

① NULL, NULL（节点初始左右子树为空）（6 分）​

② root == NULL（递归终止：根节点为空）（6 分）​

③ preOrder (root->left)（遍历左子树）（3 分）​

④ preOrder (root->right)（遍历右子树）（3 分）​