Lista de exercícios de Algoritmos e complexidade com respostas

O que é recursão?

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

Como funciona o selection sort?

1. AInsere cada elemento numa parte ordenada crescente por deslocamento
2. BTroca repetidamente elementos vizinhos que estão na ordem errada
3. CDivide o array em metades e as intercala
4. DEncontra repetidamente o mínimo da parte não ordenada e o troca para a frente

O que é um algoritmo?

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

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

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

Com moedas de 1, 3 e 4 e um valor de 6, quantas moedas o método guloso "maior moeda primeiro" usa, em comparação com o ótimo?

1. AO guloso usa 4 moedas; o ótimo é 3
2. BO guloso usa 2 moedas; o ótimo é 2
3. CO guloso usa 3 moedas; o ótimo é 2
4. DO guloso usa 3 moedas; o ótimo é 3

Uma função executa um laço de n iterações e depois, separadamente, outro laço de n iterações. Qual é a sua complexidade de tempo?

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

Qual algoritmo encontra uma árvore geradora mínima adicionando repetidamente a aresta mais barata que não forma um ciclo?

1. AAlgoritmo de Kruskal
2. BAlgoritmo de Prim a partir de um nó
3. CFloyd-Warshall
4. DAlgoritmo de Dijkstra

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(n) e espaço O(1)
2. BTempo O(2ⁿ) e espaço O(1)
3. CTempo O(n) e espaço O(n)
4. DTempo O(log n) e espaço O(n)