simples chs

Prévia do material em texto

Explicação: O algoritmo A* tem essa complexidade ao usar uma fila de prioridade para 
explorar os vértices. 
 
55. O que caracteriza um algoritmo de ordenação in-place? 
 a) Ele não utiliza memória adicional 
 b) Ele utiliza memória adicional 
 c) Ele é sempre eficiente 
 d) Ele não altera a ordem dos elementos 
 Resposta: a) Ele não utiliza memória adicional 
 Explicação: Algoritmos de ordenação in-place ordenam os elementos usando apenas 
uma quantidade constante de espaço adicional. 
 
56. Qual é a complexidade de tempo do algoritmo de ShellSort? 
 a) O(n log n) 
 b) O(n^2) 
 c) O(n^(3/2)) 
 d) O(log n) 
 Resposta: c) O(n^(3/2)) 
 Explicação: O ShellSort tem complexidade variável dependendo da sequência de 
incrementos, mas em média é O(n^(3/2)). 
 
57. O que é um grafo ponderado? 
 a) Um grafo que tem arestas com pesos 
 b) Um grafo que não possui arestas 
 c) Um grafo que é sempre conexo 
 d) Um grafo que possui ciclos 
 Resposta: a) Um grafo que tem arestas com pesos 
 Explicação: Um grafo ponderado é aquele em que cada aresta é atribuída a um valor ou 
peso que representa algum custo ou distância. 
 
58. Qual é a complexidade de tempo do algoritmo de CountingSort? 
 a) O(n) 
 b) O(n log n) 
 c) O(n^2) 
 d) O(log n) 
 Resposta: a) O(n) 
 Explicação: O CountingSort é um algoritmo de ordenação não comparativa que opera 
em tempo linear quando o intervalo dos valores é limitado. 
 
59. O que caracteriza um problema de programação linear? 
 a) A função objetivo é não linear 
 b) As restrições são lineares 
 c) O problema não tem solução 
 d) A solução é sempre inteira 
 Resposta: b) As restrições são lineares 
 Explicação: Problemas de programação linear têm uma função objetivo e restrições que 
são expressas como equações lineares. 
 
60. Qual é a complexidade de tempo do algoritmo de BogoSort? 
 a) O(n) 
 b) O(n log n) 
 c) O(n!) 
 d) O(log n) 
 Resposta: c) O(n!) 
 Explicação: O BogoSort é um algoritmo extremamente ineficiente que gera permutações 
aleatórias até encontrar a ordenação correta, resultando em complexidade O(n!). 
 
61. O que é um grafo acíclico? 
 a) Um grafo que possui ciclos 
 b) Um grafo que não possui ciclos 
 c) Um grafo que é sempre conexo 
 d) Um grafo que possui arestas direcionadas 
 Resposta: b) Um grafo que não possui ciclos 
 Explicação: Um grafo acíclico é aquele que não contém ciclos, significando que não há 
caminhos que retornam ao mesmo vértice. 
 
62. Qual é a complexidade de tempo do algoritmo de Dijkstra em um grafo esparso? 
 a) O(E) 
 b) O(V log V) 
 c) O(E log V) 
 d) O(V^2) 
 Resposta: c) O(E log V) 
 Explicação: Em um grafo esparso, o algoritmo Dijkstra tem essa complexidade ao usar 
uma fila de prioridade. 
 
63. O que caracteriza um problema de satisfatibilidade booleana (SAT)? 
 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 objetivo é determinar se uma expressão booleana pode ser satisfeita 
 Resposta: d) O objetivo é determinar se uma expressão booleana pode ser satisfeita 
 Explicação: O problema SAT pergunta se existe uma atribuição de variáveis que torna 
uma expressão booleana verdadeira. 
 
64. Qual é a complexidade de tempo do algoritmo de Floyd-Warshall para encontrar todos 
os caminhos mais curtos em um grafo? 
 a) O(V^2) 
 b) O(E log V) 
 c) O(V^3) 
 d) O(E + V) 
 Resposta: c) O(V^3) 
 Explicação: O algoritmo Floyd-Warshall utiliza três loops aninhados, resultando em uma 
complexidade de O(V^3). 
 
65. O que é um grafo dirigido? 
 a) Um grafo que não possui arestas