simples csh

Prévia do material em texto

b) Não tem solução 
 c) Tem infinitas soluções 
 d) É inconsistente 
 Resposta: c) Tem infinitas soluções 
 Explicação: Se o determinante de A é zero, a matriz é singular, o que implica que o 
sistema tem infinitas soluções ou nenhuma, dependendo do vetor b. 
 
4. Um algoritmo de ordenação por seleção tem um tempo de execução em média de: 
 a) O(n) 
 b) O(n log n) 
 c) O(n^2) 
 d) O(log n) 
 Resposta: c) O(n^2) 
 Explicação: O algoritmo de ordenação por seleção percorre a lista para encontrar o 
menor elemento e o coloca na posição correta, repetindo esse processo. Portanto, a 
complexidade no pior caso é O(n^2). 
 
5. Qual é a complexidade de tempo do algoritmo de Dijkstra para encontrar o caminho 
mais curto em um grafo denso com n vértices? 
 a) O(n) 
 b) O(n^2) 
 c) O(n log n) 
 d) O(n^3) 
 Resposta: b) O(n^2) 
 Explicação: O algoritmo de Dijkstra, quando implementado com uma matriz de 
adjacência, tem complexidade O(n^2) em grafos densos, pois precisa verificar todos os 
vértices. 
 
6. Dado um vetor com 100 elementos, qual é o número máximo de comparações 
necessárias para encontrar o menor elemento usando uma busca linear? 
 a) 50 
 b) 99 
 c) 100 
 d) 101 
 Resposta: b) 99 
 Explicação: Em uma busca linear, o algoritmo compara cada elemento do vetor. Para 
encontrar o menor elemento, no pior caso, ele precisa comparar todos os outros 99 
elementos. 
 
7. Se um algoritmo tem uma complexidade de tempo de O(n^3), qual é o tempo de 
execução aproximado para n = 100? 
 a) 1000 
 b) 10000 
 c) 1000000 
 d) 1000000000 
 Resposta: c) 1000000 
 Explicação: O tempo de execução é proporcional a n^3. Assim, para n = 100, temos 
100^3 = 1,000,000. 
 
8. Um problema de programação dinâmica pode ser resolvido em tempo polinomial se: 
 a) Ele pode ser dividido em subproblemas independentes 
 b) Ele pode ser dividido em subproblemas sobrepostos 
 c) Ele não pode ser resolvido por recursão 
 d) Ele não tem solução 
 Resposta: b) Ele pode ser dividido em subproblemas sobrepostos 
 Explicação: A programação dinâmica é uma técnica que resolve problemas complexos 
dividindo-os em subproblemas que se sobrepõem, armazenando os resultados para 
evitar cálculos repetidos. 
 
9. Qual é a complexidade de tempo do algoritmo de Floyd-Warshall para encontrar todos 
os caminhos mais curtos em um grafo? 
 a) O(n) 
 b) O(n^2) 
 c) O(n^3) 
 d) O(n log n) 
 Resposta: c) O(n^3) 
 Explicação: O algoritmo Floyd-Warshall utiliza três loops aninhados para calcular os 
caminhos mais curtos entre todos os pares de vértices, resultando em uma complexidade 
de O(n^3). 
 
10. Em um problema de otimização, se a função objetivo é não linear, qual método pode 
ser usado para encontrar a solução? 
 a) Programação Linear 
 b) Programação Dinâmica 
 c) Algoritmos Genéticos 
 d) Busca Binária 
 Resposta: c) Algoritmos Genéticos 
 Explicação: Algoritmos genéticos são usados para resolver problemas de otimização em 
espaços de busca complexos, especialmente quando a função objetivo é não linear e não 
convexa. 
 
11. Um algoritmo de força bruta para resolver um problema de combinação de 10 
elementos tem complexidade de tempo de: 
 a) O(10) 
 b) O(10!) 
 c) O(2^10) 
 d) O(10^2) 
 Resposta: b) O(10!) 
 Explicação: O número de combinações de 10 elementos é dado por 10!, que é a 
complexidade de tempo do algoritmo de força bruta para gerar todas as combinações. 
 
12. Qual é a complexidade de tempo do algoritmo de Kruskal para encontrar a árvore 
geradora mínima em um grafo? 
 a) O(E log E) 
 b) O(V^2) 
 c) O(E + V log V) 
 d) O(E^2) 
 Resposta: a) O(E log E) 
 Explicação: O algoritmo de Kruskal ordena as arestas do grafo, o que leva O(E log E) 
tempo, onde E é o número de arestas.