某个二叉查找树(即二叉排序树)中进行查找时,效率最差的情形是该二叉查找树是()。
A.完全二叉树
B.平衡二叉树
C.单枝树
D.满二叉树
- · 有4位网友选择 D,占比22.22%
- · 有3位网友选择 D,占比16.67%
- · 有2位网友选择 A,占比11.11%
- · 有2位网友选择 C,占比11.11%
- · 有2位网友选择 B,占比11.11%
- · 有2位网友选择 B,占比11.11%
- · 有2位网友选择 A,占比11.11%
- · 有1位网友选择 C,占比5.56%
A.完全二叉树
B.平衡二叉树
C.单枝树
D.满二叉树
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。
【说明】
二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树:
●若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值;
●若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值;
●左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构,链表结点类型定义如下:
typedefstructBiTnode{
intkey_value;/*结点的键值,为非负整数*/
structBiTnode*left,*right;/*结点的左、右子树指针*/
}*BSTree;
函数find_key(root,key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到,则返回空指针。
【函数】
BSTreefind_key(BSTreeroot,intkey)
{
if((1))
returnNULL;
else
if(key==root->key_value)
return(2);
elseif(keykey_value)
return(3);
else
return(4);
}
【问题1】
请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。
【问题2】
若某二叉查找树中有n个结点,则查找一个给定关键字时,需要比较的结点个数取决于(5).
A.n/2
B.log2n
C.log2n+l
D.n
A、顺序查找
B、折半查找
C、哈希查找
D、二叉排序树查找
E、3阶B-树查找
F、斐波那契查找
G、差值查找
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!