recomeço DR

Prévia do material em texto

96. Um problema de programação dinâmica resolve o problema do caminho mais curto 
em uma grade. Qual é a complexidade de tempo desse algoritmo? 
 a) O(n) 
 b) O(n^2) 
 c) O(n log n) 
 d) O(nW) 
 Resposta: b) O(n^2) 
 Explicação: Para uma grade de n x n, a complexidade é O(n^2) devido à necessidade de 
calcular cada célula. 
 
97. Um algoritmo de busca linear é aplicado a um vetor de 100 elementos. Qual é a 
complexidade de tempo desse algoritmo? 
 a) O(1) 
 b) O(n) 
 c) O(n log n) 
 d) O(n^2) 
 Resposta: b) O(n) 
 Explicação: A busca linear verifica cada elemento até encontrar o alvo, resultando em 
uma complexidade linear. 
 
98. Um algoritmo de Dijkstra é utilizado em um grafo com 30 vértices. Qual é a 
complexidade de tempo se o grafo for representado como uma lista de adjacência? 
 a) O(V^2) 
 b) O(E log V) 
 c) O(V + E) 
 d) O(V log V) 
 Resposta: b) O(E log V) 
 Explicação: A complexidade do algoritmo Dijkstra usando uma lista de adjacência e uma 
fila de prioridade é \(O(E \log V)\). 
 
99. Um algoritmo de ordenação por mistura (Merge Sort) é aplicado a um vetor de 70 
elementos. Qual é a complexidade de tempo desse algoritmo? 
 a) O(n) 
 b) O(n log n) 
 c) O(n^2) 
 d) O(log n) 
 Resposta: b) O(n log n) 
 Explicação: O Merge Sort divide a lista em partes menores e as combina, resultando em 
uma complexidade de tempo de O(n log n). 
 
100. Um grafo tem 10 vértices e 15 arestas. Qual é a densidade do grafo? 
 a) 0.1 
 b) 0.2 
 c) 0.3 
 d) 0.4 
 Resposta: b) 0.3 
 Explicação: A densidade é dada por \( \frac{2E}{V(V-1)} = \frac{30}{90} = 0.3\). 
 
Esses 100 problemas abrangem conceitos de algoritmos, complexidade de tempo e 
espaço, e propriedades de grafos, todos com explicações detalhadas. 
Claro! Aqui estão 100 problemas de matemática discreta em formato de múltipla 
escolha, todos únicos e com explicações detalhadas. 
 
1. Considere um grafo G com 5 vértices e 8 arestas. Se o grafo for conexo, qual é o número 
mínimo de arestas que podem ser removidas para torná-lo desconexo? 
 a) 1 
 b) 2 
 c) 3 
 d) 4 
 **Resposta: a) 1**. Um grafo conexo pode ser desconectado removendo uma aresta que 
conecta dois vértices, portanto, a remoção de uma única aresta é suficiente. 
 
2. Em um conjunto de 10 números inteiros, qual é o número mínimo de números que 
devem ser escolhidos para garantir que pelo menos dois deles tenham o mesmo valor 
quando tomamos os restos da divisão por 5? 
 a) 5 
 b) 6 
 c) 7 
 d) 10 
 **Resposta: b) 6**. Pelo princípio da casa dos pombos, ao escolher 6 números, pelo 
menos dois deles terão o mesmo resto quando divididos por 5. 
 
3. Quantas permutações diferentes podem ser feitas com as letras da palavra 
"MATEMATICA"? 
 a) 50400 
 b) 7200 
 c) 12600 
 d) 10080 
 **Resposta: c) 12600**. A palavra "MATEMATICA" tem 10 letras, com as letras M, A e T 
repetidas 2 vezes cada. O número de permutações é dado por \( \frac{10!}{2! \cdot 2! 
\cdot 2!} = 12600 \). 
 
4. Quantos subconjuntos de um conjunto de 8 elementos não contém o elemento "a"? 
 a) 128 
 b) 64 
 c) 256 
 d) 32 
 **Resposta: a) 128**. Se excluímos "a", sobramos com 7 elementos. O número de 
subconjuntos é \( 2^7 = 128 \). 
 
5. Um estudante tem 4 exames para fazer. Se ele pode escolher a ordem em que faz os 
exames, quantas ordens diferentes ele pode escolher? 
 a) 12 
 b) 24 
 c) 16 
 d) 30 
 **Resposta: b) 24**. O número de formas de organizar 4 exames é \( 4! = 24 \). 
 
6. Considere um grafo bipartido completo K_{3,4}. Qual é o número total de arestas nesse 
grafo? 
 a) 12 
 b) 10