Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF-PE 2019
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq509660
Banca
IF-PE
Órgão
IF-PE
Ano
2019
Nível
Médio
Cargo
Técnico em Tecnologia da Informação - Desenvolvimento
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
AI, II e III.
BII e V.
CI, III, IV e V.
DIII, IV e V.
EI, II e IV.
Revelar gabarito e comentário▾
GabaritoA — I, II e III.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Algoritmos de busca – complexidade
Gabarito: letra A (apenas as proposições I, II e III estão corretas). A questão avalia o conhecimento da complexidade assintótica de diferentes algoritmos de busca. A busca linear tem complexidade O(n) no pior caso; a busca binária tem complexidade O(log n), podendo ser implementada iterativamente (com laço) ou recursivamente (sem laço). A proposição IV erra ao afirmar que a complexidade da busca linear em matriz é proporcional à soma das dimensões, quando na verdade é proporcional ao produto (número total de elementos). A proposição V erra ao dizer que a busca em tabela hash tem complexidade constante no pior caso – na verdade, o pior caso é O(n) devido a colisões.
Proposição
Afirmação sobre complexidade
Correção?
Motivo
I
Busca linear em array 1D: O(n) no pior caso, implementada com laço
✅ Correta
Percorre todos os elementos no pior caso; complexidade linear O(n)
II
Busca binária iterativa em array 1D: O(log n) no pior caso, com laço
✅ Correta
Divisão sucessiva ao meio; complexidade O(log n)
III
Busca binária recursiva em array 1D: O(log n) no pior caso, sem laço
✅ Correta
Recursão substitui laço; mesma complexidade O(log n)
IV
Busca linear em array 2D: O(m+n) no pior caso
❌ Incorreta
Complexidade real é O(m×n), proporcional ao produto, não à soma
V
Busca em tabela hash: complexidade constante no pior caso
❌ Incorreta
Pior caso é O(n) devido a colisões; constante é caso médio
Complexidade de busca: Busca linear (array 1D) (O(n) – pior caso, Implementação: laço único); Busca binária (array ordenado) (O(log n) – pior caso, Iterativa: laço, Recursiva: sem laço); Busca linear (array 2D) (O(m×n) – produto, não soma); Tabela hash (Caso médio: O(1), Pior caso: O(n) – colisões)
Item I — ✅ Correto
A busca linear percorre cada elemento do array até encontrar o valor desejado. No pior caso (quando o elemento está na última posição ou não existe), todos os elementos são visitados, resultando em complexidade O(n) – linearmente relacionada ao tamanho do array. A implementação típica utiliza um único laço (for, while). Portanto, a afirmativa está correta.
Item II — ✅ Correto
A busca binária exige que o array esteja ordenado. Ela funciona dividindo repetidamente o intervalo de busca pela metade. Uma implementação iterativa utiliza um laço (geralmente while) e, no pior caso, realiza cerca de log₂(n) comparações, o que é linearmente relacionado ao logaritmo do tamanho do array. Complexidade O(log n). Afirmativa correta.
Item III — ✅ Correto
A busca binária recursiva elimina a necessidade de laços explícitos, substituindo a iteração por chamadas recursivas. A complexidade continua O(log n) no pior caso, pois a cada chamada o problema é reduzido pela metade. A recursão é uma forma de controle de fluxo que não utiliza laços. Afirmativa correta.
Item IV — ❌ Incorreto
Uma busca linear em um array bidimensional (matriz) percorre todos os elementos para encontrar o valor. Se a matriz tem m linhas e n colunas, o total de elementos é m × n. No pior caso, todos são visitados, resultando em complexidade O(m×n) – proporcional ao produto, não à soma. A afirmativa erra ao dizer "soma da quantidade de linhas e colunas". O correto seria "produto" ou "número total de elementos".
Item V — ❌ Incorreto
Em uma tabela hash ideal, sem colisões, a busca pode ser feita em O(1) – tempo constante. Porém, no pior caso (quando muitas chaves colidem na mesma posição), a busca pode degenerar para O(n), dependendo da política de resolução de colisões (encadeamento, endereçamento aberto, etc.). Além disso, a implementação prática geralmente envolve laços (para calcular o hash ou percorrer listas encadeadas). Portanto, afirmar que a complexidade é "constante, independentemente do tamanho" no pior caso é falso.
Gabarito: letra A – corretos apenas os itens I, II e III.