设记录的关键字(key)集合：k={24，15，39，26，18，31，05，22}，请回答： 依次取K中各值，构造一棵二叉排序树(不要求平衡)，并写出该树的前序、中序和后序遍历序列。 设Hash表表长m=16，Hash函数H(key)=(key)％13，处理冲突方法为“二次探测法”，请依次取K中各值，构造出满足所给条件的Hash表；并求出等概率条件下查找成功时的平均查找长度。 将给定的K调整成一个堆顶元素取最大值的堆(即大根堆)。
【正确答案】正确答案：(1)将关键字{24，15，39，26，18，31，05，22}依次插入构成的二叉排序树如下：
先序遍历序列：24，15，05，18，22，39，26，31 中序遍历序列：05，15，18，22，24，26，31，39 后序遍历序列：05，22，18，15，31，26，39，24 (2)各关键字通过Hash函数得到的散列地址如下表。
Key=24、15、39均没有冲突，H0(26)=0，冲突，H1(26)=0+1=1，没有冲突；Key=18没有冲突，H0(31)=5，冲突，H1(31)=5+1=6，没有冲突；H0(05)=5，冲突，H1(05)=5+1=6，冲突，H2(05)=5—1=4，没有冲突，Key=22没有冲突故各个关键字的存储地址如下表所示。
没有发生冲突的关键字，查找的比较次数为1，发生冲突的关键字，查找的比较次数为冲突次数+1，因此，等概率下的平均查找长度为： ASL=(1+1+1+2+1+2+3+1)／2=1．5次 (3)首先对以26为根的子树进行调整，调整后的结果如图b所示；对以39为根的子树进行调整，调整后的结果如图c所示；再对以15为根的子树进行调整，调整后的结果如图d所示；最后对根结点进行调整，调整后的结果如图e所示。
先序遍历序列：24，15，05，18，22，39，26，31 中序遍历序列：05，15，18，22，24，26，31，39 后序遍历序列：05，22，18，15，31，26，39，24 (2)各关键字通过Hash函数得到的散列地址如下表。Key=24、15、39均没有冲突，H0(26)=0，冲突，H1(26)=0+1=1，没有冲突；Key=18没有冲突，H0(31)=5，冲突，H1(31)=5+1=6，没有冲突；H0(05)=5，冲突，H1(05)=5+1=6，冲突，H2(05)=5—1=4，没有冲突，Key=22没有冲突故各个关键字的存储地址如下表所示。没有发生冲突的关键字，查找的比较次数为1，发生冲突的关键字，查找的比较次数为冲突次数+1，因此，等概率下的平均查找长度为： ASL=(1+1+1+2+1+2+3+1)／2=1．5次 (3)首先对以26为根的子树进行调整，调整后的结果如图b所示；对以39为根的子树进行调整，调整后的结果如图c所示；再对以15为根的子树进行调整，调整后的结果如图d所示；最后对根结点进行调整，调整后的结果如图e所示。【答案解析】