HASH GAME - Online Skill Game GET 300

　　习题9 一、单项选择题 1. 若查找每个元素的概率相等，则在长度为 n 的顺序表上查找任一元素的平均查找长 度为( )。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 2. 对于长度为 9 的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找 长度为( )的9 分之一。 A. 20 B. 18 C. 25 D. 22 3. 对于长度为 18 的顺序存储的有序表，若采用折半查找，则查找第15 个元素的比较 次数为( )。 A. 3 B. 4 C. 5 D. 6 4. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元 素26 的比较次数为( )。 A. 2 B. 3 C. 4 D. 5 5. 对具有n 个元素的有序表采用折半查找，则算法的时间复杂度为( )。 2 A. O(n) B. O(n ) C. O(1) D. O(log n) 2 6. 在索引查找中，若用于保存数据元素的主表的长度为n，它被均分为k 个子表，每个 子表的长度均为n/k，则索引查找的平均查找长度为( )。 A. n+k B. k+n/k C. (k+n/k)/2 D. (k+n/k)/2+1 7. 在索引查找中，若用于保存数据元素的主表的长度为 144，它被均分为12 子表，每 个子表的长度均为12，则索引查找的平均查找长度为( )。 A. 13 B. 24 C. 12 D. 79 8. 从具有 n 个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致 为( )。 2 A. O(n) B. O(1) C. O(log n) D. O(n ) 2 9. 从具有 n 个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为 ( )。 2 A. O(n) B. O(1) C. O(log n) D. O(n ) 2 10. 在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是( ) 。 A. -11 B. -22 C. 12 D. 01 11. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K% 13 计算哈希 地址，则元素64 的哈希地址为( )。 A. 4 B. 8 C. 12 D. 13 12. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7 计算哈希地 址，则哈希地址等于3 的元素个数( )。 A. 1 B. 2 C. 3 D. 4 13. 若根据查找表建立长度为m 的哈希表，采用线性探测法处理冲突，假定对一个元素 第一次计算的哈希地址为d，则下一次的哈希地址为( )。 A. d B. d+1 C. (d+1)/m D. (d+1)%m 二、填空题 1. 以顺序查找方法从长度为n 的顺序表或单链表中查找一个元素时，平均查找长度为 ________，时间复杂度为________。 2. 对长度为n 的查找表进行查找时，假定查找第i 个元素的概率为p ,查找长度（即在 i 查找过程中依次同有关元素比较的总次数）为c ，则在查找成功情况下的平均查找长度的计 i 算公式为________。 3. 假定一个顺序表的长度为40 ，并假定查找每个元素的概率都相同，则在查找成功情 况下的平均查找长度________，在查找不成功情况下的平均查找长度________。 4. 以折半查找方法从长度为 n 的有序表中查找一个元素时，平均查找长度约等于 ________的向上取整减1，时间复杂度为________。 5. 以折半查找方法在一个查找表上进行查找时，该查找表必须组织成________存储的 ________表。 6. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43 和56 元素时，其比较次数 分别为________和________。 7. 假定对长度n=50 的有序表进行折半查找，则对应的判定树高度为________，最后一 层的结点数为________。 8. 假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查 找的平均查找长度为____________。 9. 在索引查找中，假定查找表（即主表）的长度为96，被等分为8 个子表，则进行索 引查找的平均查找长度为________。 10. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定________该结点 的值，右子树上所有结点的值一定________该结点的值。 11. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个________。 12. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明 _______，若元素的值小于根结点的值，则继续向________查找，若元素的值大于根结点的 值，则继续向________查找。 13. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结 点的________插入，若元素的值大于根结点的值，则接着向根结点的________插入。 14. 根据n 个元素建立一棵二叉排序树的时间复杂度大致为________。 15. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超 过________。 16. 假定对线)进行哈希存储，采用H(K)=K % 7 作为哈希函数， 采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到________次存储冲突。 17. 假定对线)进行哈希存储，采用H(K)=K % 7 作为哈希函数， 采用线性探测法处理冲突，则平均查找长度为________。 18. 在线性表的哈希存储中，装填因子又称为装填系数，若用m 表示哈希表的长度， n 表示线性表中的元素的个数，则等于________。 19. 对线)进行哈希存储时，若选用H(K)=K % 9 作为哈希 函数，则哈希地址为0 的元素有________个，哈希地址为5 的元素有________个。 三、应用题 1. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的折 半查找判定树，求出其平均查找长度。 2. 假定一个线)，画出按线性表中元素的次序 生成的一棵二叉排序树，求出其平均查找长度。 3. 假定一个待哈希存储的线)，哈希地址空间 为HT [13]，若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈 希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。 元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 最终哈希地址 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 4. 假定一个待哈希存储的线)，哈希地 址空间为HT [12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的 哈希表，并求出平均查找长度。 四、算法设计题 1. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存 储结构，且树中结点的关键字均不同。 2. 试将折半查找的算法改写成递归算法。 习题9 参 一、单项选择题 1. D 2. A 3. B 4. C 5. D 6. D 7. A 8. C 9. A 10. A 11. C 12. B 13. D 二、填空题 n 1. (n+1)/2, O (n) 2.  p c i i i1 3. 20.5, 41 4. log (n+1)，O (log n) 2 2 5. 顺序 有序 6. 1，3 7. 6， 19 8. (n/s+s)/2+1 9. 11 10. 小于，大于 11. 有序序列 12. 查找成功，左子树，右子树 13. 左子树，右子树 14. O (nlog n) 2 15. 1 16. 5 17. 2 18. n/m 19. 3， 2 三、应用题 1. 折半查找判定树如图7-3 所示，平均查找长度等于29/10 。图7-3 中的结点与有序表中元 素的对应关系如下表所示。 5 2 8 1 3 6 7 4 9 10 7-3 1 2 3 4 5 6 7 8 9 10 15 26 34 39 45 56 58 63 74 76 2. 二叉排序树如图7-4 所示，平均查找长度等于32/10 。 38 25 52 74 16 30 68 90 54 72 图7-4 3. H(K)=K % 13 平均查找长度为 14/10，其余解答如下。 元素 32 75 29 63 48 94