Buscar

Complexidade de Algoritmo AV - 10 Pts

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 3, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 6, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 9, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Prévia do material em texto

1a Questão (Ref.: 202006216765)
	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(1)
	
	O(log N)
	
	O(Nlog N)
	
	
	 2a Questão (Ref.: 202006216767)
	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:  
		
	
	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. 
	
	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. 
	
	a primeira asserção é uma proposição falsa e a segunda uma proposição verdadeira. 
	
	
	 3a Questão (Ref.: 202006218757)
	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);
}
}
		
	
	Recursiva da exponenciação
	
	Recursiva da série de Fibonacci
	
	Iterativa da série de Fibonacci
	
	Iterativa da exponenciação
	
	Recursiva do fatorial
	
	
	 4a Questão (Ref.: 202006218755)
	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:
		
	
	360
	
	720
	
	240
	
	120
	
	1440
	
	
	 5a Questão (Ref.: 202006279620)
	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, é: 
		
	
	I, III, II, IV, V 
	
	V, IV, II, III, I 
	
	I, IV, V, III, II 
	
	I, II, III, IV, V 
	
	V, II, III, IV, I 
	
	
	 6a Questão (Ref.: 202006285466)
	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): 
		
	
	Insertion sort. 
	
	Quick sort e insertion sort. 
	
	Bubble sort. 
	
	Merge sort e bubble sort. 
	
	Quick sort e merge sort. 
	
	
	 7a Questão (Ref.: 202006216779)
	Observe a árvore binária a seguir: 
O caminhamento central (infixado) sobre essa árvore produz a sequência de visitação: 
		
	
	A - B - D - E - H - I - J - K - C - F - G 
	
	A - B - C - D - E - F - G - H - I - J - K 
	
	D - H - J - K - I - E - B - F - G - C - A 
	
	J - K - I - H - E - D - B - F - G - C - A 
	
	D - B - H - E - J - I - K - A - F - C - G 
	
	
	 8a Questão (Ref.: 202006216775)
	
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.  
	
	Se a árvore em tela for balanceada, depois da inserção de um nó 9, o nó 12 assume a raiz da árvore.  
	
	O percurso a percorrer nessa árvore na pré-ordem é 4 10 15 12 8.  
	
	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.  
	
	
	 9a Questão (Ref.: 202006218771)
	(CESGRANRIO - Banco da Amazônia - Técnico Científico - Banco de Dados - 2014)
O grafo anterior pode ser representado pela seguinte matriz:
		
	
	
	
	
	
	
	
	
	
	
	
	
	 10a Questão (Ref.: 202006218770)
	(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 é:
		
	
	15
	
	13
	
	16
	
	17
	
	14
:

Continue navegando