Questão de Algoritmos e Estrutura de Dados — Algoritmos — CEPS-UFPA 2022
Algoritmos e Estrutura de Dados›Algoritmos
Código
gp036802
Banca
CEPS-UFPA
Órgão
UFPA
Ano
2022
Cargo
CEPS - - Analista de Tecnologia da Informação / Área: Desenvolvimento
Considere as funções busca1 e busca2 descritas a seguir, que apresentam a busca de um nó na listalinear L com n elementos, conhecendo-se a sua chave. A variável x corresponde à chave do nóprocurado. As funções informam, ao final, o índice do nó que se deseja buscar. Se este não forencontrado, o índice é nulo. função busca1(x) 1. i := 1 2. busca1 := 0 3. enquanto i ≤ n faça 4. se L[i].chave = x então 5. busca1 := i 6. i := n + 1 7. senão i := i + 1 função busca2(x) 1. i := 1 2. L[n + 1].chave := x 3. enquanto L[i].chave ≠ x faça 4. i := i + 1 5. se i ≠ n + 1 então busca2 := i 6. senão busca2 := 0 Com base nas informações dadas, é correto afirmar:
AA complexidade temporal no pior caso de ambas as funções é O(n).
BA complexidade temporal no pior caso da função busca1 é quadrática em função de n.
CPara que a função busca1 entregue corretamente o índice do nó procurado, a lista linear L precisaestar ordenada.
DPor empregar a estratégia conhecida como busca binária, a complexidade temporal no pior caso dafunção busca2 é O(log n).
EDiferentemente da função busca2, a função busca1 sempre encontra um nó da lista linear L com ascaracterísticas desejadas, evitando o teste de fim de lista.
Revelar gabarito e comentário▾
GabaritoA — A complexidade temporal no pior caso de ambas as funções é O(n).
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”.
Análise de algoritmos de busca em lista linear
Gabarito: letra A. Ambas as funções, busca1 e busca2, realizam uma busca linear (sequencial) na lista L, percorrendo os elementos um a um. No pior caso, quando o elemento não está presente ou está no final, o número de iterações é proporcional a n, resultando em complexidade O(n). Nenhuma das outras alternativas está correta.
Função
Estratégia de busca
Complexidade no pior caso
Requer lista ordenada?
Teste de fim de lista a cada iteração?
Sempre encontra a chave?
busca1
Busca linear (sequencial)
O(n)
Não
Sim (i ≤ n)
Não (retorna 0 se não encontrado)
busca2
Busca linear com sentinela
O(n)
Não
Não (usa sentinela em L[n+1])
Sim (sentinela garante que encontrará)
Busca linear (sequencial): busca1 (sem sentinela) (Testa i ≤ n a cada iteração, Retorna 0 se não encontrado, Pior caso: O(n)); busca2 (com sentinela) (Cópia da chave em L[n+1], Sempre encontra (sentinela), Pior caso: O(n)); Características comuns (Não exige lista ordenada, Não é busca binária)
Alternativa A — ✅ Correta ⟵ GABARITO
A complexidade temporal no pior caso de ambas as funções é O(n). Justificativa: busca1 percorre a lista do início ao fim (ou até encontrar o elemento), e busca2 utiliza um sentinela (cópia da chave em L[n+1]) para garantir que a busca sempre encontrará a chave, mas ainda assim realiza até n+1 iterações, ambas com crescimento linear em relação a n.
Alternativa B — ❌ Incorreta
Afirma que a busca1 tem complexidade quadrática. Na verdade, ela é linear (O(n)). Não há laço aninhado ou operação que dependa de n^2. Trata-se de um simples laço while com incremento unitário.
Alternativa C — ❌ Incorreta
A busca1 funciona corretamente independentemente de a lista estar ordenada ou não, pois compara a chave de cada elemento linearmente. A ordenação não é requisito para busca linear.
Alternativa D — ❌ Incorreta
A busca2 emprega busca linear com sentinela, não busca binária. A busca binária exige lista ordenada e tem complexidade O(log n). A sentinela apenas elimina a necessidade de testar o fim da lista a cada iteração, mas a busca continua sequencial.
Alternativa E — ❌ Incorreta
A afirmação inverte as características: na verdade, é a busca2 que sempre encontra o elemento (devido ao sentinela) e evita o teste de fim de lista. A busca1 realiza o teste i ≤ n a cada iteração e retorna 0 se o elemento não existir.
PEGA ESSA DICA!
Ao analisar complexidade de algoritmos, identifique o laço principal e seu comportamento no pior caso. Para buscas sequenciais, a complexidade é sempre O(n), independentemente de uso de sentinela. A diferença prática é apenas a eliminação de uma comparação extra por iteração, não a ordem de crescimento.