MO417 - Questão para a Prova Oral

Número: 2003-050


Enunciado: Sobre o Heapsort, o Quicksort, e suas estruturas subjacentes podemos afirmar que:

 

A) Em um HEAP máximo S podemos executar INSERÇÃO(S,x), DELEÇÃO(S,i), MÁXIMO(S) e MÍNIMO(S) em tempo O(lg n), onde x é um elemento a ser inserido e i é um índice válido no arranjo do HEAP.
B) No algoritmo Quicksort, o pior caso ocorre apenas quando todos os valores do vetor são iguais.
C) Mesmo no pior caso, o Quicksort tem desempenho melhor que o Heapsort, para qualquer n.
D) Em um HEAP máximo, todos os valores do nível h são obrigatoriamente maiores que qualquer valor do nível h+1, com h crescendo da raiz em direção às folhas.
E) N.D.A.


Ideia original de: Bruno Cedraz Brandão