COMPLEXIDADE DE ALGORITMOS

Prévia do material em texto

Disciplina: COMPLEXIDADE DE ALGORITMOS 
	AV
	Aluno: RUAN 
	
	Professor: JHONATAN ALVES
 
	Turma: 9002
	EEX0030_AV_202007270291 (AG) 
	 21/11/2021 14:18:24 (F) 
			Avaliação:
8,0
	Nota Partic.:
	Av. Parcial.:
2,0
	Nota SIA:
10,0 pts
	 
		
	ENSINEME: ALGORITMOS DE ORDENAÇÃO AVANÇADOS
	 
	 
	 1.
	Ref.: 4053481
	Pontos: 0,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, III, II, IV, V 
	
	V, IV, II, III, I 
	 
	V, II, III, IV, I 
	
	I, IV, V, III, II 
	
	I, II, III, IV, V 
	
	
	 2.
	Ref.: 4053479
	Pontos: 1,00  / 1,00
	
	Analise as seguintes afirmativas sobre os métodos de ordenação: 
 
I. Quick sort divide um conjunto de itens em conjuntos menores, que são ordenados de forma independente, e, depois, os resultados são combinados para produzir a solução de ordenação do conjunto maior. 
 
II. Seleção é um método que consiste em selecionar o menor item de um vetor e substituí-lo pelo item que estiver na primeira posição. Essas duas operações são repetidas com os itens restantes até o último elemento. 
 
III. Shell sort é uma extensão do algoritmo de ordenação por inserção, contornando o problema que ocorre quando o menor item de um vetor está na posição mais à direita. 
 
Assinale a alternativa correta: 
		
	
	A afirmativa II está errada, e as afirmativas I e III estão certas. 
	
	As afirmativas I, II e III estão erradas. 
	
	A afirmativa I está errada, e as afirmativas II e III estão certas. 
	
	A afirmativa III está errada, e as afirmativas I e II estão certas. 
	 
	As afirmativas I, II e III estão certas. 
	
	
	 
		
	ENSINEME: ALGORITMOS EM ÁRVORES BINÁRIA E ÁRVORE AVL
	 
	 
	 3.
	Ref.: 3990636
	Pontos: 1,00  / 1,00
	
	
Considerando a figura acima, que ilustra uma árvore de busca binária, assinale a opção correta. 
		
	
	O percurso a percorrer nessa árvore na pré-ordem é 4 10 15 12 8.  
	 
	Se a árvore em tela for balanceada, depois da inserção de um nó 9, o nó 12 assume a raiz da árvore.  
	
	Transformando essa árvore em uma nova árvore de ordem 2, as folhas teriam de estar no nível 2. 
	
	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 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.  
	
	
	 4.
	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 
	
	J - K - I - H - E - D - B - F - G - C - A 
	 
	D - B - H - E - J - I - K - A - F - C - G 
	
	D - H - J - K - I - E - B - F - G - C - A 
	
	A - B - D - E - H - I - J - K - C - F - G 
	
	
	 
		
	ENSINEME: ALGORITMOS EM GRAFOS
	 
	 
	 5.
	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:
		
	
	Chave-valor
	
	Documento
	 
	Grafo
	
	Tabular
	
	Colunar
	
	
	 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 é:
		
	
	11 (onze)
	 
	4 (quatro)
	
	5 (cinco)
	
	6 (seis)
	
	3 (três)
	
	
	 
		
	ENSINEME: ANÁLISE DE ALGORITMO
	 
	 
	 7.
	Ref.: 3990622
	Pontos: 0,00  / 1,00
	
	Marque a alternativa correta. Vetor é uma coleção de variáveis de: 
		
	 
	tipo de dado homogêneo em sequência na memória. 
	
	diferentes tipos de dados em sequência na memória. 
	 
	tipo de dado homogêneo distribuído pela memória. 
	
	registros alocadas em sequência na memória. 
	
	diferentes tipos de dados distribuídos pela memória. 
	
	
	 8.
	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. 
		
	
	5
	
	8
	
	4
	 
	7
	
	10
	
	
	 
		
	ENSINEME: RECURSIVIDADE
	 
	 
	 9.
	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 exponenciação
	
	Iterativa da série de Fibonacci
	
	Iterativa da exponenciação
	
	Recursiva da série de Fibonacci
	 
	Recursiva do fatorial
	
	
	 10.
	Ref.: 3992581
	Pontos: 1,00  / 1,00
	
	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
		
	 
	Recursividade indireta
	
	Recursividade simples
	
	Lista linear simples
	
	Recursividade direta
	
	Lista circular