PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO - AV4

Prévia do material em texto

 Pergunta 1 
1 em 1 pontos
	
	
	
	Nas árvores de busca balanceada, as chaves alocadas são mantidas ordenadas, permitindo que a operação de busca seja realizada, percorrendo um ramo da árvore, desde da base até chegar ao início. Vários algoritmos foram desenvolvidos para a construção de árvores de busca que permanecem equilibradas (VIANA, Gerardo Valdisio Rodrigues; CINTRA, Glauber Ferreira; NOBRE; Ricardo Holanda. Pesquisa e ordenação de Dados. 2 edição. EdeuECE, 2015.).
 
Assinale a alternativa com dois tipos de árvores de busca. 
	
	
	
	
		Resposta Selecionada: 
	
.AVL e B+. 
	Resposta Correta: 
	
.AVL e B+. 
	Feedback da resposta: 
	Resposta correta. A árvore AVL é uma árvore binária que vai seguir as mesmas regras para inserção, busca e remoção de elementos. As árvores B e B+ são formas de árvore de pesquisa equilibrada baseada em árvores gerais. 
	
	
	
 Pergunta 2 
1 em 1 pontos
	
	
	
	Ambas árvore B e B+ são árvores de auto-equilíbrio que possuem operações logarítmicas de inserção, localização e exclusão. 
  
Entre as configurações a seguir, quais alternativas condizem com as propriedades da árvore B? 
  
I. Uma árvore B é definida pelo termo grau mínimo t. O valor de t depende do tamanho do bloco de disco. 
II.Todos os ( nós) 
(incluindo raiz) podem conter no máximo 2t - 1 chaves.   
III.Todo nó 
do tipo folha possui a mesma profundidade entre eles e o ( nó) da raiz. 
IV.Nenhuma das folhas estão no mesmo nível. 
V.Nenhum nó 
possui a mesma profundidade entre o ( nó) da raiz. 
            
Agora, assinale a alternativa que apresenta as propriedades da árvore B. 
	
	
	
	
		Resposta Selecionada: 
	
I, II e III. 
	Resposta Correta: 
	
I, II e III. 
	Feedback da resposta: 
	Resposta correta. As propriedades da árvore B é definida pelo termo grau mínimo t. O valor de t depende do tamanho do bloco de disco. Assim como,  todos os ( nós) (incluindo raiz) podem conter no máximo 2t - 1 chaves e Todo nó do tipo folha possui a mesma profundidade entre eles e o ( nó) da raiz. 
	
	
	
 Pergunta 3 
1 em 1 pontos
	
	
	
	A busca é bem comum na área da computação, onde podemos usar muitos método e estruturas de dados para está realizando essa busca, ela pode ser realizada pelo índice ou pelo valor. A busca realizada pelo índice é considerada uma busca direta , ou seja, vai direto na posição da memória.
 
Para realizar essa busca por valor temos duas maneiras, assinale a alternativa que condiz com essas maneiras. 
	
	
	
	
		Resposta Selecionada: 
	
.Busca sequencial e busca binária. 
	Resposta Correta: 
	
.Busca sequencial e busca binária. 
	Feedback da resposta: 
	Resposta correta. Para realizar essa busca por valor temos duas maneiras ou realizamos uma busca sequencial ou uma busca binária. 
A busca sequencial ela percorre todas as posições do vetor verificando uma a uma até achar o valor desejado ou simplesmente chegou ao final sem achá-lo, já na busca binária é dividido o vetor ao meio e a busca é realizada apenas em uma das metades. 
	
	
	
 Pergunta 4 
1 em 1 pontos
	
	
	
	A idéia essencial por trás de uma tabela de dispersão é que todas as informações são armazenadas em uma matriz de tamanho fixo. O hashing é usado para identificar a posição em que um item deve ser armazenado.
 
Assinale a alternativa com os tipos de hashing mais usados. 
	
	
	
	
		Resposta Selecionada: 
	
.Hashing aberto e hashing fechado. 
	Resposta Correta: 
	
.Hashing aberto e hashing fechado. 
	Feedback da resposta: 
	Resposta correta. Os tipos de hashing pode ser divididos em duas formas, sendo ela hashing fechado no qual é permitido o armazenar um conjunto de informações de tamanho limitado e o hashing aberto no qual é permitido armazenar um conjunto de informações de tamanho limitado. 
	
	
	
 Pergunta 5 
1 em 1 pontos
	
	
	
	Nas árvores de busca balanceada, as chaves alocadas são mantidas ordenadas, permitindo que a operação de busca seja realizada, percorrendo um ramo da árvore, desde a base até chegar ao início (VIANA, Gerardo Valdisio Rodrigues; CINTRA, Glauber Ferreira; NOBRE; Ricardo Holanda. Pesquisa e ordenação de Dados. 2 edição. EdeuECE, 2015.).
 
