Seu próximo nível começa aqui
Seu desenvolvimento não pode ter limites. Garanta sua Assinatura Ilimitada e libere uma preparação completa com os melhores professores do Brasil.
Considere as funções busca1 e busca2 descritas a seguir...
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
A complexidade temporal no pior caso de ambas as funções é O(n).
B
A complexidade temporal no pior caso da função busca1 é quadrática em função de n.
C
Para que a função busca1 entregue corretamente o índice do nó procurado, a lista linear L precisa estar ordenada.
D
Por empregar a estratégia conhecida como busca binária, a complexidade temporal no pior caso da função busca2 é O(log n).
E
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.