Lista de exercícios de Algoritmos e complexidade com respostas

Quanta memória extra usa um merge sort padrão baseado em arrays?

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

O que significa uma operação rodar em tempo O(1)?

1. ASó pode ser executada uma vez
2. BProcessa exatamente um elemento por segundo de tempo de execução
3. CSempre leva exatamente um segundo
4. DSeu tempo de execução não cresce com o tamanho da entrada

Quais são as três etapas de um algoritmo de divisão e conquista?

1. ALer, calcular, escrever
2. BDividir, conquistar, combinar
3. CChutar, verificar, repetir
4. DOrdenar, buscar, retornar

Como o algoritmo de Prim constrói uma árvore geradora mínima?

1. AFaz crescer uma árvore a partir de um vértice inicial, adicionando a aresta mais barata que sai da árvore
2. BOrdena todas as arestas por peso e adiciona cada uma, a menos que forme um ciclo na floresta
3. CExecuta uma busca em largura e mantém a árvore da BFS
4. DRemove a aresta mais cara até não restarem ciclos

O que a análise amortizada mede?

1. AO custo médio por operação ao longo de uma sequência de operações de pior caso
2. BO custo esperado sobre entradas aleatórias
3. CO custo de um algoritmo com a melhor entrada
4. DO custo da operação individual mais cara em qualquer ponto da sequência

A busca em largura (BFS) em um grafo não ponderado encontra:

1. AA árvore geradora mínima
2. BCaminhos mínimos em número de arestas a partir do nó inicial
3. CUma ordenação topológica em todos os grafos
4. DCaminhos mínimos em grafos que contêm arestas com pesos negativos

Caminhos simples mínimos podem ser encontrados em tempo polinomial. O que se sabe sobre encontrar o caminho simples mais longo entre dois vértices num grafo geral?

1. AÉ indecidível
2. BÉ sempre solúvel em O(V + E)
3. CPode ser resolvido pelo algoritmo de Dijkstra com os pesos negados
4. DÉ NP-difícil

Como n! e 2ⁿ se comparam para n grande?

1. ACrescem no mesmo ritmo
2. B2ⁿ cresce mais rápido que n!
3. Cn! é O(n²)
4. Dn! cresce mais rápido que 2ⁿ