数据结构习题课8.ppt

《数据结构习题课8.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构习题第8章第8章作业8-48-7，8-8，8-9，8-108-138-22，8-238-4设有关键词为A、B、C和D，按照不同的输入顺序，共可能组成多少种不同的二叉查找树。请画出其中高度较小的6种。参考答案以A为根的BST共5种B为第2个元素：2种C为第2个元素：1种（高度为2）D为第2个元素：2种以B为根的BST共2种（高度为2）以C为根的BST共2种（高度为2）以D为根的BST共5种（类似A）一共有14种。高度为2的有6种，为3的有8种8-7画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。参考

2、答案ASLsucc=(1+2*2+3*4+4*3)/10=29/10ASLunsucc=(5*3+6*4)/11=39/114528169710a5a8a9a10a2a1a3a6a4a73a28-8对长度为12的有序表（a1,a2,…,a12）（其中aia12,ai

3、UNSUCC＝En/(n+1)＝(3*3+4*10)/13＝49/13参考答案56391711812a6a9a11a12a3a1a4a7a5a82410a2a108-9假设按下述递归方法进行顺序表的查找：若表长n≤10，则进行顺序查找，否则进行折半查找。试画出对表长n=50的顺序表进行上述查找时，描述该查找的判定树，并求出在等概率情况下查找成功的平均查找长度。ASL=(1+2*2+3*4+(4+5+6+7+8)*8+9*3)/50=284/50参考答案26-3013-171-519-2432-3725123863144a25a38a44a1

4、2a6a18a31187-1145-5039-43a28-10已知下列关键词和它们对应的散列函数值：由此构造哈希表，用线性探测法冲突，计算平均查找长度ASL。若用拉链法解决冲突情况又如何?keyZhaoSunLiWangChenLiuZhangH(key)6574164参考答案线性探测法（假设散列表的长度是8，下标从0开始）查找成功ASL=(1*5+3*1+7*1)/7=15/7下标元素7Li6Zhao5Sun4Wang32Zhang1Chen0Liu拉链法（假设散列表长度是8，下标从0开始）查找成功ASL=(1*5+2*1+2*1)/7=

5、9/7下标指针76543Λ2Λ10ΛLiΛZhaoLiuΛSunΛWangZhangΛChenΛ合并拉链法（算法C）拉链法（假设散列表的长度是8，下标从0开始）查找成功ASL=(1*5+2*1+2*1)/7=9/7下标元素Link7Li-16Zhao35Sun-14Wang23Liu-12Zhang-11Chen-108-13已知序列(17,31,13,11,20,35,25,8,4,11,24,40,27)，请画出该序列的二叉查找树，并分别给出下列操作后的二叉查找树。（1）插入数据9（2）删除节点17（3）再删除节点13参考答案动态插入创

6、建二叉查找树：(17,31,13,11,20,35,25,8,4,11,24,40,27)171731173113173113111731131120173113112035(17,31,13,11,20,35,25,8,4,11,24,40,27)1731131120352517311311203584244027插入数据9251731131120358424402792517311311203584244027删除17251731131120358424402724203113112535844027再删除节点1324203113112

7、5358440272420311182535440278-22编写判定给定的二叉树是否是二叉查找树的算法。[提示]判定二叉树是否为二叉查找树是建立在中根遍历的框架基础下，在遍历中附设一指针pre指向当前访问节点的中根直接前驱，每访问一个节点便比较前驱节点pre和此节点是否有序，若遍历结束后各节点和其中根直接前驱均满足有序，则此二叉树为二叉查找树；否则，只要有一个节点不满足，那么此二叉树就不是二叉查找树。算法BST(t.pre,flag)/*使用中根遍历和pre指针判断t是否是二叉查找树*/B1[特判]flagTRUE.IFt=NULLTH

8、ENRETURN.B2[中根遍历]BST(left(t),pre,flag).IF(!flag)THENRETURN.IF(pre!=NULLANDdata(pre)>data(