第八章 查找(6)

第八章 查找

载因子过大 ⑤数据元素过多
　　E ： ①线性探查法和双散列函数法 ②建溢出区法和不建溢出区法
　　　　 ③除余法和折叠法 ④拉链法和开地址法
(试题1)
　　如图所示的二叉树，有下列性质：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上一切结点的值。这是一棵__A__树。
　　现有一菲波那契数列｛an｝,a0=a1=1,ak=ak-1+ak-2,k=2,3......。若把｛a1,a2,......,a9}填入该二叉树，一般可采用__B__遍历法遍历该树上全部结点，得到由结点的值组成的从小到大顺序排列的序列。对本题给出的二叉树图形填入｛a1,......,a9｝后，其结点n8的值为__C__，根结点的值为__D__。若欲插入｛a1,......,a9｝的平均值，则应该在__E__增加一个结点。
o n1
/ \
o n2 o n3
/ \ \
o n4 o n5 o n6
/ \ \
o n7 o n8 o n9
　　供选择的答案
　　Ａ：①穿线树　　　 ②最佳查找树 ③Ｂ－树　　 　④查找树
　　Ｂ：①前序　　　　 ②中序　　　 ③后序　　　 　④广度
　　Ｃ：①３　　　　　 ②８　　　　 ③21　　　 　 ④57
　　Ｄ：①８　　　　　 ②21 ③34　　　　 ④66
　　Ｅ：①n2与n4之间 ②n6下 ③n５与n9之间 ④n9下
●已知一个线性表(38，25，74，63，52，48)，采用的散列函数为H(Key)=Key mod 7，将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 (11) ；若利用拉链法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 (12) 。
(11) A、1.5 B、1.7 C、2.0 D、2.3
(12) A、1.0 B、7/6 C、4/3 D、3/2
(试题5 )
　　在二叉排序树中，每个结点的关键码值__A__，__B__一棵二叉排序树，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序树，最佳二叉排序树在结构上的特点是__C__，__D__不是二叉排序树，__E__是最佳二叉排序树。
　　供选择的答案
A：① 比左子树所有结点的关键码值大，比右子树所有结点的关键码值小；
② 比左子树所有结点的关键
码值小，比右子树所有结点的关键码值大；
③ 比左右子树的所有结点的关键码值大 ；
④ 与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系。
　　B：① 前序遍历 ②中序（对称）遍历 ③后序遍历 ④层次遍历
　　C：① 除最