Lista de exercícios de Algoritmos e complexidade com respostas

O que é um algoritmo?

1. AUma estrutura de dados que armazena números
2. BQualquer programa de computador com interface gráfica
3. CUma linguagem de programação criada para escrever fórmulas matemáticas
4. DUma sequência finita de passos bem definidos que resolve um problema

A complexidade de espaço mede:

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

Qual é a complexidade de tempo do insertion sort no pior caso?

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

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

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

O que significa um problema ter subestrutura ótima?

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

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

1. AAlgoritmo de Dijkstra
2. BBellman-Ford é necessário em todos os casos
3. CBusca em profundidade (DFS)
4. DAlgoritmo de Kruskal

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) log V)
2. BO(V³)
3. CO(V × E)
4. DO(V + E)

Qual destes problemas de satisfatibilidade é sabidamente solúvel em tempo polinomial?

1. ASAT geral em fórmulas na forma normal conjuntiva
2. B3-SAT, em que cada cláusula tem exatamente três literais
3. C2-SAT, em que cada cláusula tem no máximo dois literais
4. DSatisfatibilidade de circuitos