数据结构个人总结2

期末考试老师出题范围对应知识点整理，都是我个人总结，考试完了链接放出来

选择题：

求叶子结点 出入度：根据两个公式N=N0+N1+N2+N3+N4、N=0xN0+1xN1+2xN2+3xN3+4xN4+1

https://www.bilibili.com/video/BV16J411b7ar?spm_id_from=333.999.0.0 17:05

树的遍历 根据排序构造二叉树：前（DLR）中（LDR）后（LRD）

https://www.bilibili.com/video/BV1Fh4112795?spm_id_from=333.999.0.0

栈（求容量）：只在一端进行插入和删除 只移动栈顶指针

队列（求操作后所在位置）：队尾rear添加 对头front删除 运动方向一致从左到右

插入移动次数

https://www.bilibili.com/video/BV1ub4y1m7Qj/?spm_id_from=autoNext

二叉树的性质：

求树结点数=总度数+1

求叶子结点数=出度为2的结点个数+1

求二叉树第i层有几个结点：2^i-1个结点（i>=1）

求结点总数：高度为h的二叉树最多有2^h-1个结点（h>=1）（也是满二叉树）

非空二叉树只有一个根节点

每个结点最多有两根子树，分为左子树和右子树

度为0的二叉树总是比度为2的结点多一个

满二叉树：每一层上面的结点均达到最大值 放满

完全二叉树：除最后一层，每一层的节点数均达到最大值，而最后一层缺少右边的若干结点

https://www.bilibili.com/video/BV1mh411977j/?spm_id_from=333.788.recommend_more_video.0

https://www.bilibili.com/video/BV1jb4y1Y7aE?from=search&seid=13235742882841991740&spm_id_from=333.337.0.0

习题：https://www.bilibili.com/video/BV11h411z7uP/?spm_id_from=autoNext

存储结构（顺序、链式）

https://www.bilibili.com/video/BV1sU4y1s7bH?from=search&seid=2240752725444453772&spm_id_from=333.337.0.0

填空题：

算法的复杂度

常熟阶O(1)

对数阶O(logN) while循环

线性阶O(n) for循环

线性对数阶O(nlogN) for循环嵌套while

平方阶O(n²) 双重for循环

立方阶O(n³) 三重for循环

n次方阶O(nⁿ) n重for循环

指数阶乘O(2^{^})

阶乘O(n!)

二分查找方法查找长度为n的线性表 O(log2n)

https://www.bilibili.com/video/BV14j411f7DJ?from=search&seid=8052655956111642084&spm_id_from=333.337.0.0

折半查找

https://www.bilibili.com/video/BV1i4411a78o?from=search&seid=14488354582126451533&spm_id_from=333.337.0.0

数组元素

算法填空题：

合并线性表

双向链表插入

交换二叉树左右孩子

void exchange(struct TreeNode *T){/*交换左右子树核心代码*/
    if(T!=NULL){
        struct TreeNode *temp;
        temp=T->left;
        T->left=T->right;
        T->right=temp;
        exchange(T->left);
        exchange(T->right);
    } 

分析题：

哈夫曼树

https://www.bilibili.com/video/BV1wX4y1M7TG?from=search&seid=10300161456078262055&spm_id_from=333.337.0.0

创建二叉排序树、中序遍历二叉树

根据数列画出二叉排序树，写出对应ASL (层数x个数)/个数

左子树所有结点小于其根结点

https://www.bilibili.com/video/BV1xy4y1e7Zj?spm_id_from=333.999.0.0

图的遍历和存储

DFS深度优先（任意选一个节点出发，一直走到底，到底还剩就往回一级跳，跳到有就是条新路，直到走完）

BFS广度优先（任意选一个节点出发，一层一层找下去，每一层有顺序讲究，取决于你前一层定义的顺序，否则会短连）

https://www.bilibili.com/video/BV1nW411h7q2?from=search&seid=10216318294847704744&spm_id_from=333.337.0.0

https://www.bilibili.com/video/BV1Ks411579J

冒泡排序

https://www.bilibili.com/video/BV13J411L72U