MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Dadas as seguintes afirmações:

I. Radix Sort é mais vantajoso que Merge Sort quando d < lgn, isto é, o número de dígitos for menor que lgn.
II. QuickSort e HeapSort são métodos de ordenação *in-place. Já Merge Sort e Counting Sort não são.
III. O algoritmo de seleção (SELECT), tempo de execução O(n) no pior caso, localiza o elemento desejado particionando recursivamente o arranjo de entrada. Sabe-se que o algoritmo de particionamento utilizado é o PARTITION do Quick Sort modificado.

a) Apenas I é correta
b) Apenas II é correta
c) I e II são corretas
d) II e III são corretas
e) NDA

*Um algoritmo de ordenação é in-place se a memória adicional requerida não depende do tamanho do vetor que está sendo ordenado.


Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Assinale a alternativa INCORRETA sobre os algoritmos de ordenação.

a) Radix Sort é mais vantajoso que Merge Sort quando d < lgn, isto é, o número de dígitos for menor que lgn.
b) QuickSort e HeapSort são métodos de ordenação *in-place. Já Merge Sort e Counting Sort não são.
c) Os elementos do Bucket Sort são números reais uniformente distribuídos no intervalo [0..1).
d) Para que Radix Sort funcione adequadamente, este deve utilizar um método de ordenação estável, por exemplo, Quick Sort.
e) NDA

*Um algoritmo de ordenação é in-place se a memória adicional requerida não depende do tamanho do vetor que está sendo ordenado.


Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Um algoritmo de ordenação é estável, se a ordem relativa dos itens com elementos iguais não é alterada após a ordenação. Dados os algoritmos de ordenação abaixo, qual(is) dele(s) é(são) estável(is)?

I. Insertion Sort

II. Merge Sort

III. Heapsort

a) Apenas I é correta

b) Apenas II é correta

c) I e II são corretas

d) II e III são corretas

e) NDA

Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Dadas as seguintes afirmações:

I. f(n)= 5n³+7 e g(n) = 2ⁿ, então g(n) Є Ω f(n).
II. Se f(n) Є O(g(n)), então f(n) cresce no máximo tão rapidamente quanto g(n).
III. Se f(n) = 4 ^logn e g(n) (3/2)ⁿ, então, f(n) = Ω(g(n)).

a) Apenas I é correta
b) Apenas II é correta
c) I e II são corretas
d) II e III são corretas
e) NDA

Ideia original de: Ademar Takeo Akabane