资源描述：
《计算机水平考试-中级软件设计师下午试题分类模拟15》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、中级软件设计师下午试题分类模拟15试题一阅读下列说明、图和c代码，填入横线处的字句。1>[说明叮B树是一种多又平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树。(1)树中每个节点至多有m棵了树。(2)若根节点不是叶子节点，则它至少冇两棵子树。(3)除根之外的所有非叶子节点至少有[m/2]棵子树。(4)所有的非叶子节点屮包含下列数据信息：(n,Ao,A:,K2,A2,Kn,An)o其屮，=2,n)为关键字，且KjVKi+l(i=l,2,n-1),A;(i=0,1,n)为指向树根节点命指针,且指针所指了树中所有节点的关键字均小于A士所指了树中所有节点的
2、关键字均大于k”Xi为节点屮关键字的数目。(5)所有的叶子节点都岀现在同一层次上，并且不带信息(可以看作是外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空)。例如，一棵4阶E树如图1所示(节点中关键字的数目省略)。图14阶B树示例B树的阶M、bool类型、关键字类型及B树节点的定义如F：#defineM4/B树的阶/typedefenum{FALSE=0,TRUE=1}bool；typedefintElemKeyType；typedefStructBTreeNode{intnumkeys；/节点中关键字的数目/structBTreeNode
3、parent；/指向父节点的指针，树根的父节点指针为空/structBTreeNodeA[M]；/指向子树节点的指针数组/ElemgeyTypeK[M]；/★存储关键字的数组，K[0]闲置不用/}BTreeNode;^^[SearchBtree(BTreeNoderoot,ElemKeyTypeakey,BTreeNode白勺功能是：在给定的一棵M阶B树中查找关键字akey所在节点，若義到则返冋TRUE,否则返冋FALSE0其中级软件设计师下午试题分类模拟15试题一阅读下列说明、图和c代码，填入横线处的字句。1>[说明叮B树是一种多又平衡查找树。一棵m阶的B树，
4、或为空树，或为满足下列特性的m叉树。(1)树中每个节点至多有m棵了树。(2)若根节点不是叶子节点，则它至少冇两棵子树。(3)除根之外的所有非叶子节点至少有[m/2]棵子树。(4)所有的非叶子节点屮包含下列数据信息：(n,Ao,A:,K2,A2,Kn,An)o其屮，=2,n)为关键字，且KjVKi+l(i=l,2,n-1),A;(i=0,1,n)为指向树根节点命指针,且指针所指了树中所有节点的关键字均小于A士所指了树中所有节点的关键字均大于k”Xi为节点屮关键字的数目。(5)所有的叶子节点都岀现在同一层次上，并且不带信息(可以看作是外部节点或查找失败的节点，实际上
5、这些节点不存在，指向这些节点的指针为空)。例如，一棵4阶E树如图1所示(节点中关键字的数目省略)。图14阶B树示例B树的阶M、bool类型、关键字类型及B树节点的定义如F：#defineM4/B树的阶/typedefenum{FALSE=0,TRUE=1}bool；typedefintElemKeyType；typedefStructBTreeNode{intnumkeys；/节点中关键字的数目/structBTreeNodeparent；/指向父节点的指针，树根的父节点指针为空/structBTreeNodeA[M]；/指向子树节点的指针数组/ElemgeyT
6、ypeK[M]；/★存储关键字的数组，K[0]闲置不用/}BTreeNode;^^[SearchBtree(BTreeNoderoot,ElemKeyTypeakey,BTreeNode白勺功能是：在给定的一棵M阶B树中查找关键字akey所在节点，若義到则返冋TRUE,否则返冋FALSE0其屮，root是指向该M阶B树根节点的指针，参数ptr返冋akey所在节点的指针，若且key不在该B树屮,则ptr返回查找失败吋空指针所在节点的指针。例如，在图丄所示的4阶B树中查找关竝字25吋，ptr返回指向节点e的指针。注：在节点中查找关键字akey时米用二分法。函数Sea
7、rchBtree的代码女II下:boolSearchBtree(BTreeNoderoot,ElemKeyTypeakey,BTreeNodeptr){intlwzhi,mid；BTreeNodeP=root；ptr=NULL；while(p){lw=l；hi=；while(lw<=hi){mid=(lw+hi)/2；if(pfK[mid]==akey){ptr=P；returnTRUE;}elseifhi=mid-1;elselw=mid+l；}ptr=p；p=;}returnFALSE；2、[说明2]在M阶E树中插入一个关键字时，首先在最接近外部节点的某个非
8、叶了节点中增加一个关键字
