一、$B^{-}$ 树关键字

m 阶 n 层的 $B^{-}$ 树

DANGER

本文 $B^{-}$ 树关键字求法有一些错误之处，为考前总结不当，不建议学习。

最多关键字求法

$m-1$ 层关键字 $\times$ $(m^0+m^1+\dots m^{n-2})$

例： 一棵 3 阶 5 层(根为第一层，叶子为第五层)的 $B^{-}$ 树，至多有 80 个关键字。 解： $(3-1)\times (1+3+9+27)=80$

最少关键字求法

$[\frac{m}{2}]-1\text{层关键字}\times (2\times [\frac{m}{2}{]}^0+2\times [\frac{m}{2}{]}^1+2\times [\frac{m}{2}{]}^1\times [\frac{m}{2}{]}^2+2\times [\frac{m}{2}{]}^1\dots [\frac{m}{2}{]}^{n-3})+1\text{(其中，t 向上取整)}$

例： 一棵 3 阶 5 层(根为第一层，叶子为第五层)的 $B^{-}$ 树，至多有 80 个关键字。 解： $([3/2]-1)\times (2+2\times 2+4\times 2)+1=15$

二、树的度与边的关系

树的度为子节点数，这里与离散数学所讲的不同

1. 各节点度数和为边数，因为叶子节点度为 0

2. $\sum \mathrm{度}=\sum \mathrm{边}=\mathrm{节}\mathrm{点}\mathrm{总}\mathrm{数}-1$

例： 一颗三叉树，度为 1 的节点有 4 个，度为 2 的节点为 5 个，度为 3 的节点为 6 个，问度为 0 的节点数是多少？ 解： $1\times 4+2\times 5+3\times 6=4+5+6+l-1$$l=18$

三、哈希表

除留余数法是 $H(key)=key\mathrm{\%}p$，$p$ 为比表长小的质数。

散列处理冲突是 $H_i=(H(key)+d_i)\mathrm{\%}m$，$m$ 是表长，这样才能保证整个表被覆盖满。

四、迪杰斯特拉算法

画表

序号	路径	B	C	D	E	F
初始		20	16	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$
1
2

五、二叉树根据遍历画形状

前序或后序遍历确定根节点

中序遍历确定左右子树

六、快速排序

每选一个枢轴，就执行一轮，以递归的层次逐级深入。

七、算法

单链表

typedef int ElemType;

typedef struct LNode
{
   ElemType data;
   struct LNode* next;
}LNode, *LinkList;

二叉树

typedef int TElemType;

typedef struct BiTNode
{
   TElemType data;                     // 数据

   struct BiTNode *lchild, *rchild;    // 左右指针

} BiTNode, *BiTree;

二叉树求带权路径长度

status func(T& root,int& depth;int& sum){
   sum+=depth*root->weight;
   func(root->left,++depth;sum);
   depth--;
   func(root->right, ++depth;sum);
}