simples cfp

Prévia do material em texto

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: Um grafo dirigido é aquele em que as arestas têm uma direção específica, 
indicando um relacionamento unidirecional entre os vértices. 
 
66. Qual é a complexidade de tempo do algoritmo de Prim usando uma matriz de 
adjacência? 
 a) O(E log V) 
 b) O(V^2) 
 c) O(E + V log V) 
 d) O(E^2) 
 Resposta: b) O(V^2) 
 Explicação: Quando implementado com uma matriz de adjacência, o algoritmo de Prim 
tem complexidade O(V^2). 
 
67. O que caracteriza um problema NP-hard? 
 a) Pode ser resolvido em tempo polinomial 
 b) É tão difícil quanto qualquer problema em NP 
 c) Pode ser verificado em tempo polinomial 
 d) Não tem solução 
 Resposta: b) É tão difícil quanto qualquer problema em NP 
 Explicação: Um problema NP-hard é um problema para o qual todos os problemas em 
NP podem ser reduzidos em tempo polinomial. 
 
68. Qual é a complexidade de tempo do algoritmo de Kruskal usando uma lista de 
adjacência? 
 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, resultando em complexidade O(E 
log E). 
 
69. O que é um algoritmo de busca de padrão? 
 a) Um algoritmo que busca um elemento em uma lista não ordenada 
 b) Um algoritmo que busca um padrão em uma sequência 
 c) Um algoritmo que não utiliza recursão 
 d) Um algoritmo que é sempre ineficiente 
 Resposta: b) Um algoritmo que busca um padrão em uma sequência 
 Explicação: Algoritmos de busca de padrão são projetados para encontrar ocorrências 
de um padrão em uma sequência de caracteres ou números. 
 
70. Qual é a complexidade de tempo do algoritmo de A* em um grafo? 
 a) O(n) 
 b) O(log n) 
 c) O(n^2) 
 d) O(E + V log V) 
 Resposta: d) O(E + V log V) 
 Explicação: O algoritmo A* tem essa complexidade ao usar uma fila de prioridade para 
explorar os vértices. 
 
71. O que caracteriza um algoritmo de ordenação não comparativa? 
 a) Ele não utiliza comparações entre elementos 
 b) Ele é sempre ineficiente 
 c) Ele não altera a ordem dos elementos 
 d) Ele utiliza memória adicional 
 Resposta: a) Ele não utiliza comparações entre elementos 
 Explicação: Algoritmos de ordenação não comparativa, como CountingSort e RadixSort, 
não comparam elementos diretamente, mas utilizam contagem ou agrupamento. 
 
72. Qual é a complexidade de tempo do algoritmo de Dijkstra em um grafo denso? 
 a) O(E) 
 b) O(V log V) 
 c) O(E log V) 
 d) O(V^2) 
 Resposta: d) O(V^2) 
 Explicação: Em grafos densos, o algoritmo Dijkstra, quando implementado com uma 
matriz de adjacência, tem complexidade O(V^2). 
 
73. O que caracteriza um algoritmo de busca em largura (BFS)? 
 a) Ele visita os vértices em profundidade 
 b) Ele visita os vértices em largura 
 c) Ele não utiliza recursão 
 d) Ele não encontra ciclos 
 Resposta: b) Ele visita os vértices em largura 
 Explicação: O BFS explora todos os vértices em um nível antes de passar para o próximo 
nível. 
 
74. Qual é a complexidade de tempo do algoritmo de Bellman-Ford? 
 a) O(V) 
 b) O(E) 
 c) O(VE) 
 d) O(E^2) 
 Resposta: c) O(VE) 
 Explicação: O algoritmo Bellman-Ford relaxa todas as arestas V-1 vezes, resultando em 
complexidade O(VE). 
 
75. O que é um algoritmo de busca em profundidade iterativa? 
 a) Um algoritmo que combina DFS e BFS 
 b) Um algoritmo que usa recursão 
 c) Um algoritmo que explora todos os ramos até uma profundidade fixa 
 d) Um algoritmo que não utiliza memória adicional 
 Resposta: c) Um algoritmo que explora todos os ramos até uma profundidade fixa