CSP-J1 2022 讲解

SuperUser777 / 2023-08-07 / 原文

各题考察知识点

单选题

面向对象 / 面向过程（编程思想）
栈（根据入栈序列得到出栈序列）
int 类型指针
数组和链表的区别
栈和队列（栈先进后出，队列先进先出）
中缀表达式转前缀表达式
哈夫曼树 / 哈夫曼编码
完全二叉树编码规律
有向连通图中边的个数
bfs / dfs，栈和队列的应用
双向循环链表插入元素
排序的稳定性
K 进制转十进制
字符串子串
递归函数

阅读程序

位运算模拟、数据范围判断
用递归函数实现递推
二分+平均值求根号

完善程序

枚举整数正因子
bfs 模板

各题详细知识点

单选题

面向对象 / 面向过程
- 面向对象（类 / 结构体）
  - 封装性：将数据和函数代码捆绑到某个对象上
  - 继承性：新建一个子集（派生类），可以继承某个类的特性，并补充添加另一些
- 面向过程（函数）：按照顺序依次实现多个事件
栈：先进后出
指针
- 取地址符 &：&x 表示变量 x 的地址，可以赋值给指针变量
- 解码符 *：*p 表示指针 p 指向位置的值，可以对值进行操作
数组 / 链表
- 数组
  - 是连续的一段内存
  - 数组名表示首元素地址
  - 可以快速进行随机访问
  - 长度确定，定义后就不可发生改变
  - 每一个元素只有数据
  - 插入删除元素比较麻烦
  - 可以进行排序
- 链表
  - 在内存中不一定连续
  - head 指针指向首元素
  - 访问比较麻烦
  - 长度可以动态调整
  - 一个节点分为数据和指针域
  - 插入和删除元素比较方便
  - 可以进行排序（冒泡排序，双向链表）
元素出栈后入队再出队
- 因为队列是先进先出，那么进队序列和出队序列一样
- 出栈序列等于进队序列
- 所以出栈序列等于出队序列
前中后缀表达式
- 中缀表达式：操作符在运算数的中间
- 前缀表达式：操作符在运算数的前面
- 后缀表达式：操作符在运算数的后面
- 中缀转前缀：a+b 转 +ab，a, b 可以是字母也可以是一个表达式
哈夫曼树 / 哈夫曼编码
- 每次从序列中抽取两个最小的元素，他们共同的父节点点权是他们数值的和
- 加和完成后把和放回到序列中
- 根据左零右一规则，根据元素到根节点的简单路径对元素进行编码
用数组储存完全二叉树
- 除 \(1\) 以外，奇数编号都是右结点，偶数编号都是左节点
- 左兄弟结点，编号 \(-1\)
- 右兄弟节点，编号 \(+1\)
- 左子节点，编号 \(×2\)
- 右子节点，编号 \(×2+1\)
强连通图 / 有向连通图
- 设图的点数为 \(n\)
- 邻接矩阵（有向图）
  - 大小为 \(n×n\)
  - 如果 \(a[i][j]≠0\)，代表有一条 \(i \rightarrow j\) 的边
- 有向连通图最少边数
  - 图是一个环
  - 边数最少是 \(n\) 条
bfs 广度优先 / dfs 深度优先，栈和队列的应用
- 深度：栈，广度：队列
- 可以用两个栈实现一个队列
  - 进队放入 s1
  - 出队优先取 s2 栈顶
  - 如果 s2 为空，将 s1 所有元素倒入 s2，再进行出队操作
双向循环链表在结点 p 之后插入结点 s
- 判断后面的操作要用的变量是否被提前覆盖
- 画图判断
排序稳定性
- 相同元素在排序后的相对位置是否放生改变
  - 发生改变则排序算法不稳定
  - 不发生改变则排序算法稳定
- 选择排序、快速排序不稳定，其他都稳定
进制转换（K 转 10）
- 根据进制权重进行累加即可
字符串子串
- 字符串子串必须连续
- 子序列不一定连续
- 枚举子串时按照长度进行分类
- 考虑空串
递归
- 函数定义时自己调用自己