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