Lista de exercícios de Algoritmos e complexidade com respostas

Um problema costuma ser chamado de tratável se:

1. APode ser resolvido em tempo polinomial
2. BSó pode ser resolvido testando todas as possibilidades
3. CNão tem solução
4. DPode ser resolvido em tempo constante

O que é recursão?

1. AUma função que chama a si mesma com entradas menores
2. BUm tipo de estrutura de dados
3. CUm método de ordenação
4. DUm laço que nunca termina

A complexidade de espaço mede:

1. AO tamanho físico do computador
2. BO espaço em disco do arquivo do programa depois de compilado
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 um problema ter subestrutura ótima?

1. AO problema tem exatamente uma solução ótima, compartilhada por todos os subproblemas
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 pode ser resolvido em tempo constante

O que o algoritmo de Floyd–Warshall calcula, e com que rapidez?

1. AUma ordenação topológica em O(V²)
2. BCaminhos mínimos de um vértice de origem para todos os outros em O(V + E)
3. CUma árvore geradora mínima em O(E log V)
4. DCaminhos mínimos entre todos os pares de vértices em O(V³)

No problema de seleção de atividades, qual regra gulosa sempre dá o número máximo de atividades sem sobreposição?

1. AEscolher a atividade que começa mais cedo
2. BEscolher primeiro a atividade com menos sobreposições e repetir com as compatíveis
3. CEscolher a atividade que termina mais cedo e repetir com as compatíveis
4. DEscolher primeiro a atividade mais curta

Quais são os custos de tempo e espaço de calcular o n-ésimo número de Fibonacci com um laço que guarda só os dois últimos valores?

1. ATempo O(2ⁿ) e espaço O(1)
2. BTempo O(n) e espaço O(1)
3. CTempo O(log n) e espaço O(n)
4. DTempo O(n) e espaço O(n)

Para qual variante da mochila a regra gulosa "pegar os itens em ordem de valor por peso" sempre dá uma resposta ótima?

1. AA mochila 0/1, em que os itens devem ser sempre levados inteiros
2. BAs duas variantes
3. CA mochila fracionária, em que os itens podem ser divididos
4. DNenhuma das variantes