Ensino rapido e

Prévia do material em texto

Claro! Aqui estão 100 problemas complexos de matemática e ciência da computação em 
formato de múltipla escolha. Cada um tem uma pergunta de tamanho médio e uma 
explicação detalhada. 
 
### Questões 
 
1. Em uma árvore binária completa de altura h, qual é o número máximo de nós que pode 
existir? 
 A) \(2^h - 1\) 
 B) \(2^{h+1} - 1\) 
 C) \(h^2\) 
 D) \(h \cdot 2^h\) 
 **Resposta: B) \(2^{h+1} - 1\)** 
 **Explicação:** Uma árvore binária completa tem todos os níveis completamente 
cheios, exceto possivelmente o último. O número total de nós é dado pela fórmula 
\(2^{h+1} - 1\), uma vez que no nível 0 (a raiz) há 1 nó, no nível 1 há 2 nós, no nível 2 há 4 
nós, e assim por diante, até chegar ao nível h. 
 
2. Qual é a complexidade de tempo do algoritmo de ordenação por inserção no pior caso 
para uma lista de n elementos? 
 A) \(O(n)\) 
 B) \(O(n^2)\) 
 C) \(O(n \log n)\) 
 D) \(O(n^3)\) 
 **Resposta: B) \(O(n^2)\)** 
 **Explicação:** No pior caso, o algoritmo de ordenação por inserção tem que comparar 
e mover cada elemento em relação a todos os itens já classificados, resultando em 
\(O(n^2)\) comparações e movimentações. Isso ocorre quando a lista está em ordem 
decrescente. 
 
3. Qual é a solução do seguinte sistema de equações lineares: 
 \(2x + 3y = 6\) 
 \(4x - y = 5\) 
 A) \((1, 1)\) 
 B) \((0, 2)\) 
 C) \((2, 0)\) 
 D) \((\frac{3}{2}, \frac{3}{2})\) 
 **Resposta: D) \((\frac{3}{2}, \frac{3}{2})\)** 
 **Explicação:** Para resolver, multiplicamos a segunda equação por 3: \(12x - 3y = 15\). 
Somando com a primeira equação dá \(14x = 21\), portanto \(x = \frac{3}{2}\). Substituindo 
\(x\) na primeira equação, obtemos \(y = \frac{3}{2}\). 
 
4. Se um algoritmo tem complexidade temporal \(O(f(n))\) e \(f(n) = 3n^4 + 2n^2 + 7\), qual 
é a maior taxa de crescimento? 
 A) \(O(n^2)\) 
 B) \(O(n^3)\) 
 C) \(O(n^4)\) 
 D) \(O(1)\) 
 **Resposta: C) \(O(n^4)\)** 
 **Explicação:** A taxa de crescimento do algoritmo é dominada pelo termo de maior 
ordem em \(f(n)\), que neste caso é \(3n^4\). Portanto a complexidade é \(O(n^4)\). 
 
5. Como se chama o princípio que afirma que um problema que pode ser reduzido a outro 
problema é no mínimo tão difícil quanto o outro? 
 A) Princípio da Indução 
 B) Princípio da Recursão 
 C) Princípio de Redução 
 D) Princípio da Completação 
 **Resposta: C) Princípio de Redução** 
 **Explicação:** O princípio de redução é usado em teoria da complexidade para 
classificar a dificuldade de problemas. Se um problema A pode ser reduzido a um 
problema B, a solução de B pode ser usada para resolver A, implicando que B é pelo 
menos tão difícil quanto A. 
 
6. Qual é a fórmula para calcular a distância entre dois pontos \(P1(x_1, y_1)\) e \(P2(x_2, 
y_2)\) no plano cartesiano? 
 A) \(d = |x_1 - x_2| + |y_1 - y_2|\) 
 B) \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\) 
 C) \(d = (x_2 - x_1)(y_2 - y_1)\) 
 D) \(d = x_1 + y_1 + x_2 + y_2\) 
 **Resposta: B) \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)** 
 **Explicação:** A fórmula da distância no plano cartesiano é derivada do Teorema de 
Pitágoras. A distância é a raiz quadrada da soma dos quadrados das diferenças nas 
coordenadas x e y. 
 
7. Se um algoritmo de busca binária é aplicado em um array de tamanho n, qual é a 
complexidade de tempo no pior caso? 
 A) \(O(n)\) 
 B) \(O(\log n)\) 
 C) \(O(n \log n)\) 
 D) \(O(1)\) 
 **Resposta: B) \(O(\log n)\)** 
 **Explicação:** A busca binária funciona dividindo o array ao meio a cada iteração, 
reduzindo o número de elementos possíveis pela metade até encontrar o elemento 
procurado ou determinar que ele não está presente. Isso resulta em uma complexidade 
de \(O(\log n)\). 
 
8. O que é um grafo acíclico dirigido (DAG) e qual é a sua principal aplicação em 
computação? 
 A) Um grafo com ciclos; usado em redes sociais 
 B) Um grafo sem ciclos; usado em sistemas de arquivos 
 C) Um grafo com arestas não direcionadas; usado em jogos 
 D) Um grafo com nós isolados; usado em análise de dados 
 **Resposta: B) Um grafo sem ciclos; usado em sistemas de arquivos** 
 **Explicação:** Um DAG é um grafo que possui arestas direcionadas, sem ciclos. Ele é 
amplamente utilizado em várias aplicações, sendo uma das principais em sistemas de 
arquivos e representação de dependências, como em compiladores para projetar ordens 
de execução de tarefas. 
 
9. Como se chama a abordagem que usa uma tabela de dispersão para armazenar e 
acessar dados? 
 A) Algoritmo de Buscas 
 B) Algoritmo de Ordenação 
 C) Tabela Hash