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(n²)
3. CO(1)
4. DO(log n)

Como funciona o selection sort?

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

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

1. ALer, calcular, escrever
2. BOrdenar, buscar, retornar
3. CDividir, conquistar, combinar
4. DChutar, verificar, repetir

O que a análise amortizada mede?

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

Por que a base do logaritmo costuma ser omitida no O grande, como em O(log n)?

1. AA base só importa para n pequeno
2. BLogaritmos de bases diferentes diferem apenas por um fator constante
3. COs logaritmos são sempre arredondados para inteiros
4. DTodos os logaritmos em computação têm base 10, então ela fica implícita

A complexidade de tempo do Fibonacci recursivo ingênuo (fib(n) = fib(n−1) + fib(n−2)) é:

1. ALogarítmica
2. BLinear
3. CExponencial
4. DConstante

Qual técnica dá ao quicksort um tempo de execução esperado O(n log n) para qualquer entrada?

1. AEscolher o pivô de forma uniformemente aleatória
2. BSempre escolher o primeiro elemento
3. CUsar recursão apenas no lado esquerdo
4. DOrdenar a entrada antes de executar o quicksort

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É NP-difícil
2. BÉ indecidível
3. CÉ sempre solúvel em O(V + E)
4. DPode ser resolvido pelo algoritmo de Dijkstra com os pesos negados