[详细完整版]数据结构09.doc

第九章 查找习题 9.1若简单顺序查找算法所要查找的元素的下标从0开始，因而不能用监视哨，故查找 失败时要返回-1。试设计相应的算法。 9.2对有序数据表（5,7,9,12,15,18,20,22,25,30,100），按二分查找方法模拟查找 元素10和28，并分别画出其搜索过程。 9.3构造有20个元素的二分查找的判定树，并求解下列问题： （1）各元素的查找长度最大是多少？ （2）查找长度为1、2、3、4、5的元素各有多少？具体是哪些元素？（假设下标从0 开始） （3）查找第13个元素依次要比较哪些元素？ 9.4对有n个元素的有序表按二分查找方法查找时，最大的查找长度是多少？ 9.5设计算法以构造有n个元素（下标范围从1到n）的二分查找的判定树。 9.6判断题：若二叉树中每个结点的值均大于其左孩子的值，小于其右孩子的值，则 该二叉树一定是二叉排序树。 9.7分别以下列数据序列为输入构造二叉排序树，并计算出在等概率情况下的平均查 找长度。 （1）100，60，20，80，50，150，110，120，200，70，135 （2）90，80，40，160，155，50，20，30，10，