判断题向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。( )A 对B 错

题目

判断题

向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。( )

对

错

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

相似问题和答案

第1题：

由关键字序列(12，7，36，25，18，2)构造一棵二叉排序树(初始为空，第一个关键字作为根结点插入，此后对于任意关键字，若小于根结点的关键字，则插入左子树中，若大于根结点的关键字，则插入右子树中，且左、右子树均为二叉排序树) ，该二叉排序树的高度(层数)为 ( ) 。

A. 6

B. 5

C. 4

D. 3

请帮忙给出正确答案和分析，谢谢!

正确答案：C

第2题：

某二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树一定是()。

A.空或只有一个结点.

B.完全二叉树

C.二叉排序树

D.高度等于其结点数

参考答案：D

第3题：

在二叉排序树中,即使删除一个结点后马上再插入该结点,该二叉排序树的形态也可能不同。()

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

参考答案：正确

第4题：

下列关于二叉树遍历的叙述中，正确的是(42)。

A．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序最后一个结点

B．若一个树叶是某二叉树的中序最后一个结点，则它必是该二叉树的前序最后一个结点

C．若一个结点是某二叉树的中序最后一个结点，则它必是该二叉树的前序最后一个结点

D．若一个结点是某二叉树的前序最后一个结点，则它必是该二叉树的中序最后一个结点

正确答案：B
解析：本题考查二叉树的遍历。在前序遍历得到的序列中，最后一个结点可能是右子树的最后一个右孩子叶子结点，如果这个孩子结点不存在，那么就是最后一个左孩子叶子结点。而在中序遍历得到的序列中，最后一个结点可能是右子树的最后一个右孩子叶子结点，如果这个孩子结点不存在，那么就是最后一棵右子树的根结点，所以，在中序序列中最后一个结点如果是叶子结点，那么这个结点肯定是右孩子叶子结点。因此，若一个树叶是某二叉树的前序最后一个结点，未必是该二叉树的中序最后一个结点；而若一个树叶是某二叉树的中序最后一个结点，则它必是该二叉树的前序最后一个结点。

第5题：

某二叉树的先序序列和后序序列正好相同，则该二叉树可能是______的二叉树。

A.高度大于1的左单支

B.高度大于1的右单支

C.最多只有一个结点

D.既有左孩子又有右孩子

正确答案：C

第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题：

下图所示平衡二叉树(树中任一结点的左右子树高度之差不超过1)中，结点A的右子树AR高度为h，结点B的左子树BL高度为h，结点C的左子树CL、右子树CR高度都为h-1。若在CR中插入一个结点并使得CR的高度增加1，则该二叉树(61)。

A．以B为根的子二叉树变为不平衡

B．以C为根的子二叉树变为不平衡

C．以A为根的子二叉树变为不平衡

D．仍然是平衡二叉树

正确答案：C
解析：本题考查平衡查找树。由于平衡二叉树中任一结点的左右子树高度之差不超过1，因此，若在CR中插入一个结点并使得CR的高度增加1，则结点C的左右子树高度之差为-1，同时以C为根的子树高度增加了1，所以结点B的左右子树高度之差变为-1。如此一来，A的左子树的高度为h+2、右子树的高度为h，根据定义，以A为根的子二叉树变为不平衡。

第8题：

在()中，任意一个结点的左、右子树的高度之差的绝对值不超过1。

A.完全二叉树

B.二叉排序树

C.线索二叉树

D.最优二叉树

正确答案：A

第9题：

●在 (59) 中，任意一个结点的左、右子树的高度之差的绝对值不超过 1。

(59)

A．完全二叉树

B．二叉排序树

C．线索二叉树

D．最优二叉树

正确答案：A

第10题：

从一个包含2000个结点的散列表A[1..2000]中查找结点的平均比较次数( )从一个包含200个结点的散列表B[1..200]中查找结点的平均比较次数。

A．大于

B．小于

C．等于

D．不确定

正确答案：D

向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。( )

题目

相似问题和答案

更多相关问题

相关内容