设有一棵阶m=3的B树，如图10-9所示： [图] 其中a, b, …,...

更多“设有一棵阶m=3的B树，如图10-9所示： [图] 其中a,…”相关的问题

第1题

设有一棵阶m=3的B树，如下图所示。其中a，b，…，g是结点的名称，结点内的整数为关键码。若在B树中捅入关键码55，画出插入后B树的状况，并计算完成该插入需要访问外存的次数(假定访问外存一次存取一个结点)，并具体说明每次访问外存的功能。

点击查看答案

第2题

阅读下列说明、图和C代码。

[说明5-1]

B树是一种多叉平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树：

①树中每个结点最多有m棵子树；

②若根结点不是叶子结点，则它至少有两棵子树；

⑧除根之外的所有非叶子结点至少有[m/2]棵子树；

④所有的非叶子结点中包含下列数据信息：

(n，A0，K1，A1，K2，A2， …，Kn，An)其中：Ki(i=1，2，…，n)为关键字，且Ki＜Ki+1(i=1，2，…，n-1)；Ai(i=0，1，…，n)为指向子树根结点的指针，且指针Ai-1，所指子树中所有结点的关键字均小于Ki，Ai+1，所指子树中所有结点的关键字均大于Ki，n为结点中关键字的数目。

⑤所有的叶子结点都出现在同一层次上，并且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。

例如，一棵4阶B树如下图所示(结点中关键字的数目省略)。

B树的阶M、bool类型、关键字类型及B树结点的定义如下：

define M 4 /*B树的阶*/

typedef enum {FALSE=0,TRUE=1}bool；

typedef int ElemKeyType；

typedef struct BTreeNode {

int numkeys； /*结点中关键字的数日*/

struct BTreeNode*parent； /*指向父结点的指针，树根的父结点指针为空*/

struct BTreeNode *A[M]； /*指向子树结点的指针数组*/

ElemKeyType K[M]； /*存储关键字的数组，K[0]闲置不用*/

}BTreeNode；

函数SearchBtree(BTreeNode*root，ElemKcyTypeakey,BTreeNode：*pb)的功能是：在给定的一棵M阶B树中查找关键字akey所在结点，若找到则返回TRUE，否则返回 FALSE。其中，root是指向该M阶B树根结点的指针，参数ptr返回akey所在结点的指针，若akey不在该B树中，则ptr返回查找失败时空指针所在结点的指针。例如，在上图所示的4阶B树中查找关键字25时，ptr返回指向结点e的指针。

注；在结点中查找关键字akey时采用二分法。

[函数5-1]

bool SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode **ptr)

{

int lw, hi, mid;

BTreeNode*p = root;

*ptr = NULL;

while ( p ) {

1w = 1; hi=(1);

while (1w ＜= hi) {

mid = (1w + hi)/2;

if (p -＞ K[mid] == akey) {

*ptr = p;

return TRUE;

}

else

if ((2))

hi=mid - 1;

else

1w = mid + 1;

}

*ptr = p;

p = (3);

}

return FALSE;

}

[说明5-2]

在M阶B树中插入一个关键字时，首先在最接近外部结点的某个非叶子结点中增加一个关键字，若该结点中关键字的个数不超过M-1，则完成插入；否则，要进行结点的“分裂”处理。所谓“分裂”，就是把结点中处于中间位置上的关键字取出来并插入其父结点中，然后以该关键字为分界线，把原结点分成两个结点。“分裂”过程可能会一直持续到树根，若树根结点也需要分裂，则整棵树的高度增加1。

例如，在上图所示的B树中插入关键字25时，需将其插入结点e中。由于e中已经有3个关键字，因此将关键字24插入结点e的父结点b，并以24为分界线将结点e分裂为e1和e2两个结点，结果如下图所示。

函数Isgrowing(BTreeNode*root，ElemKeyTypeakey)的功能是：判断在给定的M阶B树中插入关键字akey后，该B树的高度是否增加，若增加则返回TRUE，否则返回FALSE。其中，root是指向该M阶B树根结点的指针。

在函数Isgrwing中，首先调用函数SearchBtree(即函数5-1)查找关键字akey是否在给定的M阶B树中，若在，则返回FALSE(表明无需插入关键字akey，树的高度不会增加)；否则，通过判断结点中关键字的数目考查插入关键字akey后该B树的高度是否增加。

[函数5-2]

bool Isgrowing(BTreeNode* root, ElernKeyType akey)

