违法和不良信息举报 联系客服
免费注册 登录

在等概率情况下，一棵平衡树的ASL为（）

题目

在等概率情况下，一棵平衡树的ASL为（）

  • A、O（1）
  • B、O（log2n ）
  • C、O（（log2n）2）
  • D、O（nlog2n）
如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

假设一棵平衡二叉树的每个结点都表明了平衡因子b,试设计一个算法,求平衡二叉树的高度。


参考答案：因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左(当b=1时)或右(当b=-1时)向下查找。
　　[算法描述]
　　int Height(BSTree t)
　　// 求平衡二叉树t的高度
　　{level=0;p=t;
　　while(p)
　　{level++; // 树的高度增1
　　if(p->bf<0)p=p->rchild;//bf=-1 沿右分枝向下
　　//bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存储定义
　　else p=p->lchild; //bf>=0 沿左分枝向下
　　}//while
　　return (level);//平衡二叉树的高度
　　} //算法结束

第2题：

二叉树与树都可以用二叉链表作为存储结构，二者的关系是( )。

A．一棵树可以惟一对应一棵二叉树

B．一棵二叉树惟一对应一棵树

C．一棵与树对应的二叉树左子树为空

D．二者没有确定的对应关系


正确答案：A
解析：由于二叉树和树都可用二叉链表左为存储结构，以二叉链表作为媒体可导出树与二叉树之间的一个对应关系。

第3题：

下列有关树的说法错误的是（ ）。

A)一棵树中只有一个无前驱的结点

B)一棵树的度为树中各个结点的度数之和

C)一棵树中每个结点的度数之和与边的条数相等

D)一棵树中，每个结点的度数之和等于结点总数减1


正确答案：B
一棵树的度是树中各结点的度的最大值，而不是各结点的度的和。

第4题：

长度为12的按关键字排序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的ASL值是______。

A．37/12

B．62/13

C．39/12

D．49/13


正确答案：D
解析：已知12个元素进行二分查找，查找失败的情况为13种。各种情况查找的路径长度加起来共有49次，故ASL为49/13。

第5题：

在查找算法中，可用平均查找长度(记为ASL)来衡量一个查找算法的优劣，其定义为：

此处Pi为表中第i个记录被查找的概率，Ci为查找第i个记录时同关键字比较的次数，n为表中记录数。

以下叙述中均假定每一个记录被查找的概率相等，即Pi=//n(i=1，2，…，n)。当表中的记录连续存储在一个一维数组中时，可采用顺序查找与折半查找方法(折半查找要求表是按关键字有序排列的)。顺序查找时的ASL为(19)，折半查找时的ASL为(20)。记录的关键字有序时，用二叉排序树查找记录，在最坏的情况下，ASL为(21)。当二叉排序树是一棵平衡树时，ASL为(22)。在平衡树上删除一个结点后可以通过旋转使其平衡，最坏的情形下需(23)次旋转。

A．O(1)

B．O(log2n)

C．O(log2n2)

D．O(nlog2n)

E．O(n)


正确答案：E

第6题：

折半查找所对应的判定树是一棵理想平衡树。()

此题为判断题(对，错)。


答案：正确

第7题：

在一棵高度为5的理想平衡树中，至少含有16个结点，最多含有()个结点。

A.31

B.32

C.30

D.33


正确答案：A

第8题：

设有关键字n=2h-1,构成二叉排序树,每个关键字查找的概率相等,查找成功的ASL最大是n()

A.对

B.错


正确答案：B

第9题：

下列有关树的概念错误的是

A．一棵树中只有一个无前驱的结点

B．一棵树的度为树中各个结点的度数之和

C．一棵树中，每个结点的度数之和等于结点总数减1

D．一棵树中每个结点的度数之和与边的条数相等


正确答案：B
解析：一棵树的度是树中各结点的度的最大值，而不是各结点的度的和。

第10题：

m阶B-树是一棵()。

A.m叉排序树
B.m叉平衡排序树
C.m-l叉平衡排序树
D.m+l叉平衡排序树

答案：B
解析：
B-树又叫多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。B-树中每个结点之多有m棵子树，m就是B-树的阶。m阶B-树就是一棵m叉平衡排序树。

更多相关问题
相关内容