Questão 425113

• Banca: COPEVE-UFAL
• Órgão: UFAL
• Ano: 2011
• Provas: COPEVE-UFAL - 2011 - UFAL - Analista de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados

Dadas as seguintes afirmações a respeito de árvores B,

I. Em uma árvore B de ordem "m" cada nó tem, no máximo, "m" filhos.

II. Em uma árvore B de ordem "m" cada nó (exceto a raíz e as folhas) tem pelo menos "m/2" filhos.

III. Árvores B precisam ser rebalanceadas frequentemente.

IV. Um nó não-folha com "k" filhos deve ter k chaves.

V. Todas as folhas aparecem no mesmo nível e carregam informação.

estão corretos os itens

• A. I e III, apenas.
• B. I, III, IV e V.
• C. I, II e V, apenas.
• D. III, IV e V, apenas.
• E. II, III e IV, apenas.

Gabarito: C

Comentários

• O item III está incorreto porque as Árvores B não precisam ser rebalanceadas como são freqüentemente as árvores de busca binária com Árvore AVL.
  E o item IV está incorreto porque um nó não-folha com "k" filhos deve ter k-1 chaves.
• Essa assertivas da questão foram retiradas da Wikipedia, porém a palavra "ordem" é usada de formas diferentes pelos autores, podendo indicar o número máximo de filhos em cada nó, ou até mesmo a ocupação mínima em cada nó.
  
  Cuidado!!
  
  http://pt.wikipedia.org/wiki/%C3%81rvore_B#Defini.C3.A7.C3.A3o
  http://www.lcc.ufrn.br/~gilles/edhtml/B_arvore/btree.htm
• Prezados,
  
  Essa questão deveria ser anulada, pois, segundo lilian Markenzon em seu livro Estruturas de dados e Algoritmos - página 160, tem-se que:
  Uma árvore B de ordem d é uma árvore ordenada que é vazia, ou que satisfaz as seguintes condições:
  
  i) a raiz é uma folha ou tem no mínimo 2 filhos;
  ii) cada nó diferente da raiz e das folhas possui no mínimo d+1 filhos;
  iii) cada nó tem no máximo 2d+1 filhos.
  
  
  Logo,
  I. Em uma árvore B de ordem "m" cada nó tem, no máximo, "m" filhos.
  // Errado, pois cada nó tem no máximo 2d + 1 filhos. 
  II. Em uma árvore B de ordem "m" cada nó (exceto a raíz e as folhas) tem pelo menos "m/2" filhos.
  //Errado, pois cada nó diferente da raiz e das folhas possui no mínimo d+1 filhos.
  III. Árvores B precisam ser rebalanceadas frequentemente.
  //Errado.
  IV. Um nó não-folha com "k" filhos deve ter k chaves.
  //Correto, pois cada página (nó), exceto a página raiz, contém no mínimo b chaves.
  V. Todas as folhas aparecem no mesmo nível e carregam informação.
  //Correto.
  
  Acredito que um bom recurso poderia anular essa questão.