Questão para a Prova Oral 064
5ª Semana: 17/03/2003 a 21/03/2003

Enunciado
Sobre medianas e estatísticas de ordem , assinale a alternativa CORRETA:

A) O algoritmo SELECT apresentado no livro divide o vetor em grupos de 5 elementos. Caso dividisse em grupos de 9 elementos, a recorrência para o cálculo de sua complexidade seria (não são apresentados os casos base e o No):
T(n) = T(TETO(n/9)) + T(5n/18 - 10) + O(n).
B) O algoritmo SELECT é uma melhoria frente ao algoritmo RANDOMIZED-SELECT, pois garante uma boa divisão quando o arranjo é particionado. Seu tempo de execução do pior caso é linear.
C) Para se encontrar o mínimo e o máximo em um vetor simultaneamente são necessárias no mínimo 2n - 2 comparações, já que são necessárias n -1 comparações para se encontrar o mínimo, e a mesma quantidade para o máximo.
D) O tempo de execução no caso médio do algoritmo RANDOMIZED-SELECT é THETA(n), já que ele utiliza a versão randômica do algoritmo quicksort em seu interior.
E) N.D.A.

Autora: Camila Ribeiro Rocha
RA: 022247