判断题理想情况下哈希查找的等概率查找成功的平均查找长度是O（1）。（ ）A 对B 错

第1题：

第2题：

画出对长度为10的有序表进行折半查找的判定树（以序号1，2，……10表示树结点），并对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度。
（1）

（2）ASL=（1x1+2x2+3x4+4x3）/10=29/10
略

第3题：

在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度（）

• A、n/2
• B、（n-1）／2
• C、（n+1）／2
• D、n

正确答案:C

第4题：

假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度（），在查找不成功情况下的平均查找长度（）。

正确答案:20.5；41

第5题：

在最坏的情况下，查找成功时二叉排序树的平均查找长度（）

• A、小于顺序表的平均查找长度
• B、大于顺序表的平均查找长度
• C、与顺序表的平均查找长度相同
• D、无法与顺序表的平均查找长度比较

正确答案:C

第6题：

对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。

正确答案:正确

第7题：

设查找表为（20，19，24，57，68，11）。求在等概率条件下，对上述有序表成功查找的平均查找长度。

正确答案:平均查找长度=（1*1+2*2+3*3）/6=14/6

第8题：

第9题：

第10题：

第11题：

第12题：

第13题：

对长度为n的线性表进行顺序查找，在等概率情况下，平均查找长度为（）。

An

B（n+1）/2

C2n

Dn-1

B
略

第14题：

在各种查找方法中，平均查找长度ASL与结点个数n无关的查找方法是（）。

• A、顺序查找
• B、折半查找
• C、哈希查找
• D、分块查找

正确答案:C

第15题：

对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败，它们的平均查找长度是（），对于查找成功，他们的平均查找长度是（）

正确答案:不同的；相同的

第16题：

已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。

正确答案:设计哈希表的步骤为：
A.根据所选择的处理冲突的方法求出装载因子a的上界；
B.由a值设计哈希表的长度m；
C.根据关键字的特性和表长m选定合适的哈希函数。

第17题：

若有序表中关键字序列为：14，20，25，32，34，45，57，69，77，83，92。对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是（）。

• A、1
• B、2
• C、3
• D、4

正确答案:C

第18题：

长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（），查找失败时的平均查找长度是（）。

正确答案:37/12；62/13

第19题：

理想情况下哈希查找的等概率查找成功的平均查找长度是O。

正确答案:正确

第20题：

第21题：

第22题：

第23题：