SóProvas


ID
2607439
Banca
FCC
Órgão
DPE-AM
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados

Certo documento possui 1 milhão de palavras não repetidas e foi editado em um editor de textos. Considerando que o editor de textos utiliza uma Árvore Binária de Busca − ABB de altura mínima para armazenar as palavras digitadas de forma a facilitar sua localização, para se localizar qualquer palavra nesta estrutura de dados serão necessárias, no máximo,

Alternativas
Comentários
  • Esta questão é fácil de ser resolvida, se tiver um calculadora.
    Busca em árvore binária tem complexidade de log na base 2.
    Pegando isso como base, já podemos eliminar a, d e, restando b e c. Aí vai da noção de cada um, já que na prova não terá um calculadora. 
    Gabarito: letra B. 
    Log 2 (1.000.000) = 19.931 ~= 20

  • Jerico Mulambo, podemos dar uma avançada a mais no seu cálculo para termos uma melhor certeza da resposta na prova sem usar uma calculadora, empregando um pouco as propriedades dos logaritmos:

     

    log 2 (1000000) = log 2 (10^6) = 6 . log 2 (10)  *

     

    Então, a que número 2 deve ser elevado para que resulte 10? Vamos pegar por aproximação 3, já que 2^3 = 8. Então, fica assim:

     

    6 . log 2 (10) = 6 . 3 ~= 18

     

    A resposta mais próxima disso é a alternativa b (20).


    Obs.: Conforme Jerico Mulambo disse, busca em árvore binária tem complexidade log 2 (n), onde 2 é a base e n é o número de elementos. Aliás, o algoritmo pesquisa binária (ou busca binária) também tem essa mesma complexidade.

     

    * Isso vem da segunte propriedade dos logaritmos: log a (b^n) = n . log a (b)

  • Busca árvore binária é log (no. de elementos) na base 2, então log 10**6 na base 2.

    Como se faz para tornar log de base 2 no log de base 10?

    Divido o log do número que quero encontrar, só que na base 10 por log de 2 na base 10

    Nesse caso específico eu tenho:

    =log 10 **6 na base 10 / log 2 na base 10

    Separadamente 1) log 10 **6 na base 10 = a que numero elevo 10 para chegar a 10 **6? resposta=6

    e 2) log 2 na base 10 é aproximadamente 3/10

    unindo 1)/2):

    = 6/3/10

    =6 * 10/3

    =60/3

    =20 (letra B)

  • Força Guerreiro!!!!!!