查找 补充练习.docx

一、单项选择题。 1. 已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多是（ A ）。A. 4 B. 5 C. 6 D. 72. 下列选项中，不能构成折半查找中关键字比较序列的是（ A ）。A. 500，200，450，180 B. 500，450，200，180C. 180，500，200，450 D. 180，200，500，4503. 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。A. 95,22,91,24,94,71 B. 92,20,91,34,88,35C. 21,89,77,29,36,38 D. 12,25,71,68,33,244. 在任意一棵非空二叉排序树 T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树 T3。下列关于T1与T3的叙述中，正确的是（ ）。I. 若v是T1的叶结点，则T1与T3不同II. 若v是T1的叶结点，则T1与T3相同III. 若v不是T1的叶结点，则T1与T3不同IV. 若v不是T1的叶结点，则T1与T3相同A. 仅 I、III B. 仅 I、IV C. 仅 II、III D. 仅 II、IV5. 设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。A. O(1) B. O(log2n) C. O(n) D. O(n2)6. 下列二叉排序树中，满足平衡二叉树定义的是（ ）。A. B. C. D. 7. 若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则平衡二叉树的结点总数为（ ）。A. 10 B. 20 C. 32 D. 338. 若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ ）。A. 0 B. 1 C. 2 D. 39. 在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子节点中保存的关键字分别是（ ）。. 13，48 B. 24，48 . 24，53 D. 24，9010. 若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则平衡二叉树的结点总数为（ ）。A. 10 B. 20 C. 32 D. 3311. 若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是（ ）。A. 0 B. 1 C. 2 D. 312. 现在有一棵无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。A. 根节点的度一定为2 B. 树中最小元素一定是叶节点C. 最后插入的元素一定是叶节点 D. 树中最大元素一定是无左子树13. 现在有一颗无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。A. 根节点的度一定为2 B. 树中最小元素一定是叶节点C. 最后插入的元素一定是叶节点 D. 树中最大元素一定是无左子树14. 下列叙述中，不符合m阶B树定义要求的是（ ）。A. 根节点最多有m棵子树 B. 所有叶结点都在同层上 C. 各结点内关键字均升序或降序排列 D. 叶结点之间通过指针链接 15. 已知一棵3阶B树，如图8-27所示，删除关键字78得到一棵新B树，其最右叶结点中的关键字是（ ）。4517 352555 653760 62477821图8-27 一棵3阶B树A. 60 B. 60,62 C. 62,65 D. 6516. 在一棵具有15个关键字的4阶B树中，含关键字的结点数最多是（ ）。A. 5 B. 6 C. 10 D. 1517. 在一棵高度为2的5阶B树中，所含关键字的个数最少是（ ）。A.5 B. 7 C. 8 D. 1418. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H(K)=K %9作为散列函数，则散列地址为1的元素有（ ）个。A1 B2 C3 D419. 为提高散列表的查找效率，可以采取的正确措施是（ ）。I. 增大装填因子II. 设计冲突（碰撞）少的散列函数III. 处理冲突（碰撞）时避免产生聚集现象A. 仅I B. 仅II C. 仅I、II D. 仅II、III20. 用Hash（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（ ）。A. 存储效率 B. 散列函数 C. 装填（装载）因子 D. 平均查找长度二、填空题。1. 设查找表中有100个元素，如果用折半查找法查找数据元素X，则最多需要比较 次就可以断定数据元素X是否在查找表中。2. 设一组初始记录关键字序列为（11，16，25，36，48，50，65，86，90，101，126）,则利用折半查找法查找关键字90，需要比较 次。3. 设一组初始记录关键字序列为（19，11，40，30，16，12，29），则根据这些记录关键字构造的二叉排序树的平均查找长度是 。4. 假定一个线性表为（12，23，74，55，63，40），若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为 、 、 和_。5. 向一棵B树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度 。6. 散列表中解决冲突的两种方法是 和 。三、简答题。1. 设有序顺序表中的元素依次为17，54，67，75，85，93，94，112，203，261。试画出对其进行折半查找时的二叉判定树，并计算查找成功的平均查找长度和查找不成功的平均查找长度。2. 若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列3种情况分别讨论两者在等查找概率时的平均查找长度是否相同？（1）查找失败。（2）查找成功，且表中只有一个关键字等于给定值k的记录。（3）查找成功，且表中有若干个关键字等于给定值k的记录，要求一次查找找出所有记录。3. 按照分块查找，对144个元素的表分成多少块最好？每块的最佳长度是多少？假定每块的长度为8，其平均查找长度是多少？4. 设有一个输入数据的序列是 46, 25, 78, 62, 12, 37, 70, 29 , 试画出从空树起，逐个输入各个数据而生成的二叉排序树。5. 一棵3阶B树如图8-28所示。试分别画出在插入65、15、40、30之后B树的形状。554525 3580 905060 708595图8-28 一棵3阶B树6. 一棵4阶B树如图8-29所示。试画出插入关键字87后树的形状。82 85 9061 70 7520 2535 5030 60 80图8-29 一棵4阶B树7. 假定一个文件由15个记录组成，每个记录的关键码均为整数，分别为1，4，9，16，25，225，每个数据页块存放3个记录，要求：（1）用B树组织索引，设阶m=3，依次将上述15个关键码插入B树，画出插入后的B树。（2）用B+树组织索引，设阶m=3，依次将上述15个记录插入文件中，画出插入后的整个文件的结构图（包括B+树索引）。8. 将关键字序列（7、8、11、18、9、14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key)=(key*3) mod 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。（1）请画出所构造的散列表；（2）分别计算等概率情况下，查找成功和查找不成功地平均查找长度。9. 设包含 4 个数据元素的集合 S= do，for， repeat， while，各元素的查 找概率依次为：p1=0.35，p2 = 0.15，p3=0. 15，p4=0.35。将 S 保存在一