Questão 3172807

• Banca: IF-PE
• Órgão: IF-PE
• Ano: 2019
• Provas: IF-PE - 2019 - IF-PE - Técnico em Tecnologia da Informação - Desenvolvimento
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca

Sobre algoritmos de busca, analise as informações a seguir.

I. Uma busca linear sobre um array de uma dimensão pode ser implementada com um laço e possui complexidade, no pior caso, linearmente relacionada ao tamanho do array.

II. Uma busca binária sobre um array de uma dimensão pode ser implementada com um laço e possui complexidade, no pior caso, linearmente relacionada ao logaritmo do tamanho do array.

III. Uma busca binária recursiva sobre um array de uma dimensão pode ser implementada sem laços e possui complexidade, no pior caso, linearmente relacionada ao logaritmo do tamanho do array.

IV. Uma busca linear sobre um array de duas dimensões pode ser implementada com dois laços e possui complexidade, no pior caso, linearmente proporcional à soma da quantidade de linhas e colunas do array.

V. Uma busca em uma estrutura de dados chamada Tabela de Dispersão (Hash Table) pode ser implementada sem laços e possui complexidade, no pior caso, constante, independentemente do tamanho do array.

Estão CORRETAS, apenas, as proposições

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

Gabarito: A

Comentários

• IV - Não é soma, mas a multiplicação de linhas por colunas

  V - Hash Table tem, em média, complexidade O(1), ou seja, independente do tamanho. Mas, no pior caso, quando há n elementos e n colisões, a complexidade será O(n)

• Força Guerreiro!!!!!!