SóProvas


ID
2047864
Banca
FUNRIO
Órgão
IF-PA
Ano
2016
Provas
Disciplina
Algoritmos e Estrutura de Dados

Um profissional de TI recebeu um arquivo digital, do setor de banco de dados da empresa, contendo 1.048.575 chaves numéricas distintas, para que fossem armazenadas em uma estrutura de dados do tipo árvore binária de busca. Após criar um programa para realizar a tarefa e inserir todas as chaves na estrutura, verificou-se que a árvore resultante era cheia. Diante desse resultado, é correto afirmar que a altura dessa árvore é

Alternativas
Comentários
  • Alguém poderia me ajudar a entender o cálculo feito.

  • Deixa eu me expressar melhor.

    Árvore Binária Cheia Possui a fórmula 2^(n-1) - 1

                                           A

                             B                       C                       Altura 1    2^(1+1) - 1  => 2^2 ficando 4 - 1 = 3 elementos

                      D         E             F         G                  Altura 2   2^(2+1) - 1  => 2^3 ficando 8 - 1 = 7 elementos

                  H     I     J    L      M   N     O   P              Altura 3  2^(3+1) - 1  => 2^4 ficando 16 - 1 = 15 elementos

    O exercício nos deu a quantidade de elementos, assim teremos que achar o valor de n.

    Algué poderia me ajudar com esta questão?      

     

  • Dando continuidade nos cálculos teremos:

    Assim sendo teremos 1048575 = 2^(n+1) – 1

                                    1048576 = 2^(n+1)

                                        2^20  = 2^(n+1) cortaremos o 2^

                                           20 = n+1

                                             n=19

  • Anderson, voce errou na linha 2 do seu calculo:

    1.048.575=2^(n+1) -1

    2^20 = 2^(n+1)-1 simplifica 2^

    20 = n+1 -1

    n=20

     

  • Resolvi de forma mais simples

     

    Sabendo-se que a fórmula para a quantidade de nós em uma árvore binária de busca cheia é 2^n – 1:

    1) desconsiderei o -1, pois muda muito pouco o cálculo;

    2) Sei que 2^10 = 1024. Arredondei para 1000

    3) O total de nós é um pouco mais do que 1 milhão, então, usando 2^20 temos 1024 x 1024, o que seria pouco mais do que 1000 x 1000

     

    Dentre as alternativas e por essas contas simples, pode-se concluir sem dúvidas que a altura dessa árvore é 20

  • Força Guerreiro!!!!!!