COMPLEXIDADE DE ALGORITMOS AV2022

Prévia do material em texto

Disciplina: COMPLEXIDADE DE ALGORITMOS 
	AV
	Aluno: 
	
	Professor:  
 
	Turma: 
	
	) 
			Avaliação:
10,0
	Av. Parcial.:
2,0
	Nota SIA:
10,0 pts
	 
		
	ENSINEME: ALGORITMOS DE ORDENAÇÃO AVANÇADOS
	 
	 
	 1.
	Ref.: 4059323
	Pontos: 1,00  / 1,00
	
	O algoritmo de ordenação mais eficiente para um conjunto grande de elementos randomicamente inseridos é: 
		
	
	Selection sort 
	
	Bubble sort 
	
	Insert sort 
	
	Shell sort 
	 
	Quick sort 
	
	
	 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. 
	
	Insertion sort. 
	
	Bubble sort. 
	
	Quick sort e insertion sort. 
	 
	Quick sort e merge sort. 
	
	
	 
		
	ENSINEME: ALGORITMOS EM ÁRVORES BINÁRIA E ÁRVORE AVL
	 
	 
	 3.
	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: 
		
	
	D - H - J - K - I - E - B - F - G - C - A 
	
	A - B - D - E - H - I - J - K - C - F - G 
	
	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 
	
	
	 4.
	Ref.: 3990638
	Pontos: 1,00  / 1,00
	
	Árvore AVL é uma árvore de busca autobalanceada. Isso significa que:
		
	 
	as alturas das duas subárvores a partir de cada nó diferem no máximo em uma unidade. 
	
	as alturas das duas subárvores a partir de cada nó diferem no máximo em duas unidades.  
	
	cada nó da árvore possui até três descendentes.  
	
	pode possuir até duas raízes.  
	
	as alturas das duas subárvores a partir de cada nó são exatamente iguais. 
	
	
	 
		
	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?
		
	
	19
	
	17
	 
	9
	
	15
	
	11
	
	
	 6.
	Ref.: 3992624
	Pontos: 1,00  / 1,00
	
	(Adaptado de: DPE-RJ - Técnico Superior Especializado - Tecnologia da Informação - 2019)
Para que um sistema seja testado adequadamente, é preciso realizar uma quantidade mínima de testes. Para apoiar essa definição, foi criada a Complexidade Ciclomática de McCabe, com fundamentação na teoria dos grafos. Essa técnica define uma métrica de software que fornece uma medida quantitativa da complexidade lógica de um programa, apresentando um limite superior para a quantidade de casos de testes de software que devem ser conduzidos.
 
A Complexidade Ciclomática pode ser calculada tanto pelo número de regiões quanto pelo número de arestas e nós.
 
Complexidade é calculada pela fórmula CC = arestas - nós  + 2
Com base no grafo de fluxo anterior, correspondente a um trecho de código a ser testado, a quantidade mínima de testes que devem ser realizados para garantir que cada caminho do código tenha sido percorrido em ao menos um teste é:
		
	
	5 (cinco)
	
	6 (seis)
	
	11 (onze)
	
	3 (três)
	 
	4 (quatro)
	
	
	 
		
	ENSINEME: ANÁLISE DE ALGORITMO
	 
	 
	 7.
	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 anan 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:  
		
	
	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. 
	
	as duas asserções são proposições verdadeiras e a segunda não é a justificativa correta da primeira. 
	
	a primeira asserção é uma proposição verdadeira e a segunda uma proposição falsa. 
	
	
	 8.
	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:
		
	
	Registros alocadas em sequência na memória. 
	
	Diferentes tipos de dados distribuídos pela memória. 
	
	Diferentes tipos de dados em sequência na memória. 
	 
	Tipo de dado homogêneo em sequência na memória. 
	
	Tipo de dado homogêneo distribuído pela memória. 
	
	
	 
		
	ENSINEME: RECURSIVIDADE
	 
	 
	 9.
	Ref.: 3992614
	Pontos: 1,00  / 1,00
	
	Considere a função recursiva `func¿ definida por
func(1) = 1
func(n) = (n - 1) * func(n - 1)
Quais são os valores de func(4) e func(5), respectivamente?
		
	
	2 e 6
	
	1 e 2
	
	12 e 24
	 
	6 e 24
	
	24 e 120
	
	
	 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:
		
	
	120
	 
	720
	
	360
	
	1440
	
	240