GABARITO AVS ALGORITMOS E COMPLEXIDADE

Prévia do material em texto

15/04/2024, 14:28 EPS
https://simulado.estacio.br/alunos/ 1/4
Disciplina: ALGORITMOS E COMPLEXIDADE  AVS
Aluno: MARIANA NASCIMENTO LOBATO 202205092674
Turma: 9001
DGT1348_AVS_202205092674 (AG)   13/03/2024 15:40:32 (F) 
Avaliação: 10,00 pts Nota SIA: 10,00 pts
Estação de trabalho liberada pelo CPF 12999541708 com o token 854218 em 13/03/2024 15:39:02.
 
ENSINEME: ALGORITMOS DE ORDENAÇÃO AVANÇADOS  
 
 1. Ref.: 7925951 Pontos: 1,00  / 1,00
O "Selection Sort", ou ordenação por seleção, é outro algoritmo simples de ordenação. O princípio básico deste
método é dividir o array em duas partes: a parte já ordenada e a parte não ordenada.
 
Em relação à e�ciência para grandes conjuntos de dados, como o ¿Selection Sort¿ se comporta?
Muito e�ciente.
Altamente otimizado para grandes conjuntos.
Depende do tipo de dados.
 Ine�ciente.
Medianamente e�ciente.
 2. Ref.: 4059327 Pontos: 1,00  / 1,00
Se f é uma função de complexidade para um algoritmo F, então, O(f) é considerada a complexidade
assintótica ou o comportamento assintótico do algoritmo F. Assinale a alternativa que apresenta somente
algoritmos com complexidade assintótica, quando f(n) = O(n log n): 
Quick sort e insertion sort. 
Bubble sort. 
Merge sort e bubble sort. 
 Quick sort e merge sort. 
Insertion sort. 
 3. Ref.: 7925949 Pontos: 1,00  / 1,00
O "Insertion Sort", ou ordenação por inserção, é um algoritmo de ordenação simples que constrói a lista �nal um item
por vez.
Qual é uma das vantagens do algoritmo "Insertion Sort"?
Ele reorganiza os elementos com a mesma chave.
Não precisa de nenhuma comparação.
Ele realiza o menor número de comparações independentemente da disposição inicial dos dados.
Ele é sempre o algoritmo mais rápido.
 Ele se comporta de maneira ideal quando a matriz já está quase ordenada.
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7925951.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7925951.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4059327.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4059327.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7925949.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7925949.');
15/04/2024, 14:28 EPS
https://simulado.estacio.br/alunos/ 2/4
 
ENSINEME: ALGORITMOS EM ÁRVORES BINÁRIA E ÁRVORE AVL  
 
 4. Ref.: 3990638 Pontos: 1,00  / 1,00
Árvore AVL é uma árvore de busca autobalanceada. Isso signi�ca que:
 as alturas das duas subárvores a partir de cada nó diferem no máximo em uma unidade. 
cada nó da árvore possui até três descendentes.  
as alturas das duas subárvores a partir de cada nó são exatamente iguais. 
pode possuir até duas raízes.  
as alturas das duas subárvores a partir de cada nó diferem no máximo em duas unidades.  
 5. Ref.: 8022475 Pontos: 1,00  / 1,00
Ao construir um sistema de indexação para um banco de dados, um engenheiro de software escolhe usar uma árvore
AVL devido à sua e�ciência. A árvore precisa ser mantida balanceada após cada inserção e remoção para garantir um
desempenho otimizado. O balanceamento é essencial para manter a altura da árvore dentro do limite desejado.
 
Qual é a consequência de uma árvore binária de busca estar desbalanceada?
Complexidade de tempo de busca reduzida para O(log n).
 Aumento da complexidade de tempo de busca.
Aumento da e�ciência de busca.
Redução do espaço necessário para armazenamento.
Conversão automática para árvore AVL.
 
ENSINEME: ALGORITMOS EM GRAFOS  
 
 6. Ref.: 3992622 Pontos: 1,00  / 1,00
(COMPERVE - UFRN - Engenheiro - Engenharia da Computação - 2019)
 
O código abaixo pode ser utilizado para atravessar um grafo:
 
Entrada: um gráfico G e um vértice v de G
 
Saída: todos os vértices alcançáveis de v marcados
 
função DFS(G,v):
 
 marque v
 
 para todas as arestas adjacentes a v, faça
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990638.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990638.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 8022475.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 8022475.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992622.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992622.');
15/04/2024, 14:28 EPS
https://simulado.estacio.br/alunos/ 3/4
 
 se vértice w não estiver marcado, então
 
 Chame recursivamente DFS(G,w)
 
 fim se
 
 fim para
 
fim função
 
Entre os diversos tipos de algoritmos utilizados para atravessar grafos, esse código implementa o algoritmo:
 Busca em profundidade ou depth �rst search.
Busca pelo caminho mínimo (shortest path).
Busca em largura ou breadth �rst search.
Busca exaustiva ou brute force search.
Busca melhor-primeiro ou best �rst search.
 
ENSINEME: ANÁLISE DE ALGORITMO  
 
 7. Ref.: 3990623 Pontos: 1,00  / 1,00
Registros são exemplos de tipos de dados heterogêneos. Assim, sobre tipos de dados elementares e
estruturados, é correto a�rmar que os elementos de um registro são de tamanhos potencialmente
diferentes e residem em posições de memória: 
espalhadas 
aleatórias 
 adjacentes
�exíveis 
procedimentais 
 8. Ref.: 3990629 Pontos: 1,00  / 1,00
Considere os algoritmos a seguir e as suas correspondentes complexidades indicadas:  
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990623.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990623.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990629.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990629.');
15/04/2024, 14:28 EPS
https://simulado.estacio.br/alunos/ 4/4
Estão corretas apenas as complexidades indicadas para os algoritmos: 
II, III, IV e V.
I, III, IV e V.
I, II e IV.
II, III e V.
 I, II e III.
 
ENSINEME: RECURSIVIDADE  
 
 9. Ref.: 3992618 Pontos: 1,00  / 1,00
O código abaixo é uma implementação:
 
public class Misterio {
public static long Misterio(long x) {
if (x == 1)
return 1;
else
return x * Misterio(x-1);
}
}
Iterativa da série de Fibonacci
 Recursiva do fatorial
Recursiva da série de Fibonacci
Recursiva da exponenciação
Iterativa da exponenciação
 10. Ref.: 8023012 Pontos: 1,00  / 1,00
Um algoritmo recursivo é projetado para encontrar o elemento máximo em uma lista de números. A função divide a
lista ao meio a cada chamada, comparando os elementos até encontrar o maior.
Comando:
Qual abordagem recursiva é mais adequada para este algoritmo?
Recursividade múltipla.
Recursão de cauda.
 Recursividade linear.
Recursividade indireta.
Recursividade aninhada.
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992618.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992618.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 8023012.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 8023012.');