Lista de exercícios de Algoritmos e complexidade com respostas

Qual algoritmo de ordenação escolhe um pivô e particiona o array em elementos menores e maiores?

1. AInsertion sort
2. BMerge sort
3. CBubble sort
4. DQuicksort

Um laço começa com i = 1 e dobra i a cada iteração até i > n. Quantas iterações ele executa?

1. ACerca de n²
2. BCerca de n / 2
3. CCerca de n
4. DCerca de log₂ n

Qual é a complexidade de tempo da busca em profundidade num grafo armazenado como listas de adjacência?

1. AO(V²)
2. BO(V × E)
3. CO(E log V)
4. DO(V + E)

Qual algoritmo encontra os caminhos mínimos a partir de uma origem em um grafo com pesos de arestas não negativos?

1. ABellman-Ford é necessário em todos os casos
2. BBusca em profundidade (DFS)
3. CAlgoritmo de Dijkstra
4. DAlgoritmo de Kruskal

Qual é a complexidade de tempo de multiplicar duas matrizes n × n com o laço triplo padrão?

1. AO(n)
2. BO(n³)
3. CO(n²)
4. DO(n² log n)

Qual é a complexidade de tempo de calcular o n-ésimo número de Fibonacci com uma tabela bottom-up?

1. AO(n)
2. BO(n²)
3. CO(log n)
4. DO(2ⁿ)

Qual é a solução da recorrência T(n) = 2T(n/2) + n log n?

1. AΘ(n log² n)
2. BΘ(n²)
3. CΘ(n)
4. DΘ(n log n)

O que decorreria se alguém encontrasse um algoritmo de tempo polinomial para um problema NP-completo?

1. ATodo problema em NP poderia ser resolvido em tempo polinomial, então P = NP
2. BO problema da parada se tornaria decidível
3. CSó aquele problema passaria para P
4. DTodos os algoritmos de tempo exponencial passariam imediatamente a rodar em tempo linear