02 - COMPLEXIDADE DE ALGORITMOS - Prova 02

Prévia do material em texto

Disciplina: COMPLEXIDADE DE ALGORITMOS 
	AVS
	Aluno: 
	202009111891
	
	Turma: 9002
	EEX0030_AVS_202009111891 (AG) 
	 04/12/2021 20:33:03 (F) 
			Avaliação:
10,0
	Nota Partic.:
	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 é: 
		
	
	Shell sort 
	
	Insert sort 
	
	Selection sort 
	
	Bubble sort 
	 
	Quick sort 
	
	
	 2.
	Ref.: 4053481
	Pontos: 1,00  / 1,00
	
	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, II, III, IV, V 
	
	I, III, II, IV, V 
	
	V, IV, II, III, I 
	
	I, IV, V, III, II 
	 
	V, II, III, IV, I 
	
	
	 
		
	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: 
		
	
	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 
	
	A - B - D - E - H - I - J - K - C - F - G 
	 
	D - B - H - E - J - I - K - A - F - C - G 
	
	
	 4.
	Ref.: 3990635
	Pontos: 1,00  / 1,00
	
	Á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. 
		
	
	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. 
	
	Utilização de algoritmos de ordenação eficientes.  
	
	
	 
		
	ENSINEME: ALGORITMOS EM GRAFOS
	 
	 
	 5.
	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)
	
	
	 6.
	Ref.: 3992630
	Pontos: 1,00  / 1,00
	
	(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:
		
	
	Colunar
	
	Chave-valor
	 
	Grafo
	
	Documento
	
	Tabular
	
	
	 
		
	ENSINEME: ANÁLISE DE ALGORITMO
	 
	 
	 7.
	Ref.: 3990621
	Pontos: 1,00  / 1,00
	
	No algoritmo abaixo, os parâmetros da função valor são recebidos e são impressos na própria função. Assim sendo, o valor da variável u exibido na última linha da função é: 
Algoritmo questao_prova; 
var 
x,y: inteiro; 
inicio 
x<- 4; 
y<- 2; 
valor(x,y); 
fim. 
 
sub-rotina valor(inteiro: u, v) 
inicio 
u <- u * 2; 
v <- v + u; 
u <- u - 1; 
escreva(u); 
fim sub-rotina; 
 
Marque a opção que mostra o valor correto exibido da variável u. 
		
	
	8
	
	4
	
	10
	
	5
	 
	7
	
	
	 8.
	Ref.: 3990628
	Pontos: 1,00  / 1,00
	
	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 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 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:  
		
	
	tanto a primeira quanto a segunda asserções são proposições falsas. 
	
	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. 
	
	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. 
	
	
	 
		
	ENSINEME: RECURSIVIDADE
	 
	 
	 9.
	Ref.: 3992587
	Pontos: 1,00  / 1,00
	
	Ano: 2017 Banca: CONSULPLAN Órgão: TRE-RJ Prova: CONSULPLAN - 2017 - TRE-RJ - Técnico Judiciário - Programação de Sistemas
Analise as afirmativas a seguir a respeito de algoritmos recursivos.
I. Diz-se que uma rotina é recursiva se a sua definição envolver uma chamada a ela mesma. Neste sentido, o termo recursão é equivalente ao termo indução utilizado por matemáticos.
II. Cada algoritmo recursivo possui um algoritmo iterativo equivalente e vice-versa, mas que pode ter mais ou menos complexidade em sua construção.
III. Uma função recursiva possui duas partes: caso base e caso recursivo.
IV. Um algoritmo pode ser chamado de iterativo quando ele requer a repetição implícita de um processo até que determinada condição seja satisfeita.
V. A recursividade possibilita a escrita de um código mais enxuto, com maior legibilidade e simplicidade.
Assinale a alternativa que possui alguma afirmação INCORRETA.
		
	
	I e IV
	 
	III e IV
	
	I e II
	
	I e V
	
	II e III10.
	Ref.: 3992618
	Pontos: 1,00  / 1,00
	
	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 série de Fibonacci
	
	Iterativa da exponenciação
	 
	Recursiva do fatorial
	
	Recursiva da exponenciação
	
	Iterativa da série de Fibonacci