西安石油大学：《数据结构》精品课程资源（章节习题）第10章 查找

基本概念题: 10-1什么叫静态査找?什么叫动态査找?什么样的存储结构适宜于进行静态查找?什 么样的存储结构适宜于进行动态查找? 10-2什么叫平均查找长度?写出平均查找长度的定义。 10-3索引表由哪几项组成?什么叫完全索引表?怎样构造完全索引表? 10-4什么叫等长索引表?什么叫不等长索引表? 10-5为什么B树上的查找效率比二叉排序树上的查找效率高? 10-6在哈希表中,发生冲突的可能性与哪些因素有关?为什么? 复杂概念题: 10-7已知一个个数为12的数据元素序列为{Dec,Feb,Noy,Oet,June,sept, Aug Apr, Maxy,July,Jan,Mar},要求: (1)按各数据元素的顺序构造一棵二叉排序树。 (2)设各数据元素的查找概率相等,给出该二叉排序树的平均查找长度 (注:字母的大小是指字母的ASCI码数值大小) 10-8对于一棵初始为空的3阶B树,要求: (1)给出按数据元素序列{20,30,50,52,60,68,70}构造3阶B树的图示过程。 (2)给出删除关键字50和68的图示过程。 10-9设有数据元素序列{11,23,35,47,51,60,75,8890,10211,126,},用除留余数法构造哈 希表,要求 (1)设计哈希表的长度取值m。 (2)画出用开放定址法的线性探查法解决哈希冲突的哈希表结构。 (3)画出用链表法解决哈希冲突的哈希表结构 10-10有n个结点的二叉排序树共有多少种不同形态? 上机实习题: 10-11哈希表设计。仿照10.4.4节的例10-3,设计采用除留余数法哈希函数、链地址 法哈希冲突解决方法的哈希表。要求: (1)哈希表操作包括初始化操作、元素插入操作、元素删除操作、查找操作和动态空 间撤消操作。 (2)设计一个测试程序进行测试

基本概念题： 10-1 什么叫静态查找？什么叫动态查找？什么样的存储结构适宜于进行静态查找？什 么样的存储结构适宜于进行动态查找？ 10-2 什么叫平均查找长度？写出平均查找长度的定义。 10-3 索引表由哪几项组成？什么叫完全索引表？怎样构造完全索引表？ 10-4 什么叫等长索引表？什么叫不等长索引表？ 10-5 为什么 B_树上的查找效率比二叉排序树上的查找效率高？ 10-6 在哈希表中，发生冲突的可能性与哪些因素有关？为什么？ 复杂概念题： 10-7 已知一个个数为 12 的数据元素序列为{Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan, Mar}，要求： （1）按各数据元素的顺序构造一棵二叉排序树。 （2）设各数据元素的查找概率相等，给出该二叉排序树的平均查找长度。 （注：字母的大小是指字母的 ASCII 码数值大小） 10-8 对于一棵初始为空的 3 阶 B_树，要求： （1）给出按数据元素序列{20, 30, 50, 52, 60, 68, 70}构造 3 阶 B_树的图示过程。 （2）给出删除关键字 50 和 68 的图示过程。 10-9 设有数据元素序列{11,23,35,47,51,60,75,88,90,102,113,126,}，用除留余数法构造哈 希表，要求： （1）设计哈希表的长度取值 m。 （2）画出用开放定址法的线性探查法解决哈希冲突的哈希表结构。 （3）画出用链表法解决哈希冲突的哈希表结构。 10-10 有 n 个结点的二叉排序树共有多少种不同形态？ 上机实习题： 10-11 哈希表设计。仿照 10.4.4 节的例 10-3，设计采用除留余数法哈希函数、链地址 法哈希冲突解决方法的哈希表。要求： （1）哈希表操作包括初始化操作、元素插入操作、元素删除操作、查找操作和动态空 间撤消操作。 （2）设计一个测试程序进行测试