第八章 查找(5)

第八章 查找

位置＋1D．该中间位置／2
12．散列文件不能（　　　）
A．随机存取B．索引存取
C．按关键字存取D．直接存取
13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（　　　）
A．n/2B．n
C．n/4D．log n
10．在最坏的情况下，查找成功时二叉排序树的平均查找长度（　　　）
A．小于顺序表的平均查找长度B．大于顺序表的平均查找长度
C．与顺序表的平均查找长度相同D．无法与顺序表的平均查找长度比较
11．闭散列表中由于散列到同一个地址而引起的"堆积"现象，是由（　　　）
A．同义词之间发生冲突引起的
B．非同义词之间发生冲突引起的
C．同义词之间或非同义词之间发生冲突引起的
D．散列表"溢出"引起的
12．从外存设备的观点看，存取操作的基本单位是（　　　）
A．逻辑记录B．数据元素
C．文件D．物理记录
13．对文件进行检索操作时，每次都要从第一个记录开始的文件是（　　　）
A．顺序文件B．索引文件
C．顺序索引文件D．散列文件
5、考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上的一切结点的值。
　　现把9个数1，2，3，...8，9填入下图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是＿A＿，n2的值是＿B＿，n9的值是＿C＿。现欲把101/2放入此树，并使该树保持前述性质，增加的一个结点可以放在＿D＿或＿E＿。
o n1
/ \
o n2 o n3
/ \ \
o n4 o n5 o n6
/ \ \
o n7 o n8 o n9
供选择的答案
A～C：①1 ②2　 ③3 ④4　 ⑤5　 ⑥6　
　　　　 ⑦7　 ⑧8　 ⑨9
D、E：①n7下面 ②n8下面 ③n9下面 　 ④n6下面
⑤n1与n2之间 ⑥n2与n4之间 ⑦n5与n9之间 ⑧n3与n6之间
1、散列法存储的基本思想是根据_A_来决定_B_ , 碰撞 (冲突) 指的是_C_ , _D_越大, 发生碰撞的可能性也越大。 处理碰撞的两类主要方法是_E_。
　　供选择的答案
　　A 、B 、D ：①存储地址 ②元素的序号 ③元素个数 ④关键码值
　　　　　　　　⑤非码属性
⑥平均检索长度 ⑦负载因子 ⑧散列表空间
　　C ： ①两个元素具有相同序号
　　 ②两个元素的关键码值不同, 而非码属性相同
　　　　 ③不同关键码值对应到相同的存储地址
　　　　 ④负