COMPLEXIDADE DE ALGORITMOS AV

Prévia do material em texto

ALGORITMOS DE ORDENAÇÃO AVANÇADOS
	 
	 
	 1.
	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: 
		
	
	As afirmativas I, II e III estão erradas. 
	
	A afirmativa I está errada, e as afirmativas II e III estão certas. 
	 
	As afirmativas I, II e III estão certas. 
	
	A afirmativa III está errada, e as afirmativas I e II estão certas. 
	
	A afirmativa II está errada, e as afirmativas I e III estão certas. 
	
	
	 2.
	Ref.: 4053480
	Pontos: 1,00  / 1,00
	
	Acerca dos algoritmos de ordenação, assinale a afirmativa correta: 
		
	
	O algoritmo insertion sort é mais eficiente do que o quick sort para grandes entradas de dados. 
	
	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. 
	
	A complexidade do algoritmo bubble sort é de ordem logarítmica. 
	
	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. 
		
	
	Não é necessário indexar os registros. 
	
	As operações de inserir, retirar e pesquisar são definidas. 
	
	Utilização de estruturas de dados como lista, pilha e fila. 
	
	Utilização de algoritmos de ordenação eficientes.  
	 
	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.  
	
	
	 4.
	Ref.: 3990639
	Pontos: 0,00  / 1,00
	
	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: 
		
	
	as duas afirmações são verdadeiras, e a segunda não justifica a primeira.  
	
	as duas afirmações são verdadeiras, e a segunda justifica a primeira.  
	
	as duas afirmações são falsas. 
	 
	a primeira afirmação é falsa, e a segunda é verdadeira.  
	 
	a primeira afirmação é verdadeira, e a segunda é falsa.  
	
	
	 
		
	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:
		
	
	Colunar
	
	Chave-valor
	
	Documento
	
	Tabular
	 
	Grafo
	
	
	 6.
	Ref.: 3992629
	Pontos: 1,00  / 1,00
	
	(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.
	 
	{1} {3,2} {4,5} {6}, caminho mais curto 1-3-4-6.
	
	{6} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual a 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.
	
	
	 
		
	ENSINEME: ANÁLISE DE ALGORITMO
	 
	 
	 7.
	Ref.: 3990624
	Pontos: 0,00  / 1,00
	
	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. 
		
	
	F, F, V 
	 
	V, F, V 
	
	V, F, F 
	
	F, V, F 
	 
	V, V, V 
	
	
	 8.
	Ref.: 3990625
	Pontos: 1,00  / 1,00
	
	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, IV. 
	
	II, III, V. 
	
	I, III, IV, V. 
	 
	II, III, IV, V. 
	
	
	 
		
	ENSINEME: RECURSIVIDADE
	 
	 
	 9.
	Ref.: 3992612
	Pontos: 1,00  / 1,00
	
	Ano: 2010 Banca: FCC Órgão: TRT - 20ª REGIÃO (SE) Prova: FCC - 2010 - TRT - 20ª REGIÃO (SE) - Técnico Judiciário - Tecnologia da Informação
Objeto que se constitui parcialmente ou é definido em termos de si próprio. Nesse contexto, um tipo especial de procedimento (algoritmo) será utilizado, algumas vezes, para a solução de alguns problemas. Esse procedimento é denominado:
		
	
	Rotatividade
	 
	Recursividade
	
	Repetição
	
	Interligação
	
	Condicionalidade
	
	
	 10.
	Ref.: 3992614
	Pontos: 1,00  / 1,00
	
	Considere a função recursiva `func¿ definida por
func(1) = 1
func(n) = (n - 1) * func(n - 1)
Quais são os valores de func(4) e func(5), respectivamente?
		
	
	2 e 6
	
	1 e 2
	 
	6 e 24
	
	12 e 24
	
	24 e 120