AV 1_ ALGORITMOS E COMPLEXIDADE

Prévia do material em texto

Disc.: DGT1348 - ALGORITMOS E COMPLEXIDADE
	
	
	
	
	
	
	 1a Questão (Ref.: 202206527372)
	Classifique cada uma das seguintes afirmações em "V" (se verdadeira) ou "F" (se falsa) e escolha a alternativa que corresponde à sequência correta de indicações. 
I- Um registro reúne uma coleção de informações, facilitando a sua organização e o seu uso. 
II- Cada informação distinta de um registro é considerada um atributo ou campo. 
III- O atributo pode ser definido como qualquer tipo de dado que a linguagem utiliza ou como outra estrutura de dados: vetor, matriz ou mesmo outro registro. 
		
	
	V, V, V 
	
	V, F, V 
	
	F, V, F 
	
	V, F, F 
	
	F, F, V 
	
	
	 2a Questão (Ref.: 202208649255)
	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:
		
	
	Tipo de dado homogêneo distribuído pela memória. 
	
	Tipo de dado homogêneo em sequência na memória. 
	
	Diferentes tipos de dados em sequência na memória. 
	
	Registros alocadas em sequência na memória. 
	
	Diferentes tipos de dados distribuídos pela memória. 
	
	
	 3a Questão (Ref.: 202206529364)
	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
	
	1440
	
	240
	
	120
	
	
	 4a Questão (Ref.: 202206529335)
	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.
		
	
	II e III
	
	III e IV
	
	I e V
	
	I e IV
	
	I e II
	
	
	 5a Questão (Ref.: 202206590229)
	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, III, II, IV, V 
	
	I, IV, V, III, II 
	
	I, II, III, IV, V 
	
	V, IV, II, III, I 
	
	
	 6a Questão (Ref.: 202206596075)
	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): 
		
	
	Quick sort e insertion sort. 
	
	Merge sort e bubble sort. 
	
	Quick sort e merge sort. 
	
	Bubble sort. 
	
	Insertion sort. 
	
	
	 7a Questão (Ref.: 202206527387)
	Após a inserção de um nó, é necessário verificar cada um dos nós ancestrais desse nó inserido, relativamente à consistência com as regras estruturais de uma árvore AVL. 
                                                  PORQUE 
O fator de balanceamento de cada nó, em uma árvore AVL, deve pertencer ao conjunto formado por {−2, −1, 0, +1, +2}. 
 
Analisando-se as afirmações acima, conclui-se que: 
		
	
	a primeira afirmação é verdadeira, e a segunda é falsa.  
	
	as duas afirmações são verdadeiras, e a segunda justifica a primeira.  
	
	as duas afirmações são verdadeiras, e a segunda não justifica a primeira.  
	
	as duas afirmações são falsas. 
	
	a primeira afirmação é falsa, e a segunda é verdadeira.  
	
	
	 8a Questão (Ref.: 202206527383)
	Á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 algoritmos de ordenação eficientes.  
	
	Utilização de estruturas de dados como lista, pilha e fila. 
	
	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. 
	
	Não é necessário indexar os registros. 
	
	
	 9a Questão (Ref.: 202206529376)
	(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?
		
	
	9
	
	15
	
	17
	
	19
	
	11
	
	
	 10a Questão (Ref.: 202206529377)
	(FCC - ARTESP - Agente de Fiscalização à Regulação de Transporte - Tecnologia de Informação - 2017)
Considere a estrutura abaixo que representa um problema de rotas em pequena escala:
Considere, por hipótese, que se solicitou a um Agente de Fiscalização à Regulação de Transporte da ARTESP utilizar alguma estratégia lógica para, partindo do ponto 1, chegar ao ponto 6 usando a menor rota. De um mesmo ponto pode haver mais de uma rota, com distâncias diferentes. A lógica correta utilizada pelo Agente, em função dos pontos a serem percorridos, foi:
		
	
	{1} {2,3} {2,4} {5,6} {6}, caminho mais curto 1-2-5-6.
	
	{1} {2} {4} {6}, caminho mais curto 1-2-4-6.
	
	{6} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual a 1-3-4-6.
	
	{1} {3,2} {4,5} {6}, caminho mais curto 1-3-4-6.
	
	{6} {4} {5,3} {2,1} {1}, caminho mais curto 6-4-3-5-2-1, que é igual a 1-2-5-3-4-6.