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