#2105044 CEPS UFPA - 2022 - Analista de Tecnologia da Informação (UFPA)/Desenvolvimento

Considere as funções busca1 e busca2 descritas a seguir, que apresentam a busca de um nó na lista linear 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 for encontrado, 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:

A complexidade temporal no pior caso de ambas as funções é O(n).
A complexidade temporal no pior caso da função busca1 é quadrática em função de n.
Para que a função busca1 entregue corretamente o índice do nó procurado, a lista linear L precisa estar ordenada.
Por empregar a estratégia conhecida como busca binária, a complexidade temporal no pior caso da função busca2 é O(log n).
Diferentemente da função busca2, a função busca1 sempre encontra um nó da lista linear L com as características desejadas, evitando o teste de fim de lista.