67天通过软考（二）——程序语言小结

一、有限自动机(FA)

1.在正规式中，“*”号表示任意自我连接 (eg:a*表示n>=0个a (ab)*表示n>=0个ab相连ababab...)
2.将有限自动机M转化为与其等价的正规式R的步骤：
(1)在M的转换图中加上2个状态x和y，从x用标有e的弧连接到M的所有初态节点，从M的所有终态节点用标有e的弧连接到y，从而形成一个新的有穷自动机M'。它只有一个初态x和一个终态y，显然L(M)=L(M'),L(M)表示M所能接受的字符串集
(2)逐步消去所有节点，直到只剩下x和y为止，在消节过程中逐步用正规式来标记弧，消节的规则见下图

3.(R1|R2)*=(R1*R2*)*
4.正规式不能用于描述配对或嵌套的结构
  正规式只能表示给定结构的固定次数的重复或者没有给定次数的重复
  正规式描述的每种结构都可以用上下文无关文法描述，但反之则不然
  每个正规式都有一个与其等价的NFA
5.若某DFA与NFA等价，则它们可识别的记号相同
6.NFA与DFA的区别(1)f是上的映像。对于S中的一个给定状态及输入符号，返回一个状态的集合，即当前状态的后继状态不一定是唯一确定的。
(2)有向弧上的标记可以是

二、文法

1.文法的定义：
   描述语言语法结构的形式规则称为文法。文法G是一个四元组，可表示为,其中是一个非空有限集，其每个元素称为一个终结符；是一个非空有限集，其每个元素称为非终结符。和不含公共元素。令，称V为文法G的词汇表，V中的符号称为文法符号，包括终结符和非终结符。，称为开始符号，它至少要在一条产生式中作为左部出现。P是产生式的有限集合，每个产生式是形如“”的规则，其中称为产生式的左部，且中至少含有一个非终结符；称为产生式的右部，且
正则闭包+：
闭包*：
2.文法分类(1)短语文法(0型文法)
(2)上下文相关文法(1型文法)
(3)上下文无关文法(3型文法)
(4)正规(则)文法(3型文法)
上面四种文法有包含的关系，1型文法是0型文法的一个子集，2型文法是1型文法的一个子集，3型文法是2型文法的一个子集
3.上下文无关方法G所描述的语言是从S出发推导出的仅包含T中符号的串的集合

三、其他

1.语句用于描述程序中得运算步骤、控制结构及数据传输
  语法是书写规则
  语义表示含义
  语用是关于程序与使用者之间的关系
2.为什么叫共用体呢，因为不同的数据项在内存中占用同一段存储单元，且存储单元的大小以最大空间的变量为准
3.将高级语言编译后产生的仍然是一种程序(低级语言程序，如汇编)，只有当程序调入内存执行时，逻辑地址才会转换成物理地址

67天通过软考（一）——数据结构与算法小结

一、线性表、栈、队列
1.通用的计算队列长度公式：(rear-front+QueueSize)%QueueSize

2.有序线性表顺序存储，删除一个元素平均需要移动(n-1)/2个元素

二、图
1.无向图的邻接矩阵是对应的，即图中的一条边对应邻接矩阵的2个非零元素
2.无向图：顶点i的度=邻接矩阵第i行元素的和
  有向图：出度=邻接矩阵第i行元素的和 入度=邻接矩阵第j列元素的和
3.无向图：一个顶点的度是指关联于该顶点边的数目（该顶点相邻的顶点数）
4.连通无向图：任意两点是可达的
  一个具有n个顶点的连通无向图至少有n-1条边
5.关键路径：源点到汇点权和最大的那条路径
  最早开始时间：从源点到该活动对应点的最长路径的长度
6.具有n个顶点，e条边，用邻接表存储的图，其深度优先和广度优先时间复杂度均为O(n+e)

