数据结构第9章查找习题.ppt

1、第第9 9章章 习题课习题课 1. 1.对于对于A0.10A0.10有序表有序表, ,采用二分查找法时采用二分查找法时, ,求成求成 功和不成功时的平均查找长度功和不成功时的平均查找长度. .并对有序表并对有序表 12,18,24,35,47,50,62,83,90,115,134,12,18,24,35,47,50,62,83,90,115,134,当用二分当用二分 查找法查找查找法查找9090时时, ,需进行多少次查找可确定成功需进行多少次查找可确定成功; ; 查查 找找4747时需进行多少次查找可确定成功时需进行多少次查找可确定成功; ;查找查找100100时时, ,需需 进行多少次查找

2、才能确定不成功进行多少次查找才能确定不成功. . 解解 首先构造有序表首先构造有序表A0.10A0.10的二分查找判定树的二分查找判定树 解解 首先构造有序表首先构造有序表A0.10A0.10的二分查找判定树的二分查找判定树 5 2 8 0123456789 10 0 1 3 4 6 7 9 10 ASLsuccASLsucc= =(1(1* *1+21+2* *2+42+4* *3+43+4* *4)/114)/11=3=3 ASLunsuccASLunsucc= =(4(4* *3+83+8* *4)/124)/12=3.67=3.67 对于有序表对于有序表 5 2 8 012345678

3、910 12 18 24 35 47 50 62 83 90 115134 0 1 3 4 6 7 9 10 对于有序表对于有序表 50 2 8 012345678910 12 18 24 35 47 50 62 83 90 115134 0 1 3 4 6 7 9 10 对于有序表对于有序表 50 24 8 012345678910 12 18 24 35 47 50 62 83 90 115134 0 1 3 4 6 7 9 10 对于有序表对于有序表 50 24 90 012345678910 12 18 24 35 47 50 62 83 90 115134 12 18 35 47 6

4、2 83 115 134 查找查找9090时时, ,需进行需进行2 2次查找次查找 查找查找4747时时, ,需进行需进行4 4次查找次查找 查找查找100100时时, ,需进行需进行3 3次查找次查找 9.2 9.2 将整数序列将整数序列4,5,7,2,1,3,64,5,7,2,1,3,6中的数依次插入到中的数依次插入到 一颗空的二叉排序树中一颗空的二叉排序树中, ,度构造相应的二叉排序树度构造相应的二叉排序树, ,要求要求 用图形给出构造过程用图形给出构造过程, ,不需要编写程序不需要编写程序. . 插入插入4 4 4 插入插入5 5 4 5 插入插入7 7 4 5 7 4 5 7 2 插

5、入插入2 2 插入插入1 1 4 5 7 2 1 插入插入3 3 4 5 7 2 1 3 插入插入6 6 4 5 7 2 1 3 6 设哈希表长设哈希表长m=14,m=14,哈希函数哈希函数H(keyyH(keyy)=key mod 11)=key mod 11。表。表 中已有中已有4 4个结点个结点addr(15)=4,addr(38)=5,addr(61)=6,addr(15)=4,addr(38)=5,addr(61)=6, addr(84)=7,addr(84)=7,基余地址均为空，如用平方探查法处理冲突，基余地址均为空，如用平方探查法处理冲突， 求关键字求关键字4949的结点地址。的结点地址。 解解 h(49)=49 mod 11=5 有冲突有冲突 d1=(