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

admin2013-09-16 79

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

选项

答案二叉排序树中第k个结点，即为二叉排序树中序序列中顺序号为k的结点，根结点的Lsize域中存放的是根结点的顺序号。要确定二叉排序树中第k个结点，先需将k与根结点的顺序号进行比较，若相等，则找到；若k小于根结点的顺序号，k继续与根的左孩子结点的顺序号比较，依次类推。(注意，右孩子结点的顺序号等于根结点的顺序号与右孩子结点的Lsize域值之和。)由于查找过程中不超过树的高度，故其算法复杂度为O(10gn)。 typedef struct Node{ int key： struct Node*l

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列对于南海诸岛的名称对应有误的一项是()。

以下古代文件起到了限制王权作用的是()。

下列条约中，哪一个是由协约国提出的灭亡土耳其的奴役性条约?()。

简述西欧经济一体化的原因、进程和意义。

试结合新民主主义革命不同历史时期的历史实际，阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。

简述苏联和南斯拉夫之间的冲突。

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

HSE管理体系中()是保证HSE表现良好的必要条件，是体系运行的基础要素。

蜗杆传动机构的装配顺序应根据具体情况而定，一般应先装（）。

下列关于骨巨细胞瘤的叙述，错误的是

A游离肼B间氨基酚C间氯二苯胺D2一甲氨基-5-氯二苯酮分解产物E乙基烟酰胺尼可刹米中的有关物质主要是合成的副产物

(　　)属于利润表项目。

设X～N(1，4)，则P(0≤X＜2)可表示为()。

公安机关权力的单向性，即公安机关权力的行使，是国家意志单向性表示，不以相对人同意与否为先决条件。()

我国解放战争时期著名的三大战役是()。

已知函数f(x，y)=，则fx(0，0)=，fy(0，0)=．

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

计算机408

学硕统考专业

下列对于南海诸岛的名称对应有误的一项是()。

以下古代文件起到了限制王权作用的是()。

下列条约中，哪一个是由协约国提出的灭亡土耳其的奴役性条约?()。

简述西欧经济一体化的原因、进程和意义。

试结合新民主主义革命不同历史时期的历史实际，阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。

简述苏联和南斯拉夫之间的冲突。

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

HSE管理体系中()是保证HSE表现良好的必要条件，是体系运行的基础要素。

蜗杆传动机构的装配顺序应根据具体情况而定，一般应先装（）。

下列关于骨巨细胞瘤的叙述，错误的是

A游离肼B间氨基酚C间氯二苯胺D2一甲氨基-5-氯二苯酮分解产物E乙基烟酰胺尼可刹米中的有关物质主要是合成的副产物

( )属于利润表项目。

设X～N(1，4)，则P(0≤X＜2)可表示为()。

公安机关权力的单向性，即公安机关权力的行使，是国家意志单向性表示，不以相对人同意与否为先决条件。()

我国解放战争时期著名的三大战役是()。

已知函数f(x，y)=，则fx(0，0)=________，fy(0，0)=________．

(　　)属于利润表项目。

已知函数f(x，y)=，则fx(0，0)=，fy(0，0)=．