MO417- QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: É correto afirmar que:

a) O pior caso do Algoritmo Randomized-Select é o(n²)

b) O problema de seleção pode ser feito em complexidade o(n)

c) O número mínimo de comparações necessárias para determinar simultaneamente o   mínimo e o máximo de um conjunto são n

d) O Randomized-Select tem no melhor caso a complexidade de O(n) quando o particionamento é balanceado

e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sobre os algoritmos de ordenação vistos, é falso afirmar que:

a) Heapsort trabalha melhor com a memoria do que Merge Sort
b) Quicksort é eficiente com a memoria e é estável
c) Radix sort é um dos algoritmos de ordenação mais antigos
d) Bucket sort é um algoritmo de ordenação para números entre 0 ≤ x < 1
e) NDA



Ideia original de: Sheila Katherine Venero Ferro

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Para as seguintes recorrências, indique quais se aplicam ao Caso 3 do Teorema Mestre:

I.   1/2 T(n/2) + n²

II.   64 T(n/4) + n!

III.  3T(n/3) + n^1/2

IV. T(n/2) + 2ⁿ

a) Somente I

b) Somente II,III

c) Somente I, II, IV

d) Todas 

e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL

Número:
  Quais das afirmações são corretas?  

I.    o(g(n))  ⊂ O(g(n))
II.   Ω(g(n)) ⊂ O(g(n))
III.  Ω(g(n)) ⊂ Θ(g(n))
IV. ω(g(n)) ⊂ Ω(g(n))

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

Ideia original de: Sheila Katherine Venero Ferro

Blog criado para a disciplina de Complexidade de Algoritmos -2013 UNICAMP