simples cbj

Prévia do material em texto

b) O(V log V) 
 c) O(E log V) 
 d) O(V^2) 
 Resposta: c) O(E log V) 
 Explicação: O algoritmo de Dijkstra tem essa complexidade ao usar uma fila de 
prioridade. 
 
87. O que caracteriza um grafo bipartido? 
 a) Ele possui ciclos 
 b) Ele pode ser colorido com duas cores 
 c) Ele é sempre conexo 
 d) Ele tem um número par de vértices 
 Resposta: b) Ele pode ser colorido com duas cores 
 Explicação: Um grafo bipartido pode ser dividido em dois conjuntos de vértices, de 
modo que não haja arestas entre vértices do mesmo conjunto. 
 
88. Qual é a complexidade de tempo do algoritmo de Kruskal em um grafo denso? 
 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). 
 
89. O que caracteriza um problema de programação linear inteira? 
 a) A função objetivo é não linear 
 b) As restrições são lineares 
 c) As variáveis de decisão devem ser inteiras 
 d) O problema não tem solução 
 Resposta: c) As variáveis de decisão devem ser inteiras 
 Explicação: Problemas de programação linear inteira são aqueles em que as variáveis de 
decisão devem assumir valores inteiros. 
 
90. Qual é a complexidade de tempo do algoritmo de busca em profundidade (DFS) em 
um grafo não direcionado? 
 a) O(E) 
 b) O(V) 
 c) O(V + E) 
 d) O(V^2) 
 Resposta: c) O(V + E) 
 Explicação: O DFS visita cada vértice e aresta uma vez, resultando em uma 
complexidade de O(V + E). 
 
91. O que é um algoritmo de força bruta para resolver um problema de combinação? 
 a) Um algoritmo que utiliza programação dinâmica 
 b) Um algoritmo que tenta todas as combinações possíveis 
 c) Um algoritmo que não gera soluções 
 d) Um algoritmo que é sempre eficiente 
 Resposta: b) Um algoritmo que tenta todas as combinações possíveis 
 Explicação: Algoritmos de força bruta para combinações exploram todas as 
possibilidades para encontrar uma solução. 
 
92. Qual é a complexidade de tempo do algoritmo de busca de padrão de KMP? 
 a) O(n) 
 b) O(m) 
 c) O(n + m) 
 d) O(n^2) 
 Resposta: c) O(n + m) 
 Explicação: O algoritmo KMP tem complexidade O(n + m) ao pré-processar o padrão e 
buscar no texto. 
 
93. O que caracteriza um algoritmo de busca de padrão de Rabin-Karp? 
 a) Ele é ineficiente 
 b) Ele utiliza uma função hash para buscar padrões 
 c) Ele não altera a ordem dos elementos 
 d) Ele não utiliza recursão 
 Resposta: b) Ele utiliza uma função hash para buscar padrões 
 Explicação: O algoritmo Rabin-Karp utiliza uma função hash para buscar padrões de 
forma eficiente. 
 
94. Qual é a complexidade de tempo do algoritmo de busca de padrão de Boyer-Moore? 
 a) O(n) 
 b) O(m) 
 c) O(n + m) 
 d) O(nm) 
 Resposta: c) O(n + m) 
 Explicação: O algoritmo Boyer-Moore é eficiente em buscar padrões, utilizando 
informações do padrão para pular comparações. 
 
95. O que caracteriza um problema de programação inteira mista? 
 a) A função objetivo é não linear 
 b) As restrições são lineares 
 c) Algumas variáveis de decisão são inteiras e outras são contínuas 
 d) O problema não tem solução 
 Resposta: c) Algumas variáveis de decisão são inteiras e outras são contínuas 
 Explicação: Problemas de programação inteira mista são aqueles em que algumas 
variáveis são inteiras e outras podem ser contínuas. 
 
96. Qual é a complexidade de tempo do algoritmo de busca de padrão de Z-algorithm? 
 a) O(n) 
 b) O(m) 
 c) O(n + m) 
 d) O(nm) 
 Resposta: c) O(n + m)