livro 214 DC

Prévia do material em texto

20. Em um algoritmo de divisão e conquista, se você dividir um problema em 4 
subproblemas de tamanho n/2, qual é a relação de recorrência que descreve o tempo de 
execução do algoritmo? 
A) T(n) = 4T(n/2) + O(n) 
B) T(n) = 2T(n/2) + O(n) 
C) T(n) = T(n/2) + O(n) 
D) T(n) = 3T(n/2) + O(n) 
**Resposta:** A) T(n) = 4T(n/2) + O(n) 
**Explicação:** A relação de recorrência para um algoritmo de divisão e conquista que 
divide o problema em 4 subproblemas de tamanho n/2 e tem um custo de O(n) para 
combinar as soluções é T(n) = 4T(n/2) + O(n). 
 
21. Um algoritmo de busca em largura (BFS) é aplicado a um grafo com 7 vértices e 12 
arestas. Qual é a complexidade de tempo do algoritmo? 
A) O(V + E) 
B) O(V^2) 
C) O(E) 
D) O(V log V) 
**Resposta:** A) O(V + E) 
**Explicação:** A complexidade de tempo do algoritmo BFS é O(V + E), onde V é o 
número de vértices e E é o número de arestas. Isso se deve ao fato de que cada vértice e 
cada aresta é visitado uma vez. 
 
22. Um algoritmo de classificação por inserção é aplicado a uma lista de 20 elementos. 
Qual é o número máximo de comparações que o algoritmo pode fazer? 
A) 20 
B) 190 
C) 200 
D) 210 
**Resposta:** B) 190 
**Explicação:** O número máximo de comparações em um algoritmo de classificação 
por inserção ocorre quando a lista está em ordem reversa. Para n elementos, o número 
máximo de comparações é (n*(n-1))/2. Para n = 20, isso resulta em (20*19)/2 = 190. 
 
23. Um sistema de recomendação utiliza um vetor de características com 3 dimensões. 
Qual é a distância euclidiana entre os pontos (1, 2, 3) e (4, 5, 6)? 
A) 5 
B) 6 
C) 7 
D) 8 
**Resposta:** A) 5 
**Explicação:** A distância euclidiana entre dois pontos (x1, y1, z1) e (x2, y2, z2) é dada 
pela fórmula √((x2 - x1)² + (y2 - y1)² + (z2 - z1)²). Neste caso, a distância é √((4-1)² + (5-2)² + 
(6-3)²) = √(3² + 3² + 3²) = √(27) = 5. 
 
24. Um problema de otimização utiliza uma abordagem de programação dinâmica. Se o 
problema tem 3 subproblemas independentes, qual é o número total de subproblemas 
que precisam ser resolvidos? 
A) 3 
B) 6 
C) 9 
D) 27 
**Resposta:** A) 3 
**Explicação:** Se os subproblemas são independentes e não se sobrepõem, o número 
total de subproblemas que precisam ser resolvidos é igual ao número de subproblemas, 
que neste caso é 3. 
 
25. Um algoritmo de ordenação por seleção é aplicado a uma lista de 10 elementos. Qual 
é a complexidade de tempo do algoritmo? 
A) O(n) 
B) O(n log n) 
C) O(n^2) 
D) O(log n) 
**Resposta:** C) O(n^2) 
**Explicação:** A complexidade de tempo do algoritmo de ordenação por seleção é 
O(n^2) no pior caso, pois ele percorre a lista várias vezes para encontrar o menor 
elemento e ordenar a lista. 
 
26. Um banco de dados contém 3 tabelas, cada uma com 500 registros. Se você realizar 
uma junção externa entre essas tabelas, qual é o número máximo de registros que você 
pode esperar na tabela resultante? 
A) 500 
B) 1000 
C) 1500 
D) 2000 
**Resposta:** D) 2000 
**Explicação:** O número máximo de registros em uma junção externa pode ser a soma 
dos registros de todas as tabelas, caso não haja correspondências. Portanto, 500 + 500 + 
500 = 1500. 
 
27. Um algoritmo de aprendizado de máquina tem 3 hiperparâmetros que precisam ser 
ajustados. Se cada hiperparâmetro pode assumir 5 valores diferentes, quantas 
combinações diferentes de hiperparâmetros existem? 
A) 15 
B) 25 
C) 125 
D) 75 
**Resposta:** C) 125 
**Explicação:** O número total de combinações de hiperparâmetros é dado pelo produto 
dos valores possíveis para cada hiperparâmetro. Portanto, 5 * 5 * 5 = 125 combinações. 
 
28. Um modelo de previsão de vendas utiliza 3 variáveis independentes. Se a relação 
entre as variáveis é linear, qual é a forma da equação do modelo? 
A) y = a + b1*x1 + b2*x2 
B) y = a + b1*x1 + b2*x2 + b3*x3 
C) y = a + b1*x1 + b2*x2 + b3*x3 + b4*x4 
D) y = a + b*x 
**Resposta:** B) y = a + b1*x1 + b2*x2 + b3*x3 
**Explicação:** A forma da equação para um modelo de regressão linear com 3 variáveis 
independentes é dada por y = a + b1*x1 + b2*x2 + b3*x3. 
 
29. Um algoritmo de busca sequencial é aplicado a uma lista de 30 elementos. Qual é o 
número máximo de comparações que o algoritmo pode fazer?