Prova Estácio - Complexidade de Algoritmos

Prévia do material em texto

Disciplina: EEX0030 - COMPLEXIDADE DE Período: 2022.2 EAD (GT) 
Aluno: Matr.: 202012017875 
 Turma: 9001 
 
 
 
1 ponto 
 
1. 
 
 
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.: 202016010288) 
 
 
 O(log N) 
 
 O(N2 
) 
 
 O(Nlog N) 
 
 O(1) 
 
 O(N) 
 
 
 
 
1 ponto 
 
2. 
 
 
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 an 
 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 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: 
 (Ref.: 202019644970) 
 
 
 
as duas asserções são proposições verdadeiras, mas a segunda é uma 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. 
 
 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. 
 
 
 
 
 
 
 
 
 
1 ponto 
 
3. 
 
 
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); 
} 
} 
 (Ref.: 202016012280) 
 
 
 Recursiva do fatorial 
 
 Recursiva da exponenciação 
 
 Recursiva da série de Fibonacci 
 
 Iterativa da exponenciação 
 
 Iterativa da série de Fibonacci 
 
 
 
 
1 ponto 
 
4. 
 
 
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 
 (Ref.: 202016012243) 
 
 
 Lista circular 
 
 Recursividade direta 
 
 Lista linear simples 
 
 Recursividade indireta 
 
 Recursividade simples 
 
 
 
1 ponto 
 
5. 
 
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. 
 
( ) É 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.: 202016073143) 
 
 
 V, II, III, IV, I 
 
 I, III, II, IV, V 
 
 V, IV, II, III, I 
 
 I, II, III, IV, V 
 
 I, IV, V, III, II 
 
 
 
 
1 ponto 
 
6. 
 
 
O algoritmo bubble sort é popular, mesmo que ineficiente. Usando esse algoritmo para 
ordenar um vetor em ordem crescente, contendo os números [ 5, 4, 1, 3, 2 ], serão feitas: 
 (Ref.: 202016078981) 
 
 
 10 comparações e 10 trocas. 
 
 16 comparações e 9 trocas. 
 
 10 comparações e 8 trocas. 
 
 10 comparações e 9 trocas. 
 
 6 comparações e 10 trocas. 
 
 
 
 
1 ponto 
 
7. 
 
 
Á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.: 202016010297) 
 
 
 Utilização de algoritmos de ordenação eficientes. 
 
 Utilização de estruturas de dados como lista, pilha e fila. 
 
 Não é necessário indexar os registros. 
 
 
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. 
 
 As operações de inserir, retirar e pesquisar são definidas. 
 
 
 
 
1 ponto 
 
8. 
 
 
Imagine que temos números de 1 a 100 em uma árvore de pesquisa binária (ABP). Agora 
queremos procurar o número 50. Assinale a alternativa que apresenta a possível sequência 
de elementos da árvore consultada. 
 (Ref.: 202016010296) 
 
 
 40 - 60 - 45 - 48 - 50. 
 
 42 - 60 - 20 - 48 - 50. 
 
 40 - 15 - 45 - 30 - 50. 
 
 40 - 10 - 45 - 30 - 50. 
 
 42 - 60 - 20 - 30 - 50. 
 
 
 
 
1 ponto 
 
9. 
 
 
(IBGE - Analista Censitário - Análise de Sistemas - Desenvolvimento de 
Aplicações - Web Mobile - 2017) 
Observe a figura a seguir que ilustra relações entre colegas e seus interesses: 
 
O tipo de Banco de Dados NoSQL, não relacional, que armazena tais 
informações, utilizando estruturas de vértices e arestas, com propriedades 
associadas, é o: 
 (Ref.: 202016012292) 
 
 
 Chave-valor 
 
 Tabular 
 
 Documento 
 
 Grafo 
 
 Colunar 
 
 
 
 
1 ponto 
 
10. 
 
 
(CESGRANRIO - Banco da Amazônia - Técnico Científico - Banco de Dados - 
2014) 
 
O grafo anterior pode ser representado pela seguinte matriz: 
 (Ref.: 202016012294)