Lista de exercícios de Algoritmos e complexidade com respostas

A complexidade de espaço mede:

1. AO espaço em disco do arquivo do programa depois de compilado
2. BO tamanho físico do computador
3. CO número de linhas de código
4. DA quantidade de memória que um algoritmo precisa à medida que a entrada cresce

O que significa f(n) = Θ(g(n))?

1. Af cresce estritamente mais rápido que g
2. Bf é sempre menor que g para todo n, então g a limita por cima, mas nunca por baixo
3. Cf cresce estritamente mais devagar que g
4. Df cresce no mesmo ritmo que g, limitada por cima e por baixo por múltiplos constantes de g

Um algoritmo com dois laços aninhados, cada um executado n vezes, normalmente tem qual complexidade?

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

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. CRemove a aresta mais cara até não restarem ciclos
4. DExecuta uma busca em largura e mantém a árvore da BFS

O que significa um problema ter subestrutura ótima?

1. AO problema pode ser resolvido em tempo constante
2. BUma solução ótima pode ser construída a partir de soluções ótimas dos seus subproblemas
3. CTodos os subproblemas têm o mesmo tamanho
4. DO problema tem exatamente uma solução ótima, compartilhada por todos os subproblemas

O que a análise amortizada mede?

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

Qual é o tempo de execução do algoritmo de Dijkstra com um heap binário num grafo com V vértices e E arestas?

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

Qual é a diferença entre um problema indecidível e um intratável?

1. AAmbos significam que o problema não tem nenhum algoritmo
2. BProblemas intratáveis não podem ser resolvidos por nenhum algoritmo, enquanto os indecidíveis só exigem tempo exponencial
3. CNenhum algoritmo resolve um problema indecidível para todas as entradas, enquanto um intratável tem algoritmo, mas é lento demais
4. DProblemas indecidíveis estão em NP, enquanto os intratáveis estão em P