数据结构-查找

  • 折半搜索与二叉搜索树的时间性能( C
    • A. 相同 B. 完全不同 C.有时不相同 D.数量级都是$O(log_2n)$
    • 二叉搜索树也叫二叉排序树,含有n个结点的二叉排序树的AVG(Average Search Length)和树的形态有关。当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树。树的深度为n,其AVG为$\frac{n+1}{2}$(和顺序查找相同),这是最差的情况。显然,最好的情况是,二叉排序树的形态和折半查找的判定树相似,其平均查找长度和$log_2n$成正比。可以证明,就平均而言,二叉排序树的AVG仍然和$log_2n$是同数量级的。
  • 有一个表长为m的散列表,初始状态为空,现将n(n<m)个不同的关键码插入到散列表中,解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同,则探测的总次数是$ \frac{n(n-1)}{2}$。