Question

设一组初始记录关键字序列为(20,18,22,16,30,19)

Answer 1

（16,18,19,20,32,22）

注：

1、第一个关键字做根结点。

2、每个关键字都与根结点比较，如果小于根结点就插入到左子树，否则插入到右子树。

等概率查找成功查找的平均查找长度的计算方法是（书上也有）：将每个记录关键字查找成功所需要的次数相加再除以记录的个数，所以题目中的平均查找长度ASL=(1+2+3+4+5+6+7)/7=4。

解释：比如从左向右查找，15关键字1次就找到，17需比较2次，18需比较3次，依次类推。

说明：顺序查找成功查找时的平均查找长度有公式：ASL=(n+1)/2

扩展资料：

根结点的深度为1。

在通信领域，根节点、叶节点之前，首先要了解一下以太网树形业务（E-TREE业务）。这种以太网业务是PTN以太网业务中的一种。E-TREE E-TREE为点到多点业务，如下图所示，业务的连通性在两个或多个点之间。这种类型的以太网业务主要应用在视频点播、银行系统等方面。

其中，客户的接入点称为UNI。E-TREE业务将UNI的属性分为根节点和叶节点，这就有如一颗大树，根可以同每一片叶联通，每一片叶也可以同根联通，但是叶与叶之间无法联通。对于E-TREE业务来说，根节点可以与其它根节点和叶节点通信。叶节点只能与根节点通信。

参考资料来源：百度百科-根结点