MO417 - Questão para a prova oral

Número: 

Enunciado: Considere as seguintes afirmações: 
  
  (I)  Para localizar simultaneamente o elemento mínimo e o elemento máximo de um vetor com n elementos, onde n é impar, tem 3*(floor(n/2)) comparações. Se removemos o primeiro elemento do vetor o número de comparações para localizar simultaneamente o elemento mínimo e o elemento máximo é  3*(floor(n/2))  - 7/2.

 (II)  O algoritmo RANDOMIZED-SELECT pode encontrar o i-th elemento mais large de um vetor em Θ(n)

(III)  O tempo de execução do algoritmo RANDOMIZED-SELECT quando o vetor de entrada é ordenada em forma crescente é Θ(n²)

Assinale a alternatica correta:

1. Somente (I) é verdadeira.
2. Somente (II) é verdadeira.
3. (I) e (II) são verdadeiras.
4. (II) e (III) são verdadeiras.
5. NDA

Ideia original de: Jhon Anthony Campos Arteaga