csp初赛复习记录

Celenova · 2025-09-13 16:31:55 · 个人记录

::::info[Linnux]

切换目录命令cd
cd(change directory)
列出文件列表的命令 ls
ls(list)是一个非常常用的命令,用来显示当前目录下的内容.
创建目录和移除目录mkdir rmdir
mkdir(make directory)创建目录
rmdir(remove directory)移除目录
打印当前工作的目录pwd
pwd(prinlt work directory)
tail显示文件后几行的内容。
touch创建一个空文件
mv(move) 移动文件
cp(copy) 拷贝文件
rm删除文件
tar将用户所指定的文件或目录打包成一个文件

::::

欧拉回路：通过图的每一条边，最终回到起点的路径。

欧拉通路：可以不回到起点
一个自然数 n ，计算 n 的逆元用扩展欧几里得算法
有 n 个键值的哈希表查找一个元素的时间复杂O(n)
一棵 ℎ 层的完全二叉树，该树最多包含2^h−1个结点
队列是一种先进先出（FIFO）的线性结构
哈夫曼树的构造过程主要是为了实现图的广度优先搜索
散列表是一种通过散列函数将关键字映射到存储位置的数据结构
二叉树是一种每个结点最多有两个子结点的树结构
连通无向图中，完全三叉树一定可以用不超过两种颜色进行染色

10.对比常见排序算法性能

排序算法	最优时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
快速排序	O(n \log n)	O(n \log n)	O(n^2)	O(\log n)	❌ 否
归并排序	O(n \log n)	O(n \log n)	O(n \log n)	O(n)	✅ 是
堆排序	O(n \log n)	O(n \log n)	O(n \log n)	O(1)	❌ 是
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	✅ 否
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	✅ 否
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	❌ 是
希尔排序	O(n \log n)	O(n^{1.3})	O(n^2)	O(1)	❌ 否
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	✅ 是
桶排序	O(n + k)	O(n + k)	O(n^2)	O(n + k)	✅ 是
基数排序	O(d(n + k))	O(d(n + k))	O(d(n + k))	O(n + k)	✅ 是

g++ -o main main.cpp ,能将一个名为 main.cpp 的 C++ 源文件，编译并生成一个名为 main 的可执行文件
奇数个结点的树一定只有一个重心
存在环的图无法拓扑排序