二叉查找树的查找效率与二叉树的树型有关，在（）时其查找效率最低。A、结点太多B、完全二叉树C、呈单枝树D、结点太复杂

题目

二叉查找树的查找效率与二叉树的树型有关，在（）时其查找效率最低。

A、结点太多
B、完全二叉树
C、呈单枝树
D、结点太复杂

参考答案和解析

正确答案:B

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

相似问题和答案

第1题：

二叉查找树的查找效率与二叉树的树型有关，在()时其查找效率最低

A.结点太多

B.完全二叉树

C.是单枝树

D.节点太复杂

正确答案：C

第2题：

引入线索二叉树的目的是()。

A、加快查找结点的前驱或后继的速度

B、为了能方便地找到双亲

C、为了能在二叉树中方便地进行插入与删除

D、使二叉树的遍历结果唯一

参考答案：A

第3题：

线索二叉树的优点是便于在中序下查找前趋结点和后继结点。

A．错误

B．正确

参考答案：B

第4题：

二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是()。

A.先序遍历二叉树
B.判断两个指定位置的结点是否在同一层上
C.层次遍历二叉树
D.根据结点的值查找其存储位置

答案：B

解析：

第5题：

关于满二叉树、完全二叉树有以下说法：

①满二叉树不仅是一种特殊形态的二叉树，而且是一种特殊的完全二叉树。

②具有n个结点的满二叉树的高度为+1。

③具有n个结点的完全二叉树的高度为+1。

④具有n个结点的满二叉树的高度为log2(n+1)。

⑤具有n个结点的满二叉树共有叶子结点。

其中______最全面、最准确。

A．①②④

B．③④⑤

C．①③④⑤

D．全对

正确答案：D
解析：若二叉树的每一层的结点数都是最大结点数，也就是说每一层都是满的，那么此时的二叉树便成为一棵满二叉树。若二叉树除最后一层外都是满的，而且最后一层的结点都连续紧挨靠左，那么称此时的二叉树为完全二叉树。所谓的“完全”，指的是在给其结点按层次自上而下、同一层自左至右编号时，n个结点(设完全二叉树结点总数为n)与同深度的满二叉树中编号从1到n的结点一一对应。因此，①正确。显然，③是正确的。注意到，满二叉树是特殊的二叉树，因此②也正确。值得指出的是，②和③中的n分别满足不同的条件，因此，②和③都正确。设具有n个结点的满二叉树的高度为h，那么根据二叉树的性质有n=2h-1，从而有h=log2(n+1)，叶子结点的个数为n-2h-1-1=2h-1=(n+1)/2，因此④和⑤都正确。值得指出的是②和④是等价的，只是表述不同而已。综上所述，由于题干要求选最全面、最准确的，因此选D。

第6题：

已知二叉树T的结点形式为(lling,data,count,rlink),在树中查找值为X的结点,若找到,则记数(count)加1,否则,作为一个新结点插入树中,插入后仍为二叉排序树,写出其非递归算法。

参考答案：
　　[算法描述]
　　void SearchBST(BiTree &T,int target){
　　BiTree s,q,f; //以数据值target,新建结点s
　　s=new BiTNode;
　　s->data.x=target;
　　s->data.count=0;
　　s->lchild=s->rchild=NULL;
　　if(!T){
　　T=s;
　　return ;
　　} //如果该树为空则跳出该函数
　　f=NULL;
　　q=T;
　　while (q){
　　if (q->data.x==target){
　　q->data.count++;
　　return ;
　　} //如果找到该值则计数加一
　　f=q;
　　if (q->data.x>target) //如果查找值比目标值大，则为该树左孩子
　　q=q->lchild;
　　else //否则为右孩子
　　q=q->rchild;
　　} //将新结点插入树中
　　if(f->data.x>target)
　　f->lchild=s;
　　else
　　f->rchild=s;
　　}

第7题：

最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度Σwl最小的树，其中对于最优二叉树，n表示(42)；对于最优查找树，n表示(43)；构造这两种树均(44)。

A．结点数

B．叶结点数

C．非叶结点数

D．度为二的结点数

正确答案：B

第8题：

查找效率最高的二叉排序树是()。

A.所有结点的左子树都为空的二叉排序树

B.所有结点的右子树都为空的二叉排序树

C.平衡二叉树

D.没有左子树的二叉排序数

参考答案：C

第9题：

在某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是(59) 。

A.完全二叉树

B.平衡二叉树

C.单枝树

D.满二叉树

正确答案：C
本题考查数据结构基础知识。非空二叉查找树中的结点分布特点是左子树中的结点均小于树根，右子树中的结点均大于树根。因此，在二叉查找树中进行查找时，走了一条从树根出发到所找到结点的路径，到达一个空的子树则表明查找失败。根据定义，高度为h的满二叉树中有2h-l个结点，每一层上的结点数都达到最大值。完全二叉树的最高层只要求结点先占据左边的位置。例如，高度为3的满二叉树如下图(a)所示，具有6个结点的完全二叉树如下图(b)所示。在平衡二叉树中，任何一个结点的左子树高度与右子树高度之差的绝对值不大于1。单枝树中给每个结点只有1个子树。例如，具有3个结点的单枝树如下图所示。显然，在结点数确定后，二叉查找树的形态为单枝树时查找效率最差。

第10题：

某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是（59）。

A.完全二叉树
B.平衡二叉树
C.单枝树
D.满二叉树

答案：C

解析：

单枝树极度不平衡，查找的平均时间复杂度为O（N）。

二叉查找树的查找效率与二叉树的树型有关，在（）时其查找效率最低。A、结点太多B、完全二叉树C、呈单枝树D、结点太复杂

题目

参考答案和解析

相似问题和答案

更多相关问题

相关内容