Questão 17917

• Banca: CESGRANRIO
• Órgão: BNDES
• Ano: 2008
• Provas: CESGRANRIO - 2008 - BNDES - Profissional Básico - Análise de Sistemas - Suporte - Janeiro
• Disciplina: Algoritmos e Estrutura de Dados

É uma propriedade das árvores balanceadas (árvores B)

• A. ter como 2 (dois) o limite inferior para o número de chaves que um nó pode conter.
• B. somente armazenar informação satélite nas folhas.
• C. as folhas poderem ter profundidades diferentes.
• D. cada nó interno dever estar pelo menos ¾ completo.
• E. não possuir limite superior para o número de chaves que um nó pode conter.

Gabarito: A

Comentários

• O limite inferior de uma árvore B não deveria ser t - 1?
• A arvore B e otimizada para sistemas que escrevem e leem blocos grandes da dados, e e mais comummente usada em bancos de dados e sistemas de arquivos.Cada no interno da arvore B contem um certo numero de chaves. Usualmente, o numero de chaves varia entre d e 2d. O fator 2 garante que os nos podem ser divididos ou recombinados. Se um no interno tem 2d nos, adicionar uma chave naquele no pode ser feito pela divisao do no com 2d chaves em dois nos com d chaves, e em seguida pela adicao da chave no no pai.
• Se o gabarito foi este, a banca está errada.Primeiro a raiz da árvore B pode ter menos de 2 nós.Depois o número de nós de uma árvore B não é fixo. O limite inferior variará dependendo da ordem da árvore. Ah! Mas e se esta for uma pergunta capciosa falando de mínimo geral de todas as árvores B? Aí também estará errado. Eis a definição do livro do Cormen:There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer t >= 2 called the minimum degree of the B-tree:a. Every node other than the root must have at least t - 1 keys. Every internal node other than the root thus has at least t children. If the tree is nonempty, the root must have at least one key.Se t >=2 e cada nó deve ter pelo menos t-1, então cada nó pode ter 1 uma chave.
• Uma B-árvore de ordem b possui as seguintes propriedades:
  
  Cada página contém no máximo 2b chaves.
  
  Cada página, exceto a página raiz, contém no mínimo b chaves.
  
  Todas as páginas folhas aparecem no mesmo nível.
• Uma árvore B de ordem "m" é uma árvore que atende as seguintes propriedades:
      Cada nó tem no máximo "m" filhos
      Cada nó (exceto a raíz e as folhas) tem pelo menos "m/2" filhos
      A raiz tem pelo menos dois filhos se ela mesma não for uma folha
      Todas as folhas aparecem no mesmo nível e carregam informação
      Um nó não-folha com "k" filhos deve ter k-1 chaves
  Fonte:  http://pt.wikipedia.org/wiki/%C3%81rvore_B

• A) ter como 2 (dois) o limite inferior para o número de chaves que um nó pode conter. Correta. Numa árvore B todos os nós (exceto a raiz) devem respeitar o número mínimo e máximo de chaves. Como a afirmativa não especificou se era raiz ou não, considerei como se fosse um nó interno qualquer.

  B) somente armazenar informação satélite nas folhas. Errado. As árvores B podem ter informação nos nós internos também, não só nas folhas.

  C) as folhas poderem ter profundidades diferentes. Errado. Numa árvore B todas as folhas estão na mesma profundidade (nível)

  D) cada nó interno dever estar pelo menos ¾ completo. Errado. Não existe essa regra.

  E) não possuir limite superior para o número de chaves que um nó pode conter. Errado. Numa árvore B, em geral, o limite máximo para o número de chaves é 2b. Sendo b o número mínimo de chaves para uma página. Logo, há limite sim.

• Árvore B

  Regra principal:

  As raiz tem no mínimo 2 e no máximo N árvores. N  é a ordem da árvore.

   

   

  Letra A