数据结构1800题中集合的问题

Question

1.如果要求一个线性表既能较快的查找,又能适应动态变化的要求,则可采用的方法是
A分块法 B顺序法 C二分法 D哈希法
答案是A；哈希法不能动态变化？
2.哈希法解决冲突中，哪些方法不易产生聚集？
3.对于满足折半查找和分块查找条件的文件而言，无论它放在何种介质上，均能进行顺序查找、折半查找和分块查找。
答案是错；
4.任一查找树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。
答案是错；
5.设有关键字n=2^h-1，构成二叉排序树，每个关键字查找的概率相等，查找成功的ASL最大是N
答案是对；ASL最大应该是最差的情况吧，那平均查找长度不应该是（n+1)/2吗？
6.随着装填因子的增大，用闭哈希法解决冲突，其平均搜索长度比用开哈希法解决冲突时的平均搜索长度增长的慢。
（答案错）

Answer 1

1.如果要求一个线性表既能较快的查找,又能适应动态变化的要求,则可采用的方法是
A分块法 B顺序法 C二分法 D哈希法
答案是A；哈希法不能动态变化？哈希法在删除操作的时候，各插入操作时都不很方便。
2.哈希法解决冲突中，哪些方法不易产生聚集？链地址法，建立公共溢出区，再哈希法
3.对于满足折半查找和分块查找条件的文件而言，无论它放在何种介质上，均能进行顺序查找、折半查找和分块查找。无论它放在何种介质上，这种描述是不正确，折半查找要求是顺序存储的
答案是错；
4.任一查找树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。
答案是错；当然不对啦，如果构造的查找树刚好是一个单支树就不是小于了
5.设有关键字n=2^h-1，构成二叉排序树，每个关键字查找的概率相等，查找成功的ASL最大是N
答案是对；ASL最大应该是最差的情况，平均查找长度应该是（n+1)/2
6.随着装填因子的增大，用闭哈希法解决冲突，其平均搜索长度比用开哈希法解决冲突时的平均搜索长度增长的慢。
（答案错）教材中没说过什么闭哈希法，估计可能指的非开放地址法，这个是不一定的，装填因子由小变大时，这个中间有个临界值