PAT甲级考前算法笔记

川长思鸟来 2024-04-17 21:54 40阅读 0赞

1.对完全二叉树当中的任何一个结点（设编号为x），其左孩子的编号一定是2x,  
而右子树的编号一定是2x+1,前提是根节点是1号位

2.完全二叉树可以通过建立一个大小为2^k的数组来存放所有结点的信息，其中  
k为完全二叉树的最大高度，该数组中元素存放的顺序恰好为该完全二叉树的层  
序遍历序列

3.判断某个结点是否为叶节点的标志为：该结点（记下标为root）的左子结点的  
编号root\*2大于结点总数n

4.判断某个结点是否为空结点的标志为:该结点下标root大于结点总个数n

5.对二叉查找树进行中序遍历，遍历的结果是有序的

6.对于AVL树，只要把最靠近插入结点的失衡结点调整到正常，路径上所有结点  
就都会平衡

7.并查集产生的每一个集合都是一棵树

8.dijk + dfs : dijk负责获得最短路径的前驱数组，dfs负责根据题意对最短路径  
进行相关筛选

9.如果需要用dfs获取深度，为dfs加一个depth的参数即可

10.如果给出二叉搜索树的结构和它的元素就可以还原这个数，先把元素按照从小  
到大排序，排序之后即为它的中序遍历，这时候只要直接对这个二叉树进行一次  
中序遍历即可，唯一的不同就是对已知的树中序遍历每层对根节点赋值，还原的  
时候，每层将中序遍历的一个数填入到树中

11.二叉搜索树的元素从小到大排序即为它的中序遍历

12.并查集可用于查询复杂图论中元素之间的关系，定义好father数组初始化以后，  
将可以合并的部分调用union方法即可

13.判断完全二叉树的方法：深度遍历，并且加上序号参数，例如：  
dfs(int root, int index) 如果是完全二叉树，最后一个元素的index必定为元素数  
目，如果不是完全二叉树，最后的一个元素的index将会比元素数目大

14.one-way单向的

15.二叉搜索树建树的时候如果值与根节点相同，这里统一规定放左子树

16.哈密顿图是一个无向图，由指定的起点通往指定的重点，途中经过所有节点有且只经过一次。在图论中，通常指的是哈密顿回路，即经过图中所有顶点有且只有一次，最终回到出发点。  
欧拉图：图中经过每条边有且只有一次，若最终回到出发点，则是欧拉回路。

17.根据中序和后序**建树**（不能对指针直接操作，因为树的结构还没出来，只能对左右子树一个个递归赋值，如下代码）

node* create(int inL, int inR, int postL, int postR){
        if(inL > inR || postL > postR){
            return NULL;
        }
        int k;
        for(int i = inL; i <= inR; i++){
            if(in[i] == post[postR]){
                k = i;
                break;
            }
        }
        node* root = newNode();
        root->data = post[postR];
        root->lchild = create(inL, k - 1, postL, postL + k - inL -1);
        root->rchild = create(k + 1, inR, postL + k - inL, postR - 1);
        return root;
    }

18.完全二叉树根据层序遍历序列即可构树，因为完全二叉树的根节点和它的左右子树存在以下关系：如果根节点序号为index, 左子树序号为2 \* index, 右子树序号为 2 \*index + 1  
完全二叉树可以是左子树非空，右子树为空，但反过来不行

19.用dfs从根结点遍历到叶子结点，输出每条路径：

void dfs(int index) {
        if (index * 2 > n && index * 2 + 1 > n) {
            if (index <= n) {
                for (int i = 0; i < v.size(); i++)
                    printf("%d%s", v[i], i != v.size() - 1 ? " " : "\n");
            }
        } else {
            v.push_back(a[index * 2 + 1]);
            dfs(index * 2 + 1);
            v.pop_back();
            v.push_back(a[index * 2]);
            dfs(index * 2);
            v.pop_back();
        }
    }

18.二次探测法的公式： hi=(h(key)+i\*i)％m 0≤i≤m-1 //即di=i2 即二次探测法的d并不是直接取题目的值，而需要一个遍历，遍历i加到h(key)上

for(int j = 0; j < n; j++){
          num = dig + j * j;
          if(isVisit[num % n] == 0){
              cout << num % n;
              isVisit[num % n] = 1;
              flag = 1;
              break;
          }
      }

19.当使用对大量元素使用并查集的时候，需要进行路径压缩，在findFather()方法中，获取到根节点以后，再重新走一遍x的过程，将路径上所有的点的父亲设置为x

int findFather(int x){
        int a = x;
        while(x != father[x]){
            x = father[x];
        }
        while(a != father[a]){
            int z = a;
            a = father[a];
            father[z] = x;
        }
        return x;
    }