MO417 - Questão para a prova oral

Número: 046

Enunciado:
Sobre o problema da seleção "dado um conjunto A de n números reais e um inteiro k, determinar qual é o k-ésimo menor elemento de A" foram feitas as seguintes afirmações (assuma que não temos valores repetidos no conjunto A):

I - Um algoritmo para resolver o problema da seleção pode ser ordenar os n elementos do conjunto A usando o mergesort ou o heapsort e retornar o elemento situado na posição k do conjunto A ordenado.

II - Podemos projetar um algoritmo de divisão e conquista para o problema da seleção utilizando a ideia do quicksort de particionar os elementos de dois conjuntos com relação a um elemento pivot (i-ésimo elemento): se i = k, o pivot é o elemento procurado, se i menor que k então o k-ésimo elemento está na partição dos elementos menores que o pivot, se i maior que k então o k-ésimo elemento está na partição dos elementos maiores que o pivot.

III - Existe um algoritmo O(n) no pior caso que resolve o problema da seleção.

Assinale a alternativa que indica as afirmações corretas:

1. Apenas I.
2. Apenas II.
3. Apenas III.
4. Todas as alternativas estão corretas.
5. NDA

Autor(a): Celina d' ?vila Samogin