Assinale a alternativa que diz respeito a uma árvore de busca balanceada. 
	
	
	
	
		Resposta Selecionada: 
	
. AVL. 
	Resposta Correta: 
	
. AVL. 
	Feedback da resposta: 
	Resposta correta. A árvore AVL é uma árvore binária que vai seguir as mesmas regras para inserção, busca e remoção de elementos, e adicionar essas regras a métodos para se manter o equilíbrio da árvore. 
	
	
	
 Pergunta 6 
1 em 1 pontos
	
	
	
	Imagine esse vetor ordenado como a Figura abaixo, onde se pretende procurar o elemento 8, a primeira coisa que o vetor irá fazer é descobrir a posição inicial, depois descobrir a posição final.
 
Vamos considerar a seguinte matriz: 
	1 
	2 
	3 
	4 
	5 
	6 
	7 
	8 
	9 
	10 
Figura: Vetor Ordenado
Assinale a alternativa com a afirmativa corretas para o meio desse intervalo. 
	
	
	
	
		Resposta Selecionada: 
	
.4. 
	Resposta Correta: 
	
.4. 
	Feedback da resposta: 
	Resposta correta.     meio = (posiçaoInicial + posicaoFinal) / 2 
meio = (0 + 9) / 2 
meio = 4.5 (Pegar inteiro 4) vetor formado por números inteiros. 
	
	
	
 Pergunta 7 
1 em 1 pontos
	
	
	
	Em 1962, dois cientistas da computação, mudaram para sempre o cenário das  estruturas da Árvore de Pesquisa Binária quando criaram uma árvore revolucionária de auto-equilíbrio que alcança a pior complexidade temporal de O (log n ). 
  
Assinale a alternativa com os respectivos nomes desses cientistas. 
	
	
	
	
		Resposta Selecionada: 
	
.Georgy Adelson Velsky e Evgenii Landis. 
	Resposta Correta: 
	
.Georgy Adelson Velsky e Evgenii Landis. 
	Feedback da resposta: 
	Resposta correta. Em 1962, dois cientistas da computação soviéticos, Georgy Adelson Velsky e Evgenii Landis, mudaram para sempre o cenário das  estruturas da Árvore de Pesquisa Binária. 
	
	
	
 Pergunta 8 
1 em 1 pontos
	
	
	
	A pesquisa binária é o algoritmo de pesquisa mais popular, eficiente e também uma das técnicas mais usadas para solucionar problemas. A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista.
 
Assinale a alternativa correta para forma como os vetores devem estar para busca binária funcionar. 
	
	
	
	
		Resposta Selecionada: 
	
.Ordenados. 
	Resposta Correta: 
	
.Ordenados. 
	Feedback da resposta: 
	Resposta correta. A busca binária só funciona em vetores que estejam de forma ordenados, ela divide o vetor ao meio e procura apenas em uma das metades, ou seja, o algoritmo é executado até encontrar o valor ou posição. 
	
	
	
 Pergunta 9 
1 em 1 pontos
	
	
	
	A pesquisa binária funciona apenas em um conjunto com elementos ordenados. Para usar a pesquisa binária em uma coleção, a coleção deve primeiro ser classificada.
Quando a pesquisa binária é usada para executar operações em um conjunto ordenado, o número de iterações sempre pode ser reduzido com base no valor que está sendo pesquisado.
 
Antes de iniciar a pesquisa binária, primeiro definimos o início e fim do intervalo, assinale a alternativa com a afirmativa corretas para o início e o fim desse intervalo.
Vamos considerar a seguinte matriz: 
	1 
	2 
	3 
	4 
	5 
	6 
	7 
	8 
	9 
	10 
Figura: Vetor Ordenado 
	
	
	
	
		Resposta Selecionada: 
	
.Início  = 0 e fim = 9. 
	Resposta Correta: 
	
.Início  = 0 e fim = 9. 
	Feedback da resposta: 
	Resposta correta.  O início do intervalo é definido como Low = 0, e o fim do intervalo é definido como High = n-1, ou seja, High = 10-1 = 9. 
	
	
	
 Pergunta 10 
1 em 1 pontos
	
	
	
	O equilíbrio de uma árvore de busca é medido subtraindo o número de níveis na subárvore da esquerda do número de níveis na subárvore da direita. 
Uma vez detectado o desequilíbrio na árvore o próximo passo é entender como corrigir o desequilíbrio. 
  
Assinale a alternativa com a forma a qual podemos corrigir este desequilíbrio. 
	
	
	
	
		Resposta Selecionada:.Rotações. 
	Resposta Correta: 
	
.Rotações. 
	Feedback da resposta: 
	Resposta correta. Uma vez detectado o desequilíbrio na árvore o próximo passo é entender como corrigir o desequilíbrio. O equilíbrio da árvore é corrigido através das chamadas rotações.