Lista de exercícios de Algoritmos e complexidade com respostas

O que é o caso base de uma função recursiva?

1. AA chamada que usa mais memória
2. BO caso com a maior entrada, que é tratado antes de quaisquer chamadas recursivas
3. CA primeira linha da função
4. DUm caso respondido diretamente, sem fazer outra chamada recursiva

O que é memoização?

1. AEscrever comentários ao lado de cada linha de código
2. BConverter automaticamente a recursão em um laço equivalente, de modo que não seja preciso pilha de chamadas
3. CArmazenar os resultados de chamadas de função para que chamadas repetidas sejam respondidas da memória
4. DLiberar memória depois que uma função retorna

Qual é a complexidade de tempo do insertion sort no melhor caso, com um array já ordenado?

1. AO(n²)
2. BO(n)
3. CO(1)
4. DO(n 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 3 moedas; o ótimo é 2
2. BO guloso usa 2 moedas; o ótimo é 2
3. CO guloso usa 4 moedas; o ótimo é 3
4. DO guloso usa 3 moedas; o ótimo é 3

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

1. AEscolher primeiro a atividade mais curta
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 a atividade que começa mais cedo

Qual é a solução da recorrência T(n) = T(n/2) + O(1)?

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

O algoritmo de Strassen multiplica matrizes usando 7, em vez de 8, multiplicações recursivas de blocos de metade do tamanho. Qual é o seu tempo de execução?

1. AΘ(n²)
2. BΘ(n³)
3. CΘ(n^{log₂ 7}), cerca de n^2,81
4. DΘ(n² log n)

Tomar as duas extremidades de cada aresta de um emparelhamento maximal dá uma cobertura de vértices. Quão boa é essa cobertura?

1. ASempre uma cobertura de vértices mínima
2. BNo máximo o dobro do tamanho de uma cobertura de vértices mínima
3. CNo máximo log n vezes o mínimo
4. DDe qualidade desconhecida em relação ao ótimo