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

Prévia do material em texto

AGRADEÇO SEU ACESSO! CLICA NO JOINHA LA EM CIMA E CONTINUE NOS 
INCENTIVANDO 
 
• Pergunta 1 
1 em 1 pontos 
 
O reequilíbrio eficiente é a chave para fazer a Árvore AVL funcionar bem sem 
sacrificar o desempenho. Para recuperar o equilíbrio de uma árvore AVL, 
realizaremos uma ou mais rotações na árvore. 
 
Entre as configurações a seguir, quais são os tipo de rotações usado para 
manter equilíbrio da árvore? 
 
I.Rotação à Direita 
II.Rotação à esquerda 
III.Rotação tripla à direita 
IV.Rotação dupla à esquerda 
V.Rotação dupla à direita 
 
Agora, assinale a alternativa que apresenta os tipos de rotações usado para realizar 
o equilíbrio de uma árvore. 
 
Resposta Selecionada: 
I, II, IV e V. 
Resposta Correta: 
I, II, IV e V. 
Comentário da 
resposta: 
Resposta correta. Os tipo de rotações usado para 
manter equilíbrio de uma árvore binária AVL são: Rotação à 
Direita, Rotação à esquerda, Rotação dupla à esquerda e 
Rotação dupla à direita. 
 
 
• Pergunta 2 
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. 
Comentário 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 3 
1 em 1 pontos 
 
O hashing 
aberto tem a desvantagem de exigir ponteiros. Isso tende a desacelerar um pouco o 
algoritmo por causa do tempo necessário para alocar novas células e também 
requer essencialmente a implementação de uma segunda estrutura de dados. 
 
Assinale a alternativa com o valor da posição para a chave 21 
descrita na tabela abaixo, use a técnica de hashing aberto . 
Chave 
3 
75 
16 
24 
21 
 
 
Resto 
 
0 
1 
4 
? 
 
 
Adote: h(x) = x mod m onde o 
m = 5 
0 
1 
2 
3 
4 
5 
6 
 
75 
16 
 
 
24 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Resposta Selecionada: 
. 0. 
Resposta Correta: 
. 0. 
Comentário 
da resposta: 
Resposta correta. Adotando h(x) = x mod m, onde o m = 
5, temos h(21) = 21 mod 5 = 1. Trabalhando com a técnica de 
hashing aberto é possível a inserção da chave na posição da 
função hashing, ou seja, o 21 será alocado na posição 1 na 
segunda estrutura de dados. 
 
 
• Pergunta 4 
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. 
 
De acordo com a Figura abaixo assinale a alternativa que contém o nó 
que encontra-se em desequilíbrio. 
 
Figura: Árvore binária AVL. Fonte: Autor. 
 
Resposta Selecionada: 
.B(-2). 
Resposta Correta: 
.B(-2). 
Comentário 
da resposta: 
Resposta correta. Uma árvore está desequilibrada quando este 
número for maior do que 1 ou menor que -1, ou seja em alguns 
casos não podemos fazer a árvore ter um equilíbrio completamente 
nulo. Qualquer número entre 1 e -1, será considerado o 
desequilíbrio, portanto o Nó 
no qual se inicia o desequilíbrio é o B(-2). 
 
 
• Pergunta 5 
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. 
 
Comentário 
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 6 
1 em 1 pontos 
 
De acordo com Viana a rotação dupla à esquerda consiste em como o próprio nome 
sugere, os primeiros ( nós) que estão na subárvore da direita passam para a 
esquerda fazendo com que o filho da direita se torne a nova raiz (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 a opção correta para realizar o equilíbrio na árvore da 
figura abaixo, usando a rotação dupla à esquerda. 
 
Figura: Árvore binária desequilibrada. Fonte: Autor. 
 
Resposta Selecionada: 
 
. . 
 
Resposta Correta: 
 
. . 
Comentário da 
resposta: 
Resposta correta. Para corrigir o problema de desequilíbrio 
proposto pela figura podemos adotar como solução, realizar uma 
rotação à direita na subárvore da direita logo em seguida realizar 
uma rotação à esquerda na árvore original. 
 
• Pergunta 7 
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. 
Comentário 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. 
 
 
• Pergunta 8 
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. 
Comentário 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 9 
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. 
Comentário 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 10 
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 conjuntoordenado, 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. 
Comentário 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. 
 
 
AGRADEÇO SEU ACESSO! CLICA NO JOINHA LA EM CIMA E CONTINUE NOS 
INCENTIVANDO