一、$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$$(m-1)\times (1+m+m^2+\dots m^{n-1})$

最少关键字求法（？）

$\text{最少关键字数}=2\lceil \frac{m}{2}{\rceil }^{n-1}-1.$

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

算法

输入、输出、确定性、有限性

计算二维数组地址

已知 A[m][n] 是一个二维数组。每个元素占 d 个存储单元。起始地址为 ${\text{loc}}_0$，求分别按行序和列序为主存放时，元素 A[i][j] 的起始地址为多少.

要求 i, j 从 0 计数，如果从 1 计数，则减 1。

行优先：

$$\text{loc}={\text{loc}}_0+d\ast [n\ast i+j]$$

列优先：

$$\text{loc}={\text{loc}}_0+d\ast [m\ast j+i]$$

二、树的度与边的关系

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

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

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

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

二叉树的深度

具有 n 个节点的完全二叉树的深度为 $[{\log }_{2}n]+1$

图的性质

无向完全图具有 $\frac{n(n-1)}{2}$ 边。 有向完全图具有 $n(n-1)$ 边。

三、哈希表

除留余数法是 $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);
}