三、霍夫曼树
1.霍夫曼树（最优二叉树）：带权路径长度最小的二叉树
2.构造算法关键步骤：在二叉树集合F中选取两颗根节点权值最小的树作为左右子树构造一颗新的二叉树（左右顺序没要求），置新的二叉树的根节点的权值为其左右子树上根节点的权值之和
3.性质：没有度为1的节点。因此n=n0+n2 n--总节点数 n0--度为0的节点个数（叶子节点） n2--度为2的节点个数 （度:节点拥有子树的个数）
4.树的带权路径长度：所有叶子节点的带权路径长度之和
  节点的带权路径长度：该节点到树根之间的路径长度*节点的权值
  路径长度：一个节点到另一个节点上有几根线
  树的路径长度：根节点到每一个节点的路径长度的和

四、二叉树

1.二叉树性质：对任意一颗二叉树，有n0=n2+1

2.完全二叉树性质：具有n个节点的完全二叉树的深度为

3.堆是一颗完全二叉树，其父节点要么都大于要么都小于子节点(子节点间顺序没要求)

  构造堆时，将对应的一维数组转化成一颗完全二叉树

4.推导遍历结果：

  前、中→后(唯一)

  中、后→前(唯一)

  前、后→不能确定一颗二叉树

5.二叉排序树（二叉查找树）：左子树上所有节点的值小于根节点的值，右子树上所有节点的值大于根节点的值

  对二叉排序树进行中序遍历可以得到一个有序序列

  目的：并不是为了排序，而是为了提高查找、插入、删除关键字的速度

  查找的比较次数=给定值的节点在二叉排序树中的层数
6.树的性质：对任意一颗树，它的总度数=节点数-1

7.不同二叉树存储方式导致的空间浪费：
  顺序存储：二叉树所占空间总数(数组)-节点数
  链式存储：指针数目
8.平衡二叉树是一种特殊的二叉排序树，它的每一个节点的左右子树高度差最多等于1
9.二叉排序树的最小高度为完全二叉树的高度最大高度为每个节点占一层为n
10.具有n个顶点的二叉树，如果用二叉链表存储，则空指针总数必定为n+1
11.树转化为二叉树时用孩子兄弟表示法
12.根节点高度算做1

五、分块索引
1.要求满足2个条件:1)块内无序 2)块间有序
2.索引项包含3个数据项：最大关键码（存储每一块中的最大关键字，好处：在它之后的下一块中得最小关键字也能比这一块中得最大的关键字大）、块长、块首指针
3.平均查找长度：
  设n个记录的数据集被平均分成m块，每个块中有t条记录，显然n=m*t

  设Lb为查找索引表的平均查找长度 =
  设Lw为块中查找记录的平均查找长度 =
  则分块索引的平均查找长度

  最佳的情况就是分的块数m=块中的记录数t

六、散列
1.线性再散列的公式为：Hi=(H(key)+di)%m 其中di=1,2,3,4,......
2.如果一个元素存入时，进行了N次散列，则相应的查找次数也为N

七、其他

1. 一维数组向二维数组转化
2. k分搜索
3. 在分支-界限算法中，通常采用广度优先搜索问题的解空间
4. 根据已知的表达式写对应的前(中、后)缀表达式
   把表达式转化为一颗二叉树，对其进行前(中、后)序遍历
   构造规则：
(1)操作数只在叶子节点上
(2)操作符是它们的根节点
(3)括号不构造到二叉树中
(4)构造树的顺序要遵循运算的顺序
5.逆波兰式就是后缀表达式
  根据中缀构造二叉树比后缀容易
  如果表达式第一位为符号，则可在前面加0 例如：-(a+b)*c-d → 0-(a+b)*c-d,且0-优先级高于*

八、堆、二叉排序树、霍夫曼树、中缀表达式小结

1.堆、二叉排序树都是从上往下构造 

  霍夫曼树和中缀表达式是从下往上构造

  堆根据给出的序列按完全二叉树的形式构造，二叉排序树构造时需考虑左右节点间关系 

2.霍夫曼树子节点小于父节点即可，不用考虑子节点之间关系

  堆小于（大于）即可，不用考虑子节点之间关系

  二叉排序树左<父<右