计算机不学数据结构,就犹如耶稣教徒不读圣经...

【数据结构】期末不挂科笔记

就着大纲去复习

简答题

1、哈夫曼树的构造、计算wpl

哈夫曼树的处理其实很简单,将所有的权值节点放入最小优先队列中,每次取队头的两个数出来,组成一棵树,这颗树就三个节点,头节点是两个子节点的权值和。然后将新形成的头节点放入原先的最小优先队列中,循环上述过程就成为了一颗哈夫曼树。

给出具体例子:

  1. 给出8个带有权值的节点

    img

  2. 将这些节点放入最小优先队列中,选择最小的两个权值节点——2、3出队,同时算出这两个节点的和为5

img

  1. 将刚刚得到的5权值节点放入初始的最小优先队列中,并再次pop出两个最小的权值节点,这次选择5、6,计算出和为11

img

  1. 重复上述操作,我们发现现在的最小优先队列的值为[7, 10, 11, 19, 21, 32],而我们这次出队的两个节点7、10都不是已经构造号的二叉树里面的节点,所以需要另外开一颗二叉树,这个树就是 17、7、10(头、左、右)

img

  1. 现在的队列中[11, 17, 19 ,21, 32],选取11、17,计算出和为28,构建28、11、17的树

img

  1. 现在的队列是[28, 32, 40],选出28、32,计算出和为60,构建60、28、32

    img

  2. 现在队列是[40, 60],就只剩两个了,和为100,构建100、40、60

    img

到此哈夫曼树构建完毕。

至于计算wpl,其实也很简单

我们画出来的哈夫曼树是可以看到层数的,wpl的值就是

A1最开始的权值数据 × A1爬到顶的步数 + A2最开始的权值数据 × A2爬到顶的步数 ...... + An最开始的权值数据 × An爬到顶的步数

什么意思呢,我们拿上面的哈夫曼树举例子

image-20210629134313841

红点标注的就是最初始的数据,乘的就是爬到顶部的步数,例如2这个权值节点,爬到100这个节点就要5步,所以乘5

2、哈希表、计算平均查找长度asl

哈希表也叫散列表

哈希表的构建方法书上右6种,重点就是直接定址

处理哈希冲突的方法也有几种:开放地址法(求余)

其中,对增量d右三种取法

  1. 线性探测再散列
  2. 平方探测再散列
  3. 随机探测再散列

image-20210629155803739

线性探测就是每一次+1

平方探测就是每次+1平方、负的1平方、2平方、负的2平方、3平方、负的3平方......以此类推

链地址法:

image-20210629155948670

asl就是

每层冲突的次数之和 / 冲突总次数

image-20210629160300456

3、最短路径

最短路径就是Dij算法和佛洛依德算法,既然老师说佛洛依德不考,那就是Dij算法了,详情见我的另一篇博客

4、堆排序、建堆

堆排序我也写过博客

5、avl树,bst树(两者出现一个)

AVL 树是一种平衡二叉树。平衡二叉树递归定义如下:

  1. 左右子树的高度差小于等于 1。
  2. 其每一个子树均为平衡二叉树。

基于这一句话,我们就可以进行判断其一棵树是否为平衡二叉了。

bst树就是二叉搜索树,avl树不需要平衡的需求,只需要满足排序大小为(左 < 头 < 右)即可

avl和bst树是动态查找,相比静态查找,有插入和删除功能。

avl的左旋右旋操作这里就得自己看了,我这边一时半会说不清。

编程题

1、二叉树的叶子节点个数(递归)

这题就比期中考试多了个判断条件——叶子节点

int LeafNodeNum(StructNode Node) {
    if (Node == NULL) {
        return 0;
    }
    if (Node->left == NULL && Node->right == NULL) {
        return 1;
    }
    return LeafNodeNum(Node->left) + LeafNodeNum(Node->right);
}

2、折半查找(二分查找)

这题目也不知道具体形式是啥

折半查找的前提是有序

关键判断条件

if (mid < search) {
    left = mid + 1;
}
else if (mid > search) {
    right = mid - 1;
}else {
    return mid;
}

填空、选择

1、排序的时间复杂度(最好、最坏、平均)

image-20210629162541936

选择排序最好的情况也需要O(n^2)

快速排序最坏情况就是倒序情况,退化成冒泡排序,时间复杂度为O(n^2)

快速排序的空间复杂度为O(logn),这是辅助栈的空间

归并排序的空间复杂度为O(n),这是辅助数组的空间

2、基数排序

基数排序的特点:从个位开始,次位优先

3、队列、栈,判断空与满

队头:front

队尾:rear

队列最大大小:M(maxsize)

循环队列空:(rear + 1) % M != front

循环队列满:(rear + 1) % M = front

循环队列长度:(front - rear + M) % M

栈顶:top

栈底:base

栈空:top = base

栈满:top - base >= stacksize

4、二叉树的性质

二叉树的三种遍历得会吧

二叉树有以下几个性质: 性质1:二叉树第i层上的结点数目最多为 2^{i-1} (i≥1)。 性质2:深度为k的二叉树至多有(2^{k})-1个结点(k≥1)。 性质3:包含n个结点的二叉树的高度至少为log2 (n+1)。 性质4:在任意一棵二叉树中,若叶子结点的个数为n0,度为2的结点数为n2,则n0=n2+1

5、图的性质

带权的图得会吧

6、kmp算法

O(m+n)

7、构建二叉树

中序遍历 + x遍历

通过两个遍历来构建二叉树得会吧

8、最小生成树

k算法和p算法的基本得会吧

详情见我的另一篇博客