MO417 - QUESTÃO PARA A PROVA ORAL

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-029


Enunciado: Tomando-se o algoritmo abaixo, que seleciona o i-ésimo menor elemento de um arranjo a, desde que i esteja entre 1 e o tamanho de a, auxiliado pelo algoritmo PARTICIONA:

01. SELECIONA(a: arranjo, i)
02.    se a.tamanho > 0
03.       inicio = 1
04.       fim = a.tamanho
05.       enquanto inicio < fim
06.          q = PARTICIONA(a, inicio, fim)      
07.          k = q - inicio + 1
08.          se i == k
09.             retorna a[q]
10.          senão se i < k
11.             fim = q - 1
12.          senão
13.             inicio = q + 1
14.             i = i - k
15.       retorna a[inicio]
16.    senão retorna NULO

01. PARTICIONA(a: arranjo, p, r)
02.    x = a[r]
03.    i = p - 1
04.    para j = p até r - 1
05.       se a[j] <= x
06.          i = i + 1
07.          troca a[i] com a[j]
08.    troca a[i + 1] com a[r]
09.    retorna i + 1

Sobre o algoritmo SELECIONA(a: array, i), é INCORRETO afirmar que:

1. Um pior caso ocorre para entradas ordenadas crescentemente, desejando-se saber o menor elemento.
2. Um melhor caso ocorre para entradas ordenadas crescentemente, desejando-se saber o maior elemento.
3. Um melhor caso ocorre para entradas ordenadas decrescentemente, desejando-se saber o maior elemento.
4. As complexidades de tempo esperada e no pior caso são O(n) e Θ(n²), respectivamente, para entradas de tamanho n.
5. N.D.A.

Ideia original de: Daniel Henriques Moreira