8查找

第八章查找一、填空题(1)采用二分法进行查找的查找表，应选择____________________方式的存储结构。-(2)在各种查找法中，平均查找长度与结点个数n无关的查找方法是____________________。(3)在分块查找法中，首先查找___________________，然后再查找相应的_______________。(4)假设在有序表A[0……9]中进行二分查找，比较一次查找成功的结点数为____________，比较二次查找成功的结点数为______，比较三次查找成功的结点数为__________，比较四次查找成功的结点数为________，比较五次查找成功的结点数为___________，平均查找长度为____________________。(5)查找有序表R[0……11]中每个数据元素，假设查找在等概率情况下进行，则进行顺序查找的平均查找长度为_____________，进行二分查找的平均查找长度为____________。(6)假设在线性表R[0……59]中进行分块查找，共分10块，每块长度为6，若利用顺序查找法对索引表和子块进行查找，则查找每个元素的平均查找长度为_________________。(7)在散列存储中，装填因子a的值越大，存取数据元素时发生冲突的可能性就______，装填因子a的值越小，存取数据元素时发生冲突的可能性就____________________。(8)在一个10阶B-树中，每个分支结点所含关键字的数目最多允许为_____________，根节点最少允许为__________，其它分支节点最少允许为____________________。(9)一棵深度为h的B-树上，任一个叶子结点所处的层数为_____________，当向该B-树插入一个新元素时，为了检索插入位置需读取_________________个结点。(10)当向B-树中插入关键字时，可能引起结点___________，最终可能导致该B-树的高度___________，当从B-树中删除关键字时，可能引起结点___________，最终可能导致该B-树的高度___________。二、选择题(1)采用顺序查找法检索长度为n的线性表，则检索每个元素的平均比较次数为_____。A.nB.n/2C.(n+1)/2D.(n-1)/2(2)适于对动态查找表进行高效率查找的组织结构是_____。A.有序表B.分块有序表C.二叉排序树D.线性链表(3)对线性表进行二分查找时，要求线性表必须_____。A.键值有序的链接表B.键值有序的顺序表C.链接表但键值不一定有序D.顺序但键值不一定有序(4)有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},当用二分查找法查找键值为84的结点时，经_____比较后查找成功。A.2B.3C.4D.12(5)顺序检索一个具有n个数据元素的线性表，其时间复杂度为_____，二分检索一个具有n个数据元素的线性表，其时间复杂度为_____。A.O(n)B.O(log2n)C.O(n2)D.O(nlog2n)(6)设散列表长度为m，散列函数为H（key）=key%p，为了减少发生冲突的可能性，p应取_____。A.小于m的最大奇数B.小于m的最大素数C.小于m的最大偶数D.小于m的最大合数三、判断题(1)在等概率情况下实现分块查找，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。（）(2)删除一个排序二叉树中的一个结点，在重新插入上去，一定能得到原来的二叉排序树。（）(3)只要采用顺序存储结构存放的数据元素，都可以利用折半查找法进行查找。（）(4)二叉平衡树要求任意结点的左右子树的高度必须相等。（）（5）若二叉树中每个结点的值均大于其左孩子的值，小于其右孩子的值，则该二叉树一定是二叉排序树。四、解答题（1）已知一棵二叉排序树如下，其各结点的值虽然未知，但其中序序列为1,2,3,4,5,6,7,8,9。请标注各结点的值。(2)给定表{19,14,22,01,66,21,83,27,56,13,10}①试按元素在表中的顺序构造一棵二叉排序树；②按元素在表中的顺序构造一棵二叉平衡树。(3)已知一个长度为12的表（jan,feb,mar,apr,june,july,aug,sep,ocr,nov,dec），①试按表中元素的次序依次插入一棵初始状态为空的二叉排序树。（以字符ASCII大小为序）画出相应的二叉排序树，并求出等概率情况下的查找成功的平均查找长度；②若根据该二叉排序树对表中排序构成有序表，试求在等概率情况下查找成功的平均查找长度；③按表中元素顺序构造出一棵平衡二叉树，并求出等概率情况下查找成功的平均查找长度。(4)设有一组关键字（17，13，14，153，29，35）需插入到表长为14的散列表中，请完成一下任务：①设计一个适合该散列表的散列函数；②用设计的散列函数、利用线性探测法解决地址冲突将上述关键字插入到散列表中，画出其结构；并指出散列表的装填因子为多少。(5)现有线性表的关键字集合{33，41，20，24，30，13，01，67}共8个数据元素，已知散列函数为H(k)=(3k)%11，用开放定址法解决冲突，且d1=h(k)，di=(di-1+(7k)%10+1)%11(i=2,3,……)，①试在0～10的散列地址空间中构造散列表，并计算出等概率情况下查找成功和查找失败的平均查找长度。②采用链地址法解决地址冲突，构造哈希表，并求出等概率情况下查找成功的平均查找长度。(6)已知一个有序表（13，18，24，35，47，50，62，83，90，115，134），写出利用二分查找法查找90的过程。(7)将关键字序列26，38，12，45，73，64，30，56依次插入一棵空B-树中，从而构造一棵3阶B-树，请画出其构造过程。(8)含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的3阶B-树中至少有多少个非叶子结点？五、算法题(1)编写算法，求出指定结点在给定的二叉排序树中的层数。(2)编写一个函数，利用二分查找法在一个有序表中插入一个元素x，并保持表的有序性。(3)试设计从一个用开放地址法解决冲突的散列表中删除一个指定结点的算法。(4)已知某散列表的装填因子小于1，散列函数为H（k），是k（k为关键字）的第一个字母在字母表中的序号，采用线性探测法解决地址冲突，编写一个按字母顺序输出散列表中所有关键字的算法。(5)写出二分查找的递归算法。