{ BTreeNode *t, *f;

if( !SearchBtree((4) )

点击查看答案

第3题

在一周长为 50m的圆坛周围种树，如果每隔 5m 种一棵，共要种多少棵树?

A.9

B.10

C.11

D.12 

点击查看答案

第4题

在一周长为50m的花坛周围种树，如果每隔5m种一颗，共要种多少棵树?

A．9

B．10

C．11

D．12

点击查看答案

第5题

阅读以下说明和C语言函数，将应填入(n)处的语句写在对应栏内。

【说明】

设M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根结点的值后跟用“()”括起来的各子树的列表(若有子树的话)，各子树的列表间用“，”分隔。例如，如下图所示的三叉树可用列表a(b(c,d),e,f(g,h,i))表示。

本程序根据输入的列表生成一棵M叉树，并由M叉树再输出列表。

【函数】

include

define M 3 /*三叉树*/

typedef struct node{

int val;

struct node *subTree[M];

}NODE;

char buf[255], *str=buf;

NODE *d=NULL;

NODE *makeTree() /*由列表生成M叉树*/

{

int k; NODE *s;

s=(1);

s-＞val=*str++;

for(k=0;k＜M;k++)

s-＞subTree[k]=NULL;

if(*str=='(')

{

k=0;

do{

str++;

s-＞subTree[k]=(2);

if(*str==')')

{

str++;

break;

}

k=k+1;

}while((3));

}

return s;

}

void walkTree(NODE *t) /*由M叉树输出列表*/

{

int i;

if(t !=NULL)

{

(4);

if(t-＞subTree[0]==NULL)

return;

putchar('(');

for(i=0;i＜M;i++)

{

(5);

if(i !=M-1 && t-＞subTree[i+1]!=NULL)

putchar(',');

}

putchar(')');

}

void main()

{

printf("Enter exp: ");

scanf("%s",str);

d=makeTree();

walkTree(d);

putchar('\n');

}

点击查看答案

第6题

设某种二叉树有如下特点：结点的子树数目不是2个，则是0个。这样的一棵二叉树中有m(m＞0)个子树为0的结点时，该二叉树上的结点总数为______。

A．2m+1

B．2m-1

C．2(m-1)

D．2(m+1)

点击查看答案

第7题

阅读下列程序说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明】

设M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根节点的值部分(设为一个字符)和用“()”，括起来的各子树的列表(如有子树的话)，各子列表间用“，”分隔。例如下面的三叉树可用列表a(b(c，d)，e，f(g，h，i))表示。

本程序输入列表，生成一棵M叉树，并由M叉树输出列表。假定输入无错误。

【函数5-8】

inelude＜stdio.h＞

include＜stdlib.h＞

define M3

typedef struct node{

char val;

street node *subTree[M];

}NODE;

char buf[255], *six = buf;

NODE *d = NULL;

NODE *makeTree()/*由列表生成M叉树*/

{

int k;

NODE *s;

s=(1);

s-＞val=*six++;

for(k=0; k＜M; k++)s-＞subTree[k]=NULL;

if(*str=='('){

k=0;

do{

six++;

s-＞subTree[k]=(2);

if(*str==')'){

six++;

break;

}

k=k+1;

}while((3));

}

return s;

}

void walkTree(NODE *t)/*由M叉数输出列表*/

{

int i;

if(t !=NULL){

(4);

if(t-＞subTree[0]==NULL)return;

putchar('(');

for(i=0;i＜M; i++){

(5);

if(i !=M-1 && t-＞subTree[i+1]!=NULL)

putchar(',');

}

putchax(')');

}

void main()

{

prinff("Enter exp:");

scanf("%s", str);

d = makeTree();

walkTree(d);

putchaW',n');

}

点击查看答案

第8题

●试题五

阅读下列程序说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。

【程序5说明】

设M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根结点的值部分(设为一个字符)和用"()"括起来的各子树的列表(如有子树的话)，各子列表间用"，"分隔。例如下面的三叉树可用列表a(b(c，d)，e，f(g，h，i))表示。

本程序输入列表，生成一棵M叉树，并由M叉树输出列表。假定输入无错误。

【程序5】

#include<stdio.h>

#include<stdli

B．h>

#define M 3

typedef struct node{char val;

struct node*subTree［M］;

}NODE;

char buf［255］,*str=buf;

NODE*d=NULL

NODE*makeTree()/*由列表生成M叉树*/

{int k;NODE*s;

s= (1) ;

s->val=*str++;

for(k=0;k<M;k++)s->subTree［k］=NULL;

if(*str=′(′){

k=0;

do{str++;

s->subTree［k］= (2) ;

if(*str==′)′){str++;break;}

k=k+1;

}while( (3) );

}

return s;

}

void walkTree(NODE*t)/*由M叉树输出列表*/

{int i;

if(t!=NULL){

(4)

if(t->subTree［0］==NULL)return;

putchar(′(′);

for(i=0;i<M;i++){

(5) ;

if(i!=M-1&&t->subTree［i+1］!= NULL)

putchar(′，′)；

}

putchar(′)′)；

}

void main()

{printf("Enter exp：");

scanf("%s",str);

d=makeTree();

walkTree(d);putchar(′＼n′);

}

点击查看答案

第9题

设有一棵 3 阶 B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是

A.60

B.60, 62

C.62, 65

D.65

点击查看答案