本章习题解答只给出算法描述,1~8题略。 1画出对长度为18的有序的顺序表进行折半查找时的判定树,并指出在等概率时查找成功的平均查 找长度,以及查找失败时所需的最多的关键字比较次数。 2已知如下所示长度为12的关键字有序的表 0)试表中元的次到一棵切始为空的2支排+,由5完成后的三排树,并求 其在等概率的情况下查找成功的平均查找长度 (2)若对表中元素先进行排序构成有序表,求在等概率的情况下查找成功的平均查找长度 (3)按表中元素的顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。 3.试推导含有12个结点的平衡二叉树的最大深度,并画出一棵这样的树。 4含有9个叶子结点的3阶B-树中至少有多少个非叶子结点?含有10个叶子结点的3阶B-树中 至少有多少个非叶子结点? 5试从空树开始,画出按以下次序向3阶B-树中插入关键码的建树过程:20,30,50,52,60, 68,70。如果此后删除50和68,画出每一步执行后3阶B-树的状态 6在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表 [Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec] (1)用线性探测开放地址法处理冲突 (2)用链地址法处理冲突。 并分别求这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。设哈希函数为H(key i/2,其中i为关键字中第一个字母在字母表中的序号。 7哈希函数H(key)=(3*key)号11。用开放定址法处理冲突,d=i((7*key)号10+1) i=1,2,3,.试在0~10的散列地址空间中对关键字序列(22,41,53,46,30,13,01,67)构 造哈希表,并求等概率情况下查找成功时的平均查找长度 8画出依次插入z,v,o,q,w,y到下图所示的5阶B-树的过程 g h k I s t u x 9将监测哨设在高下标端,改写教科书上给出的顺序查找算法。并分别求出等概率情况下查找成功和 查找失败的平均查找长度 typedef struct( KelTy yElemType typedef struct( Elem Type*elem;∥elem[中存储第一个元素 nt length s table本章习题解答只给出算法描述，1~8 题略。 ⒈画出对长度为 18 的有序的顺序表进行折半查找时的判定树，并指出在等概率时查找成功的平均查 找长度，以及查找失败时所需的最多的关键字比较次数。 ⒉已知如下所示长度为 12 的关键字有序的表： {Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec} ⑴试按表中元素的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求 其在等概率的情况下查找成功的平均查找长度。 ⑵若对表中元素先进行排序构成有序表，求在等概率的情况下查找成功的平均查找长度。 ⑶按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 ⒊试推导含有 12 个结点的平衡二叉树的最大深度，并画出一棵这样的树。 ⒋含有 9 个叶子结点的 3 阶 B–树中至少有多少个非叶子结点？含有 10 个叶子结点的 3 阶 B–树中 至少有多少个非叶子结点？ ⒌试从空树开始，画出按以下次序向 3 阶 B–树中插入关键码的建树过程：20，30，50，52，60， 68，70。如果此后删除 50 和 68，画出每一步执行后 3 阶 B–树的状态。 ⒍在地址空间为 0～16 的散列区中，对以下关键字序列构造两个哈希表： {Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec} ⑴用线性探测开放地址法处理冲突； ⑵用链地址法处理冲突。 并分别求这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。设哈希函数为 H(key) =i/2,其中 i 为关键字中第一个字母在字母表中的序号。 ⒎哈希函数 H(key)=(3*key) % 11。用开放定址法处理冲突，di=i ((7*key) % 10+1)， i=1,2,3,…。试在 0～10 的散列地址空间中对关键字序列（22，41，53，46，30， 13，01，67）构 造哈希表，并求等概率情况下查找成功时的平均查找长度。 ⒏画出依次插入 z，v，o，q，w，y 到下图所示的 5 阶 B–树的过程。 ⒐将监测哨设在高下标端，改写教科书上给出的顺序查找算法。并分别求出等概率情况下查找成功和 查找失败的平均查找长度。 typedef struct{ KeyType key ; … }ElemType; typedef struct{ ElemType *elem； // elem[1]中存储第一个元素 int length; }S_table ; j c f m r a b g h i k l n p s t u x