MO417 - Questão para a prova oral

Número:

Enunciado: Considere as seguintes informações sobre o algoritmo de seleção RANDOMIZED-SELECT, cujo código segue abaixo:

RANDOMIZED-SELECT(A,p,r,i)
if (p == r)
   return A[p]
q = RANDOMIZED-PARTITION(A,p,r)
k = q-p-1
if (i == k)
   return A[q]
else if (i < k)
   return RANDOMIZED-SELECT(A,p,q-1,i)
else return RANDOMIZED-SELECT(A,q+1,r,i-k)

I. O algoritmo executa em tempo linear, uma vez que adota premissas sobre a entrada.
II. O algoritmo realiza primeiro uma ordenação dos elementos para então selecionar o i-ésimo menor elemento do arranjo A[p...r].
III. Para determinar qualquer estatística de ordem, considerando elementos distintos do arranjo, o tempo esperado é linear.
IV. O algoritmo utiliza a técnica de divisão e conquista para retornar o i-ésimo menor elemento do arranjo A[p...r].

Assinale a alternativa correta:

A) I e II estão correta.
B) I, III e IV estão corretas.
C) I e III estão corretas.
D) III e IV estão corretas.
E) N.D.A

Ideia original de: Thaís Harumi Ussami