simples cly

Prévia do material em texto

d) O(E log V) 
 Resposta: b) O(VE + V^2 log V) 
 Explicação: O algoritmo de Johnson combina o algoritmo de Bellman-Ford e Dijkstra, 
resultando na complexidade mencionada. 
 
34. Se um algoritmo é classificado como "polinomial", isso significa que: 
 a) Seu tempo de execução é proporcional a uma função exponencial 
 b) Seu tempo de execução é limitado por um polinômio 
 c) Seu tempo de execução é constante 
 d) Seu tempo de execução é indefinido 
 Resposta: b) Seu tempo de execução é limitado por um polinômio 
 Explicação: Algoritmos polinomiais têm tempos de execução que podem ser expressos 
como um polinômio em relação ao tamanho da entrada. 
 
35. O que é um grafo orientado? 
 a) Um grafo que não possui arestas 
 b) Um grafo onde as arestas têm direção 
 c) Um grafo que é sempre conexo 
 d) Um grafo que possui ciclos 
 Resposta: b) Um grafo onde as arestas têm direção 
 Explicação: Em um grafo orientado, as arestas têm uma direção específica, indicando 
um relacionamento unidirecional entre os vértices. 
 
36. Qual é a complexidade de tempo do algoritmo de busca binária em uma lista de n 
elementos? 
 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 divide a lista em duas partes a cada iteração, resultando em 
uma complexidade logarítmica. 
 
37. O que caracteriza um algoritmo de divisão e conquista? 
 a) Ele resolve problemas de forma sequencial 
 b) Ele divide um problema em subproblemas menores e resolve cada um 
 c) Ele não utiliza recursão 
 d) Ele é sempre ineficiente 
 Resposta: b) Ele divide um problema em subproblemas menores e resolve cada um 
 Explicação: A técnica de divisão e conquista envolve dividir um problema em partes 
menores, resolver cada parte e combinar as soluções. 
 
38. Um grafo é chamado de árvore se: 
 a) É um grafo conectado sem ciclos 
 b) Tem um ciclo 
 c) É um grafo completo 
 d) Tem mais arestas do que vértices 
 Resposta: a) É um grafo conectado sem ciclos 
 Explicação: Uma árvore é um tipo especial de grafo que é conexo e não possui ciclos. 
 
39. Qual é a complexidade de tempo do algoritmo de QuickSelect? 
 a) O(n) 
 b) O(n log n) 
 c) O(n^2) 
 d) O(log n) 
 Resposta: a) O(n) 
 Explicação: O QuickSelect tem uma complexidade média de O(n) para encontrar o k-
ésimo menor elemento em um vetor. 
 
40. O que é um algoritmo de ordenação estável? 
 a) Um algoritmo que não altera a ordem de elementos iguais 
 b) Um algoritmo que sempre retorna a mesma ordem 
 c) Um algoritmo que é mais rápido que outros 
 d) Um algoritmo que não utiliza memória adicional 
 Resposta: a) Um algoritmo que não altera a ordem de elementos iguais 
 Explicação: Um algoritmo de ordenação estável mantém a ordem relativa de elementos 
iguais após a ordenação. 
 
41. Qual é a complexidade de tempo do algoritmo de RadixSort? 
 a) O(n log n) 
 b) O(n) 
 c) O(n^2) 
 d) O(log n) 
 Resposta: b) O(n) 
 Explicação: O RadixSort é um algoritmo de ordenação não comparativa que pode operar 
em tempo linear sob certas condições. 
 
42. O que caracteriza um problema de otimização? 
 a) A resposta é um número inteiro 
 b) A resposta é uma lista de números 
 c) O objetivo é maximizar ou minimizar uma função 
 d) O problema não tem solução 
 Resposta: c) O objetivo é maximizar ou minimizar uma função 
 Explicação: Problemas de otimização visam encontrar a melhor solução possível de 
acordo com um critério específico. 
 
43. Qual é a complexidade de tempo do algoritmo de Prim para encontrar a árvore 
geradora mínima em um grafo utilizando uma lista de adjacência? 
 a) O(E log V) 
 b) O(V^2) 
 c) O(E + V log V) 
 d) O(E^2) 
 Resposta: c) O(E + V log V) 
 Explicação: Quando implementado com uma lista de adjacência e uma fila de 
prioridade, o algoritmo de Prim tem essa complexidade. 
 
44. O que é um algoritmo de busca em profundidade (DFS)? 
 a) Um algoritmo que visita todos os vértices de um grafo em largura