24..以下说法错误的是 ①散列法存储的基本思想是由关键码的值决定数据的存储地址 ②散列表的结点中只包含数据元素自身的信息,不包含任何指针。 ③装填因子是散列法的一个重要参数,它反映散列表的装填程度。 ④散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法 以下说法错误的是 ①当所有的结点的权之都相等时,用这些结点构造的二叉排序树的特点是只有右子树 ②中序遍历二叉排序树的结点就可以得到排好序的结点序列。 ③任一二叉排序树的平均检查时间都小于用顺序査找法查找同样结点的线性表的平均查找时 间 ④对两棵具有相同关键字集合的而形状不同的二叉排序树,按中序遍历它们得到的序列的顺 序是一样的。 ⑤采用分块査找方法,既能实现线性表所希望的较快的查找速度,又能适应动态变化的需要 26.以下说法正确的是 ①平衡树一定是丰满树。 ②虽然信息项的序列的顺序不一样,但依次生成的二叉排序树确是一样的 ③在二叉排序树上插入新的结点时,不必移动其他结点,只需改动某个结点的指针,由空变 为非空即可。 ④在二叉排序树上删除一个结点时,不必移动其他结点,只要将该结点的父结点的相应的指 针域置空即可 27.长度为12的有序表:Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep,按折半查找 法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为()。 ①35/12 ②37/12 ③39/12 ④43/12 28.已知一采用开放地址法解决Hash表冲突,要从此Hash表中删除一个记录,正确的做法 是 ①将该元素所在的存储单元清空。 ②将该元素用一个特殊的元素代替 ③将与该元素有相同Hash地址的后继元素顺次前移一个位置 ④用与该元素有相同Hash地址的最后插入表中的元素替代 四、简答及应用 1.写出作为静态查找表存储结构的顺序表的类型定义 2.何谓二叉排序树? 3.简述开散列表的组织方式及类型定义。 4.简述闭散列表的类型定义 5.简述闭散列表解决冲突的基本思想 6.简述二次探测法解决冲突的基本思想 简述多重散列法解决冲突的基本思想 8.简述公共溢出区法解决冲突的基本思想。 9.对长度为20的有序表进行二分查找,试画出它的一棵判定树,并求等概率情况下的平均 查找长度 给定有序表 D={006,087,155,188,220,465,505,508,511,586,656,670,700,766,897,908},用二分查 找法在D中查找586,试用图示法表示出查找过程 11.给定表(19,14,22,01,66,21,83,27,56,13,10)。 66 24．．以下说法错误的是 （ ） ①散列法存储的基本思想是由关键码的值决定数据的存储地址。 ②散列表的结点中只包含数据元素自身的信息，不包含任何指针。 ③装填因子是散列法的一个重要参数，它反映散列表的装填程度。 ④散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。 25．以下说法错误的是 （ ） ①当所有的结点的权之都相等时，用这些结点构造的二叉排序树的特点是只有右子树 ②中序遍历二叉排序树的结点就可以得到排好序的结点序列。 ③任一二叉排序树的平均检查时间都小于用顺序查找法查找同样结点的线性表的平均查找时 间。 ④对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺 序是一样的。 ⑤采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要。 26．以下说法正确的是 （ ） ①平衡树一定是丰满树。 ②虽然信息项的序列的顺序不一样，但依次生成的二叉排序树确是一样的。 ③在二叉排序树上插入新的结点时，不必移动其他结点，只需改动某个结点的指针，由空变 为非空即可。 ④在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应的指 针域置空即可。 27．长度为 12 的有序表：Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep,按折半查找 法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）。 ① 35/12 ②37/12 ③39/12 ④43/12 28．已知一采用开放地址法解决 Hash 表冲突，要从此 Hash 表中删除一个记录，正确的做法 是 （ ） ①将该元素所在的存储单元清空。 ②将该元素用一个特殊的元素代替 ③将与该元素有相同 Hash 地址的后继元素顺次前移一个位置。 ④用与该元素有相同 Hash 地址的最后插入表中的元素替代。 四、简答及应用 1． 写出作为静态查找表存储结构的顺序表的类型定义。 2． 何谓二叉排序树？ 3． 简述开散列表的组织方式及类型定义。 4． 简述闭散列表的类型定义。 5． 简述闭散列表解决冲突的基本思想。 6． 简述二次探测法解决冲突的基本思想。 7． 简述多重散列法解决冲突的基本思想 8． 简述公共溢出区法解决冲突的基本思想。 9． 对长度为 20 的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均 查找长度。 10． 给定有序表 D={006,087,155,188,220,465,505,508,511,586,656,670,700,766,897,908}，用二分查 找法在 D 中查找 586，试用图示法表示出查找过程。 11．给定表（19，14，22，01，66，21，83，27，56，13，10）