题目
A.5
B.6
C.7
D.8
第4题
如果要根的层次为1,具有61个结点的完全二叉树的高度为(38)。
A.5
B.6
C.7
D.8
第8题
设二叉树根结点的层次编号为1,则深度为k的完全二叉树有(31)种。
A.2k
B.2k-1
C.2(k-1)
D.2k
第9题
阅读以下说明、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).
第10题
【C代码】 int lnsertBST(BSTree*rootptr,KeyType kword) /*在二叉查找树中插入一个键值为kword的结点,若插入成功返回1,否则返回0; *rootptr为二叉查找树根结点的指针 */ { BSTree p,father; (1) ; /*将father初始化为空指针*/ p=*rootptr; /*p指示二叉查找树的根节点*/ while(p&& (2) ){ /*在二叉查找树中查找键值kword的结点*/ father=p; if(kword<p->key) p=p->left; else p=p->right; } if((3) )return 0; /*二叉查找树中已包含键值kword,插入失败*/ p=(BSTree)malloc((4) ); /*创建新结点用来保存键值kword*/ If(!p)return 0; /*创建新结点失败*/ p->key=kword; p->left=NULL; p->right=NULL; If(!father) (5) =p; /*二叉查找树为空树时新结点作为树根插入*/ else if(kword<father->key) (6) ; /*作为左孩子结点插入*/ else (7) ; /*作右孩子结点插入*/ return 1; }/*InsertBST*/
为了保护您的账号安全,请在“赏学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!