Questão 1728436

• Banca: FGV
• Órgão: TJ-RO
• Ano: 2015
• Provas: FGV - 2015 - TJ-RO - Analista de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Conceitos Básicos de Estrutura de Dados; Estrutura de Dados

João tem um arquivo que contém uma lista de nomes e endereços, com mais de 100.000 registros, e precisa implementar um mecanismo de busca por nome.

João considerou três alternativas:

I. Árvore binária;

II. Tabela Hash;

III. Árvore B;

IV. Busca linear.

Depois de preparar os dados e testar cada algoritmo com nomes escolhidos aleatoriamente, João concluiu que, genericamente, a classificação desses métodos, do menor para o maior tempo de busca, é:

• A. I, II, III, IV;
• B. II, III, I, IV;
• C. III, I, IV, II;
• D. II, I, III, IV;
• E. III, II, I, IV.

Gabarito: B

Comentários

• B-

  
  

  Tabela Hash;

  Árvore B;

  Árvore binária;

  Busca linear.

• Tabela Hash: O(1) se não tiver colisão

  Árvore B: O(log(n)), pois sempre está balanceada

  Árvore Binária: O(log(n)) se tiver balanceada e O(n) se for degenerada

  Busca Linear: O(n)

• Força Guerreiro!!!!!!