在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为( )。

admin2019-08-15 33

问题在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为( )。

选项 A、O(n)
B、O(log₂n)
C、O(nlog₂n)
D、O(n²)

答案B

解析有n个结点且为完全二叉树的二叉排序树的高度为log₂n。

转载请注明原文地址:https://kaotiyun.com/show/U0Ci777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。
在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。
在一个8级中断的系统中，硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8，通过中断屏蔽技术，将中断处理优先顺序设置为1→3→5→7→2→4→6→8，如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达，CPU在按优先顺序处理到第
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。
序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。
荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。
下列叙述正确的个数是()。　1)向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
以下说法中错误的是()。
当向一棵m阶的B一树作插入操作时，若一个结点中的关键字个数等于()，则必须分裂成两个结点，当向一棵m阶的B一树作删除操作时，若一个结点中的关键字个数等于()，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。

随机试题

“人心不同，各如其面”，这句俗语体现了人格的【】
强直性脊柱炎骶髂关节X线改变中期表现特点
A.茶碱B.沙美特罗C.噻托溴铵D.孟鲁司特E.布地奈德属于M胆碱受体阻断剂的平喘药是
《公司法》规定股份有限公司的董事会成员为5~19人。董事会成员中可以有公司职工代表。()
人力资源有效性指数说法正确的是()。
担任单位会计机构负责人(会计主管人员)的，除取得会计从业资格证书外，还应当具备会计师以上专业技术职务资格或者从事会计工作2年以上经历。()
属于全木质结构建造的佛塔是()。
幽默使人如沐春风，也能解除尴尬。一个懂得幽默的人，会知道如何化解眼前的障碍。我们有时无意中让紧张代替了轻松，让严肃代替了平易，一不小心就变成了无趣的人。对这段话，理解不准确的是：
Hehastwochildren,______havebecomeworld-famousscientists.
Asabiologistandecologist,heis______allformsofhunting.

最新回复(0)

在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为( )。

计算机408

学硕统考专业

()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

以下说法中错误的是()。

当向一棵m阶的B一树作插入操作时，若一个结点中的关键字个数等于()，则必须分裂成两个结点，当向一棵m阶的B一树作删除操作时，若一个结点中的关键字个数等于()，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。

“人心不同，各如其面”，这句俗语体现了人格的【】

强直性脊柱炎骶髂关节X线改变中期表现特点

A.茶碱B.沙美特罗C.噻托溴铵D.孟鲁司特E.布地奈德属于M胆碱受体阻断剂的平喘药是

《公司法》规定股份有限公司的董事会成员为5~19人。董事会成员中可以有公司职工代表。()

人力资源有效性指数说法正确的是()。

担任单位会计机构负责人(会计主管人员)的，除取得会计从业资格证书外，还应当具备会计师以上专业技术职务资格或者从事会计工作2年以上经历。()

属于全木质结构建造的佛塔是()。

幽默使人如沐春风，也能解除尴尬。一个懂得幽默的人，会知道如何化解眼前的障碍。我们有时无意中让紧张代替了轻松，让严肃代替了平易，一不小心就变成了无趣的人。对这段话，理解不准确的是：

Hehastwochildren,______havebecomeworld-famousscientists.

Asabiologistandecologist,heis______allformsofhunting.