标签：队列 元素 J1 链表 2022 序列 排序 CSP 表达式
各题考察知识点
单选题
- 面向对象 / 面向过程（编程思想）
- 栈（根据入栈序列得到出栈序列）
- 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\) 的边
- 有向连通图最少边数
- bfs 广度优先 / dfs 深度优先，栈和队列的应用
- 深度：栈，广度：队列
- 可以用两个栈实现一个队列
- 进队放入 s1
- 出队优先取 s2 栈顶
- 如果 s2 为空，将 s1 所有元素倒入 s2，再进行出队操作
- 双向循环链表在结点
p 之后插入结点 s
- 排序稳定性
- 相同元素在排序后的相对位置是否放生改变
- 发生改变则排序算法不稳定
- 不发生改变则排序算法稳定
- 选择排序、快速排序不稳定，其他都稳定
- 进制转换（K 转 10）
- 字符串子串
- 字符串子串必须连续
- 子序列不一定连续
- 枚举子串时按照长度进行分类
- 考虑空串
- 递归
阅读程序
第一题
short：2 Bytechar：1 Byteunsigned：没有符号位- 数字前
0x：十六进制
short 和 char 互相转换时注意输出内容变化- 位运算注意转换成二进制
第二题
第三题
完善程序
第一题
- 注意程序特判 \(\sqrt{n}\) 是否为整数因子
第二题
- 根据上下文进行推断
- 弄清楚每个变量表示的东西和功能
标签：队列,
元素,
J1,
链表,
2022,
序列,
排序,
CSP,
表达式
From： https://www.cnblogs.com/winter-tide/p/17612732.html