ATIVADADE 4

Prévia do material em texto

01/04/2021 GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO GR2409211 - 202110.ead-8051.11
https://fadergsead.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_PLAYER&COURSE_ID=_670726_1&… 1/6
Curso GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO
GR2409211 - 202110.ead-8051.11
Teste ATIVIDADE 4 (A4)
Iniciado 01/04/21 11:59
Enviado 01/04/21 16:40
Status Completada
Resultado da
tentativa
10 em 10 pontos 
Tempo
decorrido
4 horas, 41 minutos
Resultados
exibidos
Respostas enviadas, Respostas corretas, Comentários
Pergunta 1
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
I, II, IV e V.
I, II, IV e V.
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
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 Resto Adote: h(x) = x mod 0 75 
1 em 1 pontos
1 em 1 pontos
01/04/2021 GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO GR2409211 - 202110.ead-8051.11
https://fadergsead.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_PLAYER&COURSE_ID=_670726_1&… 2/6
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
3
75
16
24
21
 
 
0
1
4
?
 
m onde o m = 5 1
2
3
4
5
6
16
 
 
24
 
 
 
 
 
 
 
 
 
. 0.
. 0.
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 3
Resposta Selecionada:
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.
1 em 1 pontos
01/04/2021 GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO GR2409211 - 202110.ead-8051.11
https://fadergsead.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_PLAYER&COURSE_ID=_670726_1&… 3/6
 
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 4
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
As vantagens da tabela de dispersão é que ela pode ser usada como índice, porém
a grande vantagem está em se ter uma operação cujo acesso é direto, ou seja não
é preciso fazer um percurso em uma árvore, não é preciso comparar registro, pois
é uma operação onde vai direto para aquele registro. 
 
O hashing tem dois ingredientes fundamentais, assinale a alternativa com os
respectivos.
.Função de hashing e resolução de colisões.
.Função de hashing e resolução de colisões.
Resposta correta. O hashing é uma técnica que usa uma função para transformar uma
chave em um endereço. Já a colisão acontece quando a função hashing produz o
mesmo endereçamento para chaves diferentes.
Pergunta 5
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. 
1 em 1 pontos
1 em 1 pontos
01/04/2021 GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO GR2409211 - 202110.ead-8051.11
https://fadergsead.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_PLAYER&COURSE_ID=_670726_1&… 4/6
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
I, II e III.
I, II e III.
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
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
. AVL.
. AVL.
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 7
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
0
1
2
3
4
1 em 1 pontos
1 em 1 pontos
01/04/2021 GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO GR2409211 - 202110.ead-8051.11
https://fadergsead.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_PLAYER&COURSE_ID=_670726_1&… 5/6
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
 
 
 
 
75
16
5
6
 
. 0.
. 0.
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 8
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
Uma pesquisa sequencial é quando você olha para cada parte dos dados, um por
um, e não para até encontrar o que está procurando. Você pode usar uma pesquisa
sequencial em qualquer dado. No entanto, a pesquisa sequencial é a única opção
que você pode usar quando é preciso pesquisardados desordenados.
 
Entre as configurações a seguir, quais são as diferenças entre os métodos de
busca sequencial e busca binária?
 
I.Os dados de entrada precisam ser classificados na Pesquisa binária e não na
Pesquisa linear.
II.A pesquisa linear faz o acesso sequencial, enquanto a pesquisa binária acessa
dados aleatoriamente. 
III. A pesquisa binária realiza o acesso de forma sequencial.
IV.A pesquisa linear não realiza o acesso sequencial.
V.A pesquisa linear realiza comparações de igualdade e a pesquisa binária realiza
comparações de pedidos.
 
Agora, assinale a alternativa que apresenta as diferenças existentes entre as duas
buscas, ou seja, tanto a sequencial como a binária.
I, II e V.
I, II e V.
Resposta correta. As diferenças importantes entre a busca sequencial e busca binária
é que os dados de entrada precisam ser classificados na Pesquisa binária e não na
Pesquisa linear, assim como para a pesquisa linear é realizado o acesso sequencial,
enquanto a pesquisa binária acessa dados de forma aleatória. 
A Complexidade temporal da pesquisa linear é -O(n) e para pesquisa binária possui
complexidade temporal de O(log n). 
A pesquisa linear realiza comparações de igualdade e a pesquisa binária realiza
comparações de pedidos.
Pergunta 9
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,
1 em 1 pontos
1 em 1 pontos
01/04/2021 GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO GR2409211 - 202110.ead-8051.11
https://fadergsead.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_PLAYER&COURSE_ID=_670726_1&… 6/6
Resposta Selecionada: 
Resposta Correta: 
Comentário da resposta:
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.
.4.
.4.
Resposta correta. meio = (posiçaoInicial + posicaoFinal) / 2 
meio = (0 + 9) / 2 
meio = 4.5 (Pegar inteiro 4) vetor formado por números inteiros.
Pergunta 10
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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
.Início = 0 e fim = 9.
.Início = 0 e fim = 9.
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.
1 em 1 pontos