Questão 1062631

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2012
• Provas: CESGRANRIO - 2012 - Petrobras - Analista de Sistemas Júnior - Processos de Negócios-2012
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Todos os N nomes de uma lista de assinantes de uma companhia telefônica foram inseridos, em ordem alfabética, em três estruturas de dados: uma árvore binária de busca, uma árvore AVL e uma árvore B.

As alturas resultantes das três árvores são, respectivamente,

• A. O(Log(N)), O(Log(N)), O(1)
  
• B. O(Log(N)), O(N), O(Log(N))
  
• C. O(N), O(Log(N)), O(1)
  
• D. O(N), O(Log(N)), O(Log(N))
  
• E. O(N), O(N), O(Log(N))

Gabarito: D

Comentários

• A complexidade da árvore binária de busca  é :  O(N)

   

  A complexidade da árvore AVL é: O(Log(N))

   

  A complexidade da árvore B é: O(Log(N))

• 1 - Árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (esta é a forma padrão, podendo as subárvores serem invertidas, dependendo da aplicação).O objetivo desta árvore é estruturar os dados de forma a permitir busca binária.

  Algortimo      Caso Médio     Pior caso

  Busca              O(log n)             O(n)

  Inserção          O(log n)           O(n)

  Remoção        O(log n)           O(n)

   

  2 - Árvore AVL é uma árvore binária de busca balanceada, ou seja, uma árvore balanceada (árvore completa) são as árvores que minimizam o número de comparações efetuadas no pior caso para uma busca com chaves de probabilidades de ocorrências idênticas. Contudo, para garantir essa propriedade em aplicações dinâmicas, é preciso reconstruir a árvore para seu estado ideal a cada operação sobre seus nós (inclusão ou exclusão), para ser alcançado um custo de algoritmo com o tempo de pesquisa tendendo a O(log N).

   

  Algortimo      Caso Médio     Pior caso

  Busca              O(log n)             O(log n) 

  Inserção          O(log n)            O(log n) 

  Remoção        O(log n)            O(log n) 

   

  3 - Árvore B é uma estrutura de dados projetada para funcionar especialmente em memória secundária como um disco magnético ou outros dispositivos de armazenamento secundário.

  De acordo com a definição de Knuth de ordem e página folha de Bayer e McCreight, uma árvore B de ordem d (número máximo de páginas filhas para uma página pai) deve satisfazer as seguintes propriedades:

   

  1 - Cada página contém no máximo d páginas filhas

  2 - Cada página, exceto a raiz e as folhas, tem pelo menos ⌈d/2⌉ páginas filhas

  3 - A página raiz tem ao menos duas páginas filhas (ao menos que ela seja uma folha)

  4 - Toda página folha possui a mesma profundidade, na qual é equivalente à altura da árvore

  5 - Uma página não folha com k páginas filha contem k-1 chaves

  6 - Uma página folha contém pelo menos ⌈d/2⌉-1 chaves e no máximo d-1 chaves

   

  Algortimo      Caso Médio     Pior caso

  Busca              O(log n)             O(log n) 

  Inserção          O(log n)            O(log n) 

  Remoção        O(log n)            O(log n) 

• d-

  tabela que tem ter gravada

  https://www.bigocheatsheet.com/

• Força Guerreiro!!!!!!