COMPLEXIDADE DE ALGORITMOS

Prévia do material em texto

1.
	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, IV, V, III, II 
	
	V, IV, II, III, I 
	
	I, III, II, IV, V 
	
	I, II, III, IV, V 
	 
	V, II, III, IV, I 
	
	
	 2.
	Ref.: 4053480
	Pontos: 1,00  / 1,00
	
	Acerca dos algoritmos de ordenação, assinale a afirmativa correta: 
		
	
	A complexidade do algoritmo bubble sort é de ordem logarítmica. 
	
	O shell sort é um algoritmo de ordenação estável e instável. 
	 
	O algoritmo merge sort é implementado por meio de divisão e conquista. 
	
	O algoritmo insertion sort é mais eficiente do que o quick sort para grandes entradas de dados. 
	
	O algoritmo de ordenação heap sort utiliza uma árvore ternária de busca. 
	
	
	 
		
	ENSINEME: ALGORITMOS EM ÁRVORES BINÁRIA E ÁRVORE AVL
	 
	 
	 3.
	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. 
	
	As operações de inserir, retirar e pesquisar são definidas. 
	
	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.  
	
	Utilização de algoritmos de ordenação eficientes.  
	
	
	 4.
	Ref.: 3990634
	Pontos: 1,00  / 1,00
	
	Imagine que temos números de 1 a 100 em uma árvore de pesquisa binária (ABP). Agora queremos procurar o número 50. Assinale a alternativa que apresenta a possível sequência de elementos da árvore consultada. 
		
	
	40 - 10 - 45 - 30 - 50. 
	
	40 - 15 - 45 - 30 - 50. 
	
	42 - 60 - 20 - 30 - 50. 
	
	42 - 60 - 20 - 48 - 50. 
	 
	40 - 60 - 45 - 48 - 50. 
	
	
	 
		
	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:
		
	 
	Grafo
	
	Chave-valor
	
	Documento
	
	Colunar
	
	Tabular
	
	
	 6.
	Ref.: 3992632
	Pontos: 1,00  / 1,00
	
	(CESGRANRIO - Banco da Amazônia - Técnico Científico - Banco de Dados - 2014)
O grafo anterior pode ser representado pela seguinte matriz:
		
	 
	
	
	
	
	
	
	
	
	
	
	
	 
		
	ENSINEME: ANÁLISE DE ALGORITMO
	 
	 
	 7.
	Ref.: 3990626
	Pontos: 1,00  / 1,00
	
	Uma lista ordenada de N números é inserida em uma pilha e depois retirada, sendo que, a cada POP, o elemento retirado é inserido em um vetor de elementos. Após a completa inserção de todos os elementos neste vetor, são feitas buscas de números na mesma. O tempo médio de busca de um número neste elemento é: 
		
	 
	O(N)
	
	O(log N)
	
	O(N22)
	
	O(Nlog N)
	
	O(1)
	
	
	 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:
		
	
	Diferentes tipos de dados em sequência na memória. 
	
	Diferentes tipos de dados distribuídos pela memória. 
	 
	Tipo de dado homogêneo em sequência na memória. 
	
	Registros alocadas em sequência na memória. 
	
	Tipo de dado homogêneo distribuído pela memória. 
	
	
	 
		
	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 série de Fibonacci
	
	Iterativa da série de Fibonacci
	
	Iterativa da exponenciação
	
	Recursiva da exponenciação
	 
	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
		
	
	Lista linear simples
	
	Recursividade simples
	 
	Recursividade indireta
	
	Lista circular
	
	Recursividade direta