AV Complexidade de Algorítimos

Prévia do material em texto

1a Questão (Ref.: 202008176369)
	Marque a alternativa correta. Vetor é uma coleção de variáveis de: 
		
	
	tipo de dado homogêneo em sequência na memória. 
	
	registros alocadas em sequência na memória. 
	
	diferentes tipos de dados distribuídos pela memória. 
	
	tipo de dado homogêneo distribuído pela memória. 
	
	diferentes tipos de dados em sequência na memória. 
	
	
	 2a Questão (Ref.: 202008176372)
	Leia as afirmativas a seguir considerando que f(n) e g(n) são funções positivas.  
I- Se g(n) é O(f(n)), um algoritmo de função de complexidade de tempo f(n) possui Ordem de complexidade g(n).  
II- Se g(n) é O(f(n)), f(n) é um limite superior para g(n).  
III- Se a função g(n) = 7.log(n) +6 , então a função g(n) é O(log(n)).  
IV- Se g(n) = n2 e f(n) = (n+1)2 temos que g(n) é O(f(n)) e f(n) é O(g(n)).  
V- Se g(n) = 2n+1 e f(n) = 2n temos que g(n) = O(f(n)).  
Assinale a alternativa que apresenta somente as afirmativas: 
		
	
	I, II, IV, V. 
	
	II, III, V. 
	
	II, III, IV, V. 
	
	I, III, IV, V. 
	
	II, III, IV. 
	
	
	 3a Questão (Ref.: 202008178334)
	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 V
	
	III e IV
	
	II e III
	
	I e II
	
	I e IV
	
	
	 4a Questão (Ref.: 202008178365)
	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 do fatorial
	
	Iterativa da série de Fibonacci
	
	Recursiva da série de Fibonacci
	
	Iterativa da exponenciação
	
	
	 5a Questão (Ref.: 202008245070)
	O algoritmo de ordenação mais eficiente para um conjunto grande de elementos randomicamente inseridos é: 
		
	
	Bubble sort 
	
	Insert sort 
	
	Quick sort 
	
	Selection sort 
	
	Shell sort 
	
	
	 6a Questão (Ref.: 202008239228)
	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, é: 
		
	
	V, II, III, IV, I 
	
	I, II, III, IV, V 
	
	I, IV, V, III, II 
	
	V, IV, II, III, I 
	
	I, III, II, IV, V 
	
	
	 7a Questão (Ref.: 202008176383)
	
Considerando a figura acima, que ilustra uma árvore de busca binária, assinale a opção correta. 
		
	
	Transformando essa árvore em uma nova árvore de ordem 2, as folhas teriam de estar no nível 2. 
	
	Se a árvore em tela for balanceada, depois da inserção de um nó 9, o nó 12 assume 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.  
	
	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.  
	
	O percurso a percorrer nessa árvore na pré-ordem é 4 10 15 12 8.  
	
	
	 8a Questão (Ref.: 202008176387)
	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 
	
	A - B - D - E - H - I - J - K - C - F - G 
	
	D - B - H - E - J - I - K - A - F - C - G 
	
	J - K - I - H - E - D - B - F - G - C - A 
	
	
	 9a Questão (Ref.: 202008178371)
	(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)
	
	5 (cinco)
	
	3 (três)
	
	6 (seis)
	
	4 (quatro)
	
	
	 10a Questão (Ref.: 202008178377)
	(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