A3 PESQUISA ORDENACAO ARMAZENAMENTO FMU

Prévia do material em texto

• Pergunta 3 
0,25 em 0,25 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 
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. 
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 3 
0,25 em 0,25 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. 
Comentário 
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 3 
0,25 em 0,25 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 3 
0,25 em 0,25 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. 
 
 
•