COMPLEXIDADE DE ALGORITMOS - AV

Prévia do material em texto

24/11/2022 10:21 EPS
https://simulado.estacio.br/alunos/ 1/6
RICARDO MOREIRA DA SILVA
202001449663
 
Disciplina: COMPLEXIDADE DE ALGORITMOS AV
Aluno: RICARDO MOREIRA DA SILVA 202001449663
Professor: JHONATAN ALVES
 Turma: 9001
EEX0030_AV_202001449663 (AG) 16/11/2022 10:48:53 (F) 
Avaliação:
10,0
Av. Parcial.:
2,0
Nota SIA:
10,0 pts
 
 
 
ENSINEME: ALGORITMOS DE ORDENAÇÃO AVANÇADOS 
 
 1. Ref.: 4053481 Pontos: 1,00 / 1,00
Correlacione os algoritmos internos de ordenação de listas com sua descrição: 
 
I. Bubble sort 
II. Ordenação por seleção 
III. Ordenação por inserção 
IV. Shell sort 
V. Quick sort 
 
( ) Escolhe-se um pivô e particiona-se a lista em duas sublistas - uma com os
elementos menores que ele e outra com os maiores, que, ao serem ordenadas e
combinadas com o pivô, geram uma lista ordenada. O processo é aplicado às partições
para ordená-las. Embora tenha uma complexidade de pior caso de O(n2 ), no caso
médio, é de O(n log n). 
 
( ) Encontra-se o menor item do vetor. Troca-se com o item da primeira posição do
vetor. Repetem-se essas duas operações com os n − 1 itens restantes; depois, com os n
− 2 itens; até que reste apenas um elemento. 
 
( ) Método preferido dos jogadores de cartas. A cada momento, existem duas partes na
lista ¿ uma ordenada (destino) e outra não ordenada (fonte). Inicialmente, a lista
destino tem apenas o primeiro elemento, e a fonte, os demais elementos. Em cada
passo, a partir de i=2, seleciona-se o i-ésimo item da lista fonte. Deve-se colocá-lo no
lugar apropriado na lista destino, de acordo com o critério de ordenação. 
 
Educational Performace Solution EPS ® - Alunos 
javascript:voltar();
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4053481.');
javascript:alert('Educational Performace Solution\n\nEPS: M%C3%B3dulo do Aluno\n\nAxiom Consultoria em Tecnologia da Informa%C3%A7%C3%A3o Ltda.')
24/11/2022 10:21 EPS
https://simulado.estacio.br/alunos/ 2/6
( ) É uma extensão de outro algoritmo de ordenação conhecido e permite trocas de
elementos distantes um do outro, não necessariamente adjacentes. Os itens separados
de h posições são rearranjados. Todo h-ésimo item leva a uma lista ordenada. Tal lista é
dita estar h-ordenada. 
 
( ) Varre-se a lista, trocando de posição os elementos adjacentes fora de ordem. Varre-
se a lista até que não haja mais trocas. Neste caso, a lista está ordenada. 
 
A sequência correta, de cima para baixo, é: 
 V, II, III, IV, I 
I, IV, V, III, II 
I, III, II, IV, V 
I, II, III, IV, V 
V, IV, II, III, I 
 
 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): 
Merge sort e bubble sort. 
Bubble sort. 
 Quick sort e merge sort. 
Insertion sort. 
Quick sort e insertion sort. 
 
 
ENSINEME: ALGORITMOS EM ÁRVORES BINÁRIA E ÁRVORE AVL 
 
 3. Ref.: 3990636 Pontos: 1,00 / 1,00
Considerando a figura acima, que ilustra uma árvore de busca binária, assinale a opção
correta. 
Se a árvore em questão não for balanceada, então, com a remoção do nó 8, o nó 12
deve assumir a raiz da árvore. 
O percurso a percorrer nessa árvore na pré-ordem é 4 10 15 12 8. 
Educational Performace Solution EPS ® - Alunos 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4059327.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990636.');
javascript:alert('Educational Performace Solution\n\nEPS: M%C3%B3dulo do Aluno\n\nAxiom Consultoria em Tecnologia da Informa%C3%A7%C3%A3o Ltda.')
24/11/2022 10:21 EPS
https://simulado.estacio.br/alunos/ 3/6
Transformando essa árvore em uma nova árvore de ordem 2, as folhas teriam de
estar no nível 2. 
Se a referida árvore for balanceada, a inserção de um nó 5 fará que ele tome o
lugar do nó 4, passando a ser o nó 5 a raiz da subárvore. 
 Se a árvore em tela for balanceada, depois da inserção de um nó 9, o nó 12 assume
a raiz da árvore. 
 
 4. Ref.: 3990640 Pontos: 1,00 / 1,00
Observe a árvore binária a seguir: 
O caminhamento central (infixado) sobre essa árvore produz a sequência de visitação: 
A - B - C - D - E - F - G - H - I - J - K 
 D - B - H - E - J - I - K - A - F - C - G 
J - K - I - H - E - D - B - F - G - C - A 
A - B - D - E - H - I - J - K - C - F - G 
D - H - J - K - I - E - B - F - G - C - A 
 
 
ENSINEME: ALGORITMOS EM GRAFOS 
 
 5. Ref.: 3992628 Pontos: 1,00 / 1,00
(CESGRANRIO - Transpetro - Analista de Sistemas Júnior - Processos de Negócio - 2018)
Uma das medidas de qualidade do código de um software é a Complexidade, que pode ser medida por meio da
complexidade ciclomática.
Considere um grafo de fluxo que possui 5 nós e 12 arcos. Qual a complexidade ciclomática desse grafo?
15
17
 9
