第九章 查找作业（共 100 分） 一、选择题（每题 3 分，共 24 分）。 1．对于二叉排序树，下面的说法（ C ）是正确的。 A．二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合 B．对二叉排序树进行层序遍历可得到有序序列 C．用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大 D．在二叉排序树中进行查找，关键字的比较次数不超过结点数的 1/2 2．在有 n 个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级 为（ B ）。 A．O(n) C．O(n*log2n) B．O(log2n) D．O(n2) 3．静态查找与动态查找的根本区别在于（ B ）。 A. 它们的逻辑结构不一样 B. 施加在其上的操作不同 C. 所包含的数据元素类型不一样 D. 存储实现不一样 4．已知一个有序表为{12，18，24，35，47，50，62，83，90，115，134}，当折半查找值 为 90 的元素时，经过（ A ）次比较后查找成功。 A．2 C．4 D．5 B．3 5．已知数据序列为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成 一棵二叉排序树，则该树的深度为（ B ）。 A. 4 D. 7 B. 5 C. 6 6．设散列表表长 m=14，散列函数 H（k）=k mod 11 。表中已有 15，38，61，84 四个元素， 如果用线性探测法处理冲突，则元素 49 的存储地址是（ A ）。 A. 8 D. 9 B. 3 C. 5 7. 平衡二叉树的查找效率呈（ C ）数量级。 A. 常数阶 B. 线性阶 C. 对数阶 D. 平方阶 8. 设输入序列为{20,11,12,…}，构造一棵平衡二叉树，当插入值为 12 的结点时发生了不平 衡，则应该进行的平衡旋转是（ B ）。 A. LL D. RR B. LR C. RL 二、填空题（每空 3 分，共 24 分）。 1．在有序表 A[1..18]中，采用二分查找算法查找元素值等于 A[7]的元素，所比较过的元素的 下标依次为 9,5,7 。 2．利用逐点插入法建立序列(61，75，44，99，77，30，36，45)对应的二叉排序树以后， 查找元素 36 要进行 4 次元素间的比较，查找序列为 61,44,30,36 。 

3. 用顺序查找法在长度为 n 的线性表中进行查找，在等概率情况下，查找成功的平均比较 次数是 n(n+1)/2 。 4. 二分查找算法描述如下： intSearch_Bin(SST ST, KT key) { low=1 ; while(low<=high) { high=ST. length; mid=(low+high)/2; if(key==ST.elem[mid].key) else if(key

为 H=key mod 13，冲突解决策略为链地址法，请构造 Hash 表（12 分），并计算平均查找长 度（3 分）。 ASL=(7*1+4*2+3)/12=18/13=1.4 3. （共 10 分）设关键字码序列{20，35，40，15，30，25}，给出平衡二叉树的构造过程。 （注：酌情给步骤分） 4. （共 15 分）设哈希表长为 m=13，散列函数为 H(k)=k mod 11，关键字序列为 5，7，16， 12，11，21，31，51，17，81；试求：散列后的表中关键字分布（假定解决冲突的方法为 线性探测再散列法）；求平均查找长度 ASL；计算该表的装填因子。 (1)按要求求哈希表（10 分）： 2 3 0 11 1 12 4 81 5 5 6 16 7 7 8 51 9 31 10 21 11 17 12 (2)计算 ASL（3 分）：ASL=17/10 (3)计算装填因子（2 分）：装填因子=10/13