A4 PESQUISA ORDENACAO ARMAZENAMENTO FMU

Prévia do material em texto

• Pergunta 4 
0,25 em 0,25 pontos 
 
O hashing fechado, também conhecido como endereçamento aberto, é uma 
alternativa para resolver colisões com listas vinculadas. Em um sistema de hashing 
fechado, se ocorrer uma colisão, células alternativas são tentadas até que uma 
célula vazia seja encontrada. 
 
Assinale a alternativa com o valor da posição para a chave 3 descrita na tabela 
abaixo, use a técnica de hashing fechado . 
 
Chave 
3 
75 
16 
24 
 
 
 
Resto 
? 
5 
6 
4 
 
 
 
Adote: h(x) = x mod m onde 
o m = 10 
 
 
 
2 
24 
75 
16 
 
0 
1 
2 
3 
4 
5 
6 
 
 
 
 
Resposta Selecionada: 
. 0. 
Resposta Correta: 
. 0. 
Comentário da 
resposta: 
Resposta correta. Adotando h(x) = x mod m, onde o m = 
10, temos h(3) = 3 mod 10 = 3. Como a posição 3 encontra-se 
ocupada, procura-se a próxima posição disponível para que o 3 
seja alocando, portanto a próxima posição livre é a posição 0. 
 
 
• Pergunta 4 
0,25 em 0,25 pontos 
 
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. 
 
Assinale a alternativa com a fórmula para calcular o fator de equilíbrio de uma 
árvore AVL. 
 
Resposta Selecionada: 
.( Q = R - L), onde R = número de níveis a direita e L 
= número de níveis a esquerda. 
 
Resposta Correta: 
.(Q = R - L), onde R = número de níveis a direita e L 
= número de níveis a esquerda. 
Comentário da 
resposta: 
Resposta correta. Para calcular o fator de equilíbrio adotamos a 
equação ( Q = R - L), onde R = número de níveis a direita e L = 
número de níveis a esquerda. 
 
• Pergunta 4 
0,25 em 0,25 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 4 
0,25 em 0,25 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. 
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. 
 
• Pergunta 4 
0,25 em 0,25 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.