11
19
Educational Performace Solution EPS ® - Alunos 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990640.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992628.');
javascript:alert('Educational Performace Solution\n\nEPS: M%C3%B3dulo do Aluno\n\nAxiom Consultoria em Tecnologia da Informa%C3%A7%C3%A3o Ltda.')
24/11/2022 10:21 EPS
https://simulado.estacio.br/alunos/ 4/6
 
 6. Ref.: 3992629 Pontos: 1,00 / 1,00
(FCC - ARTESP - Agente de Fiscalização à Regulação de Transporte - Tecnologia de Informação - 2017)
Considere a estrutura abaixo que representa um problema de rotas em pequena escala:
Considere, por hipótese, que se solicitou a um Agente de Fiscalização à Regulação de Transporte da ARTESP
utilizar alguma estratégia lógica para, partindo do ponto 1, chegar ao ponto 6 usando a menor rota. De um
mesmo ponto pode haver mais de uma rota, com distâncias diferentes. A lógica correta utilizada pelo Agente,
em função dos pontos a serem percorridos, foi:
{6} {4} {5,3} {2,1} {1}, caminho mais curto 6-4-3-5-2-1, que é igual a 1-2-5-3-
4-6.
{1} {2} {4} {6}, caminho mais curto 1-2-4-6.
{6} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual a 1-3-4-6.
{1} {2,3} {2,4} {5,6} {6}, caminho mais curto 1-2-5-6.
 {1} {3,2} {4,5} {6}, caminho mais curto 1-3-4-6.
 
 
ENSINEME: ANÁLISE DE ALGORITMO 
 
 7. Ref.: 6112507 Pontos: 1,00 / 1,00
Uma tarefa essencial quando começamos a aprender uma nova linguagem de programação é conhecer e saber
manipular as suas estruturas básicas de dados. Nesse sentido, um vetor é uma coleção de variáveis de:
Diferentes tipos de dados em sequência na memória. 
Diferentes tipos de dados distribuídos pela memória. 
Registros alocadas em sequência na memória. 
Tipo de dado homogêneo distribuído pela memória. 
 Tipo de dado homogêneo em sequência na memória. 
 
 8. Ref.: 7625308 Pontos: 1,00 / 1,00
Analise o custo computacional dos algoritmos a seguir, que calculam o valor
de polinômio de grau n da forma onde os coeficientes
são números de ponto flutuante armazenados no vetor [a..n], e o valor de n é maior que
zero. Todos os coeficientes podem assumir qualquer valor, exceto o coeficiente que é
diferente de zero. 
an
Educational Performace Solution EPS ® - Alunos 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992629.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6112507.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7625308.');
javascript:alert('Educational Performace Solution\n\nEPS: M%C3%B3dulo do Aluno\n\nAxiom Consultoria em Tecnologia da Informa%C3%A7%C3%A3o Ltda.')
24/11/2022 10:21 EPS
https://simulado.estacio.br/alunos/ 5/6
Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta
entre elas. 
1. Os algoritmos possuem a mesma complexidade assintótica 
 PORQUE
1. Para o melhor caso, ambos possuem a complexidade O(n) 
 
A respeito dessas asserções, assinale a opção correta: 
a primeira asserção é uma proposição verdadeira e a segunda uma
proposição falsa. 
as duas asserções são proposições verdadeiras e a segunda nãoé a justificativa
correta da primeira. 
tanto a primeira quanto a segunda asserção são proposições falsas. 
 a primeira asserção é uma proposição falsa e a segunda uma proposição
verdadeira. 
as duas asserções são proposições verdadeiras, mas a segunda é uma justificativa
correta da primeira. 
 
 
ENSINEME: RECURSIVIDADE 
 
 9. Ref.: 3992581 Pontos: 1,00 / 1,00
Ano: 2019 Banca: Quadrix Órgão: Prefeitura de Jataí - GO Prova: Quadrix - 2019 - Prefeitura de Jataí - GO -
Analista de Tecnologia da Informação
A situação em que dois subprogramas fazem chamadas recíprocas, como, por exemplo, um subprograma P faz
uma chamada a um subprograma J, que, por sua vez, faz uma chamada a P, é caracterizada como uma
Recursividade direta
Lista circular
Lista linear simples
 Recursividade indireta
Recursividade simplesEducational Performace Solution EPS ® - Alunos 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992581.');
javascript:alert('Educational Performace Solution\n\nEPS: M%C3%B3dulo do Aluno\n\nAxiom Consultoria em Tecnologia da Informa%C3%A7%C3%A3o Ltda.')
24/11/2022 10:21 EPS
https://simulado.estacio.br/alunos/ 6/6
 
 10. Ref.: 3992616 Pontos: 1,00 / 1,00
Analise o seguinte código:
 
public static double recursive (double d) {
if (d <= 1) {
return 1;
} else {
return d * recursive(d - 1);
}
}
 
Assinale o conteúdo que será exibido na saída do programa quando a função for chamada com o parâmetro 6:
1440
120
360
 720
240
 
 
 
Educational Performace Solution EPS ® - Alunos 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992616.');
javascript:alert('Educational Performace Solution\n\nEPS: M%C3%B3dulo do Aluno\n\nAxiom Consultoria em Tecnologia da Informa%C3%A7%C3%A3o Ltda.')