对包含n个关键码的散列表进行检索，平均检索长度为()。A.O(logn) B.O(n) C.O(nlogn) D.不直接依赖于n

题目

对包含n个关键码的散列表进行检索，平均检索长度为()。

A.O(logn)
B.O(n)
C.O(nlogn)
D.不直接依赖于n

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

设平衡二叉排序树(AVL树)的节点个数为n，则其平均检索长度为

A．O(1)

B．O(log2n)

C．O(n)

D．O(n log2n)

正确答案：B
解析：平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有节点的平衡因子只可能是-1、0和1。只要二叉树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何节点的左右子树的深度之差都不超过1，则可以证明它的深度和log₂n是同数量级的(n为节点个数)。因此，它的平均查找长度也和log₂n同数量级。

第2题：

对包含n个元素的散列表进行检索，平均检索长度（）。

A)为0(log2n)

B)为0(n)

C)为0(n﹡log2n)

D)不直接依赖于n

正确答案：D
由于散列表的一个重要特征是平均检索长度不直接依赖于元素个数n。平均检索长度不随表中元素增加而增加，而是随负载因子的增大而增加。如果安排得好，平均检索长度可以小于1．5。正是由于这个特征，散列表成为一种很受欢迎的组织线性表的方法。

第3题：

对包含n个关键字的散列表进行检索,平均检索长度是()。A)O(log2n)B)O(n)C)不直接依赖于nD)O(nlog2n)

A.A

B.B

C.C

D.D

参考答案：C

第4题：

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为

A．O(1)

B．O(log2n)

C．O(n)

D．O(n log2n)

正确答案：B
解析：平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点韵左右子树的深度之差都不超过1，则可以证明它的深度和log2n是同数量级的(N为结点个数)。因此，它的平均查找长度也和log2n同数量级。

第5题：

二叉排序树的平均检索长度与二分法检索数量级都为

A．O(nlog2n)

B．O(n2)

C．O(log2n)

D．O(n2/4)

正确答案：C
解析：二叉排序树的平均检索长度与二分法检索同量级都为O(1og2n)。

第6题：

以下方法中量级不为O（log2n）的是（）。 A．散列法检索B．二分法检索C．二叉排序树的平均检索长度 D．平衡二叉排序树的检索长度

正确答案：C
散列法的平均检索长度不依赖于n,它与负载因子有关，负载因子越大，检索时需要比较的次数就愈多

第7题：

对包含n个元素的散列表进行检索，平均检索长度

A．为O(10g2n)

B．为O(n)

C．为O(nlog2n)

D．不直接依赖于n

正确答案：D
解析：散列表搜索的基本思想是：由结点的关键码值决定结点的存储地址，即以关键码值k为自变量，通过一定的函数关系h(称为散列函数)，计算出对应的函数值h(k)来，把这个值解释为结点的存储地址，然后到相应的地址中去取要找的结点。可以得出这样的结论：平均搜索长度与元素个数无关。因此本题的答案为D。

第8题：

对包含n个元素的散列表进行检索，平均检索长度________。

A．为O(log2n)

B．为O(n)

C．为O(n*log2n)

D．不直接依赖于n

正确答案：D
解析：散列表的检索长度与散列表存储的碰撞情况有关。如果没有一个元素发生碰撞，则其平均检索长度为 O(1)；如果n个元素存储几乎都发生碰撞，则其平均检索长度为O(n)。

第9题：

下列关于散列表的叙述中，哪一条是不正确的?( )

A) 散列法的基本思想是：由结点的关键码值决定结点的存储地址

B) 好的散列函数的标准是能将关键码值均匀地分布在整个地址空间中

C) 在散列法中，处理碰撞的方法基本有两类：拉链法和除余法

D) 散列表的平均检索长度随负载因子的增大而增加

A．

B．

C．

D．

正确答案：C

第10题：

对包含n个元素的散列表进行检索，平均检索长度为（）。A．O（log2n）B．O（n）C．O（n*l og2n）D．不直接依赖于n

正确答案：D
装填因子表示散列表的装满程度，定义为散列表中节点的数目初一基本区域能容纳的节点数所得的商，平均检索长度依赖于装填因子

对包含n个关键码的散列表进行检索，平均检索长度为()。

题目

相似问题和答案

更多相关问题

相关内容