1. Qual a complexidade da busca binária?

2. Faça a associação correta:

busca em largura  o
busca em profundidade o

o fila
o pilha

3. Ordene as funções abaixo em ordem de crescimento (da menor para a

maior):

n, n^{2}, n^{3}, n log n, 2^{n}, n^{n}, n!, log n

4. Dos problemas abaixo, assinale os que podem ser resolvidos em tempo polinomial: árvore espalhada mínima circuito Euleriano circuito Hamiltoniano caminho mais curto entre dois vértices

5. Conhece a estrutura para implementar conjuntos disjuntos? Também conhecida como Union-Find? Qual sua complexidade?

6. Complete a tabela abaixo:

Algoritmo  Complexidade Média Complexidade Pior Caso

Insertion Sort Selection Sort Quicksort Mergesort HeapSort

7. Qual dos algoritmos para ordenação acima é melhor na prática?

8. Determine a ordem de crescimento das somatórias abaixo:

∑_{i=1}^{n} i = Θ(  )
∑_{i=1}^{n} i^{2} = Θ(  )
∑_{i=1}^{n} \frac{1}{i} = Θ(  )