一、算法的基础知识
1．用计算机解决问题的步骤：
① 分析问题
② 算法设计
③ 描述算法
④ 编程实现
从上面的求解问题过程可以看出，关键在于前三步的解决：第一步就是解决模型的数据结构，第二步是解决问题的算法，第三步是形式化地描写算法。
2．算法的定义：
算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。算法可以理解为：程序（数据处理）+ 数据结构（数据组织）。
3．算法的性质：
① 有限性
② 确定性
③ 输入输出(可以没有输入，但一定有输出)
④ 可行性
常见的算法有：穷举法、迭代法、递推法、递归法、回溯法、深度及广度搜索法、动态规划、构造法等等。
2.N-S图：
1973年，美国学者I.Nassi和B.Shneiderman提出了一种用图形表示算法的方法，称为N-S流程图。N-S图包括顺序、选择和循环三种基本结构。
3.程序设计语言：
计算机中的语言分为低级语言和高级语言，而低级语言又分为机器语言和汇编语言。
机器语言是一种CPU的指令系统，它是CPU可以识别的一系列有0和1这种二进制代码组成的指令。它依赖于机器，不同类型的计算机有不同的机器语言，机器语言的程序有许多机器指令组成，每条指令由操作码和地址码组成，数据和指令都放在不同的地址单元中。
汇编语言它是一种符号语言，为了克服机器语言固有的缺陷，20世纪50年代中期出现，将难以记忆和辨别的机器语言操作码用有意义的英文单词作为“助记符”来代替0、1进行编程。
高级语言，不再面向机器，而是接近人类的自然语言。常见的还有C/C++，Pascal,Basic,Java等。
数据类型、常量、变量及说明方法
数据类型确定了该类型数据项的表示、取值范围以及所能参与的运算。在pascal语言中，无论常量还是变量都必须属于一个确定的数据类型。
Pascal 提供了丰富的数据类型，可以分为三大类：
① 简单类型：分为标准类型（整型、实型、字符型和布尔型）和自定义类型（枚举型和子界型）
② 构造类型：分为数组类型、集合类型、记录类型和文件类型
③ 指针类型
这些数据类型中除了指针类型是动态数据类型外，其他的都是静态数据类型。另外，我们把整型、字符型、布尔型、枚举型和子界型称为顺序类型。
另：数据结构
-栈 队列
– 并查集
– 堆
– 字母树 线段树 平衡树 动态树
– 块状链表
– 后缀数组
– ……
栈
– 先进后出
* 队列
– 先进先出
* 常见的应用有哪些？
– 表达式求值
– 搜索
* 深搜
* 广搜
– 优化
* 集合用代表元表示
– representative?Getfather(x)
* 初始的时候，所有元素各自成为一个集合
– for i?1 to N
* father[i]?i
* 判断是否在同一集合
– 代表元是否相同
* return Getfather(x)=Getfather(y)
* 合并两个集合
– 将其中一集合的代表元指向另一集合代表元
* father[Getfather(x)]?y
并查集
* 如何寻找代表元？
– Getfather(x)
* if father[x]=x
– return x
* return Getfather(father[x])
* 如何优化？
– 路径压缩
* Getfather(x)
– if father[x]=x
>>return x
– father[x]?Getfather(father[x])
– return father[x]
* 用途
– 用于寻找最值
* 大根堆、小根堆
* 小根堆性质
– 是一棵完全二叉树
* i的父亲是谁？
– idiv 2
* i的左右儿子是谁？
– 2i和2i+1
– 树上的每棵子树，儿子的值不小于根
堆排序
– 建堆
– 取出根
– 删除根
– 反复取、删的过程
时间效率
– O(Nlog N)
块状数组
* 增加一下题目内容
– 询问区间最大值
– 询问区间和
– 询问区间内的和最大连续串
– 可以修改一个数
– 可以将一串连续的数变为一个值
– 可以将一串连续的数旋转一下
* 块状数组?块状链表
– 可以将一串连续的数翻转一下
可能有些难
温馨提示：答案为网友推荐，仅供参考