第九章 查找作业（共 100 分）一、选择题（每题 3 分，共 24 分）。1．对于二叉排序树，下面的说法（
C
）是正确的。A．二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合B．对二叉排序树进行层序遍历可得到有序序列C．用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大D．在二叉排序树中进行查找，关键字的比较次数不超过结点数的 1/22．在有 n 个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（
B
）。A．O(n)
B．O(log2n)
C．O(n*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
B．3
C．4
D．55．已知数据序列为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（
B
）。A.
4
B.
5
C.
6
D.
76．设散列表表长 m=14，散列函数 H（k）=k mod 11 。表中已有 15，38，61，84 四个元素，如果用线性探测法处理冲突，则元素 49 的存储地址是（
A
）。A.
8
B.
3
C.
5
D.
97. 平衡二叉树的查找效率呈（
C
）数量级。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
。2．利用逐点插入法建立序列(61，75，44，99，77，30，36，45)对应的二叉排序树以后，查找元素 36 要进行
4
次元素间的比较，查找序列为
61,44,30,36
。}

%PDF-1.4
%
340 0 obj
>
endobj
xref
340 49
0000000016 00000 n
0000002916 00000 n
0000003001 00000 n
0000003141 00000 n
0000003403 00000 n
0000003535 00000 n
0000003745 00000 n
0000003877 00000 n
0000004936 00000 n
0000008879 00000 n
0000008982 00000 n
0000009032 00000 n
0000009082 00000 n
0000009313 00000 n
0000011205 00000 n
0000011344 00000 n
0000011741 00000 n
0000011881 00000 n
0000012340 00000 n
0000012484 00000 n
0000012900 00000 n
0000013032 00000 n
0000013458 00000 n
0000013796 00000 n
0000014054 00000 n
0000127225 00000 n
0000127463 00000 n
0000127667 00000 n
0000174713 00000 n
0000181015 00000 n
0000181248 00000 n
0000181595 00000 n
0000208043 00000 n
0000242562 00000 n
0000242800 00000 n
0000242994 00000 n
0000243640 00000 n
0000252850 00000 n
0000253098 00000 n
0000269765 00000 n
0000270020 00000 n
0000270271 00000 n
0000283122 00000 n
0000283385 00000 n
0000283587 00000 n
0000283962 00000 n
0000347578 00000 n
0000347958 00000 n
0000001276 00000 n
trailer
]>>
startxref
0
%%EOF
388 0 obj
>stream
xVmLSW>_^ZlQ) ]l
QJPBCdle+_hGgg?}