Complexidade de Algoritimos AV1 - nota 10

Prévia do material em texto

29/09/2021 10:25 EPS
https://simulado.estacio.br/alunos/ 1/9
ALEX RODRIGUES DE SOUZA
Avaliação AV
 
 
202001551891 POLO ÁGUAS CLARAS I - BRASILIA - DF
 avalie seus conhecimentos
 RETORNAR À AVALIAÇÃO
Disciplina: EEX0030 - COMPLEXIDADE DE ALGORITMOS Período: 2021.3 EAD (GT) / AV
Aluno: ALEX RODRIGUES DE SOUZA Matrícula: 202001551891
Data: 29/09/2021 10:25:38 Turma: 9003
 ATENÇÃO
1. Veja abaixo, todas as suas respostas gravadas no nosso banco de dados.
2. Caso você queira voltar à prova clique no botão "Retornar à Avaliação".
 1a Questão (Ref.: 202005597706)
Uma lista ordenada de N números é inserida em uma pilha e depois retirada, sendo que, a cada
POP, o elemento retirado é inserido em um vetor de elementos. Após a completa inserção de todos
os elementos neste vetor, são feitas buscas de números na mesma. O tempo médio de busca de
um número neste elemento é: 
O(N)
O(N\(^2\))
O(log N)
O(Nlog N)
O(1)
javascript:voltar_avaliacoes()
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990626\n\nStatus da quest%C3%A3o: Liberada para Uso.');
29/09/2021 10:25 EPS
https://simulado.estacio.br/alunos/ 2/9
 2a Questão (Ref.: 202005597708)
Analise o custo computacional dos algoritmos a seguir, que calculam o valor de polinomio 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 \(a_n\) que é diferente de zero. 
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 complexida assintótica 
 PORQUE
1. Para o melhor caso, ambos possuem a complexidade O(n) 
 
A respeito dessas asserções, assinale a opção correta: 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990628\n\nStatus da quest%C3%A3o: Liberada para Uso.');
29/09/2021 10:25 EPS
https://simulado.estacio.br/alunos/ 3/9
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. 
as duas asserções são proposições verdadeiras, mas a segunda é uma justificativa correta da
primeira. 
tanto a primeira quanto a segunda asserções são proposições falsas. 
a primeira asserção é uma proposição falsa e a segunda uma proposição verdadeira. 
 3a Questão (Ref.: 202005599698)
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 da série de Fibonacci
Recursiva da exponenciação
Iterativa da exponenciação
Recursiva do fatorial
 4a Questão (Ref.: 202005599696)
Analise o seguinte código:
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992618\n\nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992616\n\nStatus da quest%C3%A3o: Liberada para Uso.');
29/09/2021 10:25 EPS
https://simulado.estacio.br/alunos/ 4/9
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:
120
360
240
720
1440
 5a Questão (Ref.: 202005660561)
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). 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4053481\n\nStatus da quest%C3%A3o: Liberada para Uso.');
29/09/2021 10:25 EPS
https://simulado.estacio.br/alunos/ 5/9
( ) 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. 
 
( ) É 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, é: 
I, IV, V, III, II 
V, II, III, IV, I 
V, IV, II, III, I 
I, III, II, IV, V 
I, II, III, IV, V 
 6a Questão (Ref.: 202005666407)
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 merge sort. 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4059327\n\nStatus da quest%C3%A3o: Liberada para Uso.');
29/09/2021 10:25 EPS
https://simulado.estacio.br/alunos/ 6/9
Bubble sort. 
Insertion sort. 
Merge sort e bubble sort. 
Quick sort e insertion sort. 
 7a Questão (Ref.: 202005597716)
Considerando a figura acima, que ilustra uma árvore de busca binária, assinale a opção correta. 
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. 
Transformando essa árvore em uma nova árvore de ordem 2, as folhas teriam de estar no nível
2. 
O percurso a percorrer nessa árvore na pré-ordem é 4 10 15 12 8. 
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. 
Se a árvore em tela for balanceada, depois da inserção de um nó 9, o nó 12 assume a raiz da
árvore. 
 8a Questão (Ref.: 202005597718)
Árvore AVL é uma árvore de busca autobalanceada. Isso significa que:
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990636\n\nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990638\n\nStatus da quest%C3%A3o: Liberada para Uso.');
29/09/2021 10:25 EPS
https://simulado.estacio.br/alunos/ 7/9
cada nó da árvore possui até três descendentes. 
as alturas das duas subárvores a partir de cada nó diferem no máximo em duas unidades. 
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 uma unidade. 
 9a Questão (Ref.: 202005599711)
(CESPE/CEBRASPE - TRT - 8ª Região (PA e AP) - Analista Judiciário - Tecnologia da Informação - 2016)
A quantidade de grau total do grafo na figura é:
17
16
15
14
13
 10a Questão (Ref.: 202005599712)
(CESGRANRIO - Banco da Amazônia - Técnico Científico - Banco de Dados - 2014)
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992631\n\nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992632\n\nStatus da quest%C3%A3o: Liberada para Uso.');
29/09/2021 10:25 EPS
https://simulado.estacio.br/alunos/ 8/9
O grafo anterior pode ser representado pela seguinte matriz:
29/09/2021 10:25 EPS
https://simulado.estacio.br/alunos/ 9/9
Autenticação para a Prova On-line
Casoqueira FINALIZAR a avaliação, digite o código de 4 carateres impresso abaixo.
ATENÇÃO: Caso finalize esta avaliação você não poderá mais modificar as suas respostas.
L89U Cód.: FINALIZAR
Obs.: Os caracteres da imagem ajudam a Instituição a evitar fraudes, que dificultam a gravação das
respostas.
Período de não visualização da avaliação: desde 28/09/2021 até 23/11/2021.