Uso de memória em algorítimos de ordenação

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Com relação ao uso de memória, incluindo a memória usada na pilha em chamadas recursivas, NÃO é correto afirmar que:

A) O Quicksort pode ser otimizado para usar apenas O(lg n) de espaço extra.
B) O Heapsort pode ser implementado para usar apenas O(1) espaço extra.
C) O Merge sort pode ser implementado usando lista ligada para usar apenas O(lg n) espaço extra.
D) O Counting sort pode ser implementado usando O(n) espaço extra, se o intervalo dos números a serem ordenados também for O(n).
E) NDA

Ideia original de: Fabrício Matheus Gonçalves

Heap Binário

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Com relação a um heap binário com n elementos, NÃO é correto afirmar que:

A) Pode ser usado para ordenar uma sequência de números em O(n lg n).
B) A altura do heap é a altura do nó raiz, ou seja θ(lg n).
C) A altura de um nó é o comprimento do caminho descendente simples mais longo do nó até uma folha.
D) Pode ser construído em O(n).
E) NDA

Ideia original de: Fabrício Matheus Gonçalves