2019

1. 森林、树和二叉树的遍历

• 树和森林的遍历

树、森林和二叉树遍历的对应关系

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

2. 哈夫曼树结点分析

对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值

哈夫曼树结点数 = 2n -1 = 115，n=58

3. 活动最早开始时间&最迟开始时间

• 关键路径

事件Vk最早发生时间：Ve(k)=Max{Ve(j)+Weight(Vj,Vk)}，Vk为Vj的任意后继，Weight(Vj,Vk)表示<Vj，Vk>上的权值

事件Vk最晚发生时间：Vlk = Min{Vl(j) - Weight(Vk,Vj)}

活动最早开始时间 = Vek 活动最晚开始时间 = Vl(j)- Weight(Vk,Vj)

4. 散列表查找失败

现有长度为11且初始为空的散列表HT，散列函数是 H（key）=key %7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列 87，40,30, 6,11,22,98,20依次插入 HT后，HT查找失败的平均查找长度是_

87%7 = 3 、40%7 = 5、30%7 = 2、6%7 = 0、11%7 = 1、22%7 = 1、98%7 = 5、20%7 = 6

0	1	2	3	4	5	6
	22	43	15