Questão 1567027

• Banca: COSEAC
• Órgão: UFF
• Ano: 2015
• Provas: COSEAC - 2015 - UFF - Técnico de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca; Estrutura de Dados; Vetores

Em relação aos algoritmos de pesquisa em um vetor de N elementos, é correto afirmar que:

• A. a pesquisa binária não necessita que o vetor esteja previamente ordenado.
• B. a busca por interpolação é mais adequada quando existe uma distribuição não uniforme nas chaves.
• C. a busca sequencial possui tempo médio da ordem de log₂N (log N na base 2).
• D. a pesquisa binária possui uma quantidade máxima de buscas da ordem de N/2.
• E. o hashing é considerado tanto um método de busca quanto um método de ordenação.

Gabarito: E

Comentários

• a) ERRADA. O vetor deve estar previamente ordenado

  b) ERRADA. A distribuição das chaves deve ser uniforme.

  c) ERRADA. O tempo médio da busca sequencial é N/2.

  d) ERRADA. Possui quantidade máxima de busca de O(logn)

  e) CORRETA.

• O algoritmo de busca linear é um algoritmo O(n). No caso médio, o elemento é encontrado após N/2

  O algoritmo de busca binária possui complexidade O(Log N base 2)

  Na busca por Interpolação, se as chaves estiverem uniformemente distribuídas a complexidade é O(log(log(n))), Se as chaves não estiverem uniformemente distribuídas, a busca por interpolação pode ser tão ruim quanto uma busca seqüencial

• A - A pesquisa binária necessita que o vetor esteja previamente ordenado.

  B - A busca por interpolação é mais adequada quando existe uma distribuição uniforme nas chaves.

  C - A busca sequencial possui tempo médio da ordem de log N/2.

  D - A pesquisa binária possui uma quantidade máxima de buscas da ordem de O(logn).

• Força Guerreiro!!!!!!