Questão 1474705

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2010
• Provas: CESGRANRIO - 2010 - Petrobras - Analista de Sistemas Júnior - Engenharia de Software
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Os números 1,2,3,...,N foram inseridos de forma ordenada em uma árvore binária de busca, em uma árvore AVL e em um vetor para o qual foi decidido que a posição do número i seria dada pelo índice i-1. Depois, sabendo-se que nenhuma inserção posterior será realizada em nenhuma das três estruturas, decidiu-se fazer uma busca em cada uma destas. Os tempos que se podem obter para essa busca na árvore binária de busca, na árvore AVL e no vetor são, respectivamente,

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

Gabarito: E

Comentários

• Busca Binária Ordenada: O(N)

  Busca AVL: O(Log N)

  Vetor pelo índice i-1: O(1) 

   

  A pegadinha estava na busca pelo índice. Do contrário, seria busca sequencia, de complexidade O(N)