AV_complexidade_algoritmos

Prévia do material em texto

11/10/2021 11:24 EPS
https://simulado.estacio.br/alunos/?p0=186165540&user_cod=2738590&matr_integracao=202003441023 1/6
GABRIEL PEREIRA TEIXEIRA
Avaliação AV
202003441023 POLO CAMPO GRANDE - SALVADOR - BA
 avalie seus conhecimentos
1 ponto
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 é: 
 (Ref.: 202007475751)
1 ponto
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 que é
diferente de zero. 
Lupa Calc. Notas
 
VERIFICAR E ENCAMINHAR
Disciplina: EEX0030 - COMPLEXIDADE DE Período: 2021.3 EAD (GT)
Aluno: GABRIEL PEREIRA TEIXEIRA Matr.: 202003441023
Turma: 9001
 
Prezado(a) Aluno(a),
Responda a todas as questões com atenção. Somente clique no botão FINALIZAR PROVA ao ter certeza de que respondeu a
todas as questões e que não precisará mais alterá-las. 
 
A prova será SEM consulta. O aluno poderá fazer uso, durante a prova, de uma folha em branco, para rascunho. Nesta folha
não será permitido qualquer tipo de anotação prévia, cabendo ao aplicador, nestes casos, recolher a folha de rascunho do aluno.
Valor da prova: 10 pontos.
 
1.
O(Nlog N)
O(1)
O(N)
O(log N)
O(N )
 
2.
2
an
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:calculadora_on();
javascript:anotar_on();
11/10/2021 11:24 EPS
https://simulado.estacio.br/alunos/?p0=186165540&user_cod=2738590&matr_integracao=202003441023 2/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 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: 
 (Ref.: 202007475753)
1 ponto
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);
}
}
a primeira asserção é uma proposição verdadeira e a segunda uma
proposição falsa. 
as duas asserções são proposições verdadeiras, mas a segunda é uma justificativa
correta da primeira. 
a primeira asserção é uma proposição falsa e a segunda uma proposição
verdadeira. 
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ções são proposições falsas. 
 
3.
11/10/2021 11:24 EPS
https://simulado.estacio.br/alunos/?p0=186165540&user_cod=2738590&matr_integracao=202003441023 3/6
}
 (Ref.: 202007477743)
1 ponto
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:
 (Ref.: 202007477741)
1 ponto
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. 
Recursiva da exponenciação
Iterativa da série de Fibonacci
Recursiva da série de Fibonacci
Recursiva do fatorial
Iterativa da exponenciação
 
4.
120
240
720
1440
360
 
5.
11/10/2021 11:24 EPS
https://simulado.estacio.br/alunos/?p0=186165540&user_cod=2738590&matr_integracao=202003441023 4/6
 
( ) 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, é: 
 (Ref.: 202007538606)
1 ponto
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): 
 (Ref.: 202007544452)
1 ponto
Questão sem pergunta cadastrada.
 
Favor informar ao seu coordenador o código da questão (3990644) para que ela seja anulada e/ou tratada pela
diretoria de ensino.
 
 (Ref.: 202007475769)
1 ponto
Árvore de pesquisa é uma estrutura de dados eficiente para armazenar informação,
sendo particularmente adequada quando existe a necessidade de considerar todos ou
alguma combinação de registros. Assinale uma combinação correta desses registros. 
 (Ref.: 202007475760)
I, IV, V, III, II 
I, III, II, IV, V 
V, II, III, IV, I 
I, II, III, IV, V 
V, IV, II, III, I 
 
6.
Quick sort e merge sort. 
Quick sort e insertion sort. 
Bubble sort. 
Insertion sort. 
Merge sort e bubble sort. 
 
7.
 
8.
11/10/2021 11:24 EPS
https://simulado.estacio.br/alunos/?p0=186165540&user_cod=2738590&matr_integracao=202003441023 5/6
1 ponto
(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 é:
 (Ref.: 202007477756)
1 ponto
(CESGRANRIO - Banco da Amazônia - Técnico Científico - Banco de Dados - 2014)
O grafo anterior pode ser representado pela seguinte matriz:
 (Ref.: 202007477757)
Não é necessário indexar os registros. 
As operações de inserir, retirar e pesquisar são definidas. 
Utilização de estruturas de dados como lista, pilha e fila. 
Utilização de algoritmos de ordenação eficientes. 
Acesso direto e sequencial eficientes, facilidade de inserção e retirada de registro,
boa taxa de utilização de memória, utilização de memória primária e secundária. 
 
9.
17
15
16
13
14
 
10.
11/10/2021 11:24 EPS
https://simulado.estacio.br/alunos/?p0=186165540&user_cod=2738590&matr_integracao=202003441023 6/6
VERIFICAR E ENCAMINHAR
Legenda: Questão não respondida Questão não gravada Questão gravada
javascript:abre_colabore();