MO417 - Questão para a prova oral

Número: 001

Enunciado:
O seguinte algoritmo não é um algoritmo de ordenação:

1. NaoOrdena(A)
2. para i de 1 a length[A]
   1. A[i] = i

Esse algoritmo, no entanto, satisfaz várias invariantes de laço. Marque a alternativa cuja invariante ele não satisfaz. Nota: "Na iteração k" abaixo deve ser interpretado como "no final da iteração k".

1. Seja A' o vetor ordenado final retornado pelo algoritmo. Na iteração k, para todo i < k, temos A_k[i] = A'[i]
2. Na iteração k, para todos i < j < k, temos A_k[i] ≤ A_k[j]
3. Na iteração k, para todos i < j, temos ou j > k ou A_k[i] < A_k[j]
4. Na iteração k, não existem i,j tais que i < j e A_k[i] > A_k[j]
5. NDA

Autor(a): Alexandre Tachard Passos