(1)试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树,画出插入完成之 后的二叉排序树 (2)按表中元素顺序构造一棵AⅥL树,并求其在等概率情况下查找成功的平均查找长度。 12.给定表(Jan,Feb,Mar,Apr,May,Jun,Jun,Aug,Sep,Oct,Nov,Dec).设取散列函数 H(x)=_i/2_|,其中i为健值中第一个字母在英语字母表中的序号,要求 (1)画出相应的开散列表; (2)画出闭散列表(以线性探测法处理 3)分别求这两个散列表在等概率情况下查找成功与不成功时的平均査找长度。 13.已知散列函数为H(K)=Kmod12,健值序列为25,37,52,43,84,99,120,15,26 11,70,82,采用拉链法处理冲突,试构造开散列表,并计算査找成功的平均查找长度。 14.顺序查找时间为0(m),二分查找时间为0(logn),散列查找时间为0(1),为什么有高效率 的查找方法而不放弃低效率的方法 五、算法设计 1.假设线性表中结点是按健值递增的顺序存放的。试写一顺序查找法,将岗哨设在高下标 端。然后分别求出等概率情况下查找成功和不成功时的平均査找长度。 2.若线性表中各结点的査找概率不等,则可用如下策略提高顺序查找的效率:若找到指定 的结点,则将该结点和其前驱(若存在)结点交换,使得经常被查找的结点尽量位于表 的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法 (注意,查找时必须从表头开始向后扫描)。 3.试写出二分查找的递归算法。 4.试编写算法求出指定结点在给定的二叉排序树中所在的层数。 5.试编写算法,在给定的二叉排序树上找出任意两个不同结点的最近公共祖先(若在两结 点A、B中,A是B的祖先,则认为A、B的最近公共祖先就是A) 6.试写一个判别给定二叉树是否为二叉排序树的算法,设此二叉树以二叉链表作存储结构 7.试写出在二叉排序树上删除指定结点的算法。 8.在以T为根指针的AⅥL树上插入健值K的新结点,返回值为新AⅥL树的根指针。7 （1）试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成之 后的二叉排序树。 （2）按表中元素顺序构造一棵 AVL 树，并求其在等概率情况下查找成功的平均查找长度。 12．给定表（Jan,Feb,Mar,Apr,May,Jun,Jun,Aug,Sep,Oct,Nov,Dec）.设取散列函数 H(x)=|_i/2_|,其中 i 为健值中第一个字母在英语字母表中的序号，要求： （1）画出相应的开散列表； （2）画出闭散列表（以线性探测法处理）； （3）分别求这两个散列表在等概率情况下查找成功与不成功时的平均查找长度。 13．已知散列函数为 H(K)=K mod 12,健值序列为 25，37，52，43，84，99，120，15，26， 11，70，82，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。 14．顺序查找时间为 O(n),二分查找时间为 O(log2n),散列查找时间为 O(1),为什么有高效率 的查找方法而不放弃低效率的方法？ 五、算法设计 1． 假设线性表中结点是按健值递增的顺序存放的。试写一顺序查找法，将岗哨设在高下标 端。然后分别求出等概率情况下查找成功和不成功时的平均查找长度。 2． 若线性表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定 的结点，则将该结点和其前驱（若存在）结点交换，使得经常被查找的结点尽量位于表 的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法 （注意，查找时必须从表头开始向后扫描）。 3． 试写出二分查找的递归算法。 4． 试编写算法求出指定结点在给定的二叉排序树中所在的层数。 5． 试编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结 点 A、B 中，A 是 B 的祖先，则认为 A、B 的最近公共祖先就是 A）。 6． 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。 7． 试写出在二叉排序树上删除指定结点的算法。 8． 在以 T 为根指针的 AVL 树上插入健值 K 的新结点，返回值为新 AVL 树的根指针