Prova PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO_Atv04 - Corrigida

Prévia do material em texto

08/02/2021 Blackboard Learn
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_PLAYER&COURSE_ID=_668368_1&PA… 1/5
Curso GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO
GR2409211 - 202110.ead-14727.01
Teste ATIVIDADE 4 (A4)
Iniciado 08/02/21 18:26
Enviado 08/02/21 20:01
Status Completada
Resultado da
tentativa
10 em 10 pontos 
Tempo
decorrido
1 hora, 34 minutos
Resultados
exibidos
Respostas enviadas, Respostas corretas, Comentários
Pergunta 1
Resposta Selecionada: 
Resposta Correta: 
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.
.B(-2).
.B(-2).
1 em 1 pontos
08/02/2021 Blackboard Learn
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_PLAYER&COURSE_ID=_668368_1&PA… 2/5
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 2
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
.Georgy Adelson Velsky e Evgenii Landis.
.Georgy Adelson Velsky e Evgenii Landis.
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 3
Resposta Selecionada:
 
Resposta Correta:
 
Comentário
da resposta:
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.
.( Q = R - L), onde R = número de níveis a direita e L 
= número de níveis a esquerda.
.(Q = R - L), onde R = número de níveis a direita e L
= número de níveis a esquerda.
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
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. 
1 em 1 pontos
1 em 1 pontos
1 em 1 pontos
08/02/2021 Blackboard Learn
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_PLAYER&COURSE_ID=_668368_1&PA… 3/5
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
 
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 5
Resposta Selecionada: 
Resposta Correta: 
Comentário da
resposta:
Formalmente, definimos uma Árvore B + pelos valores M e L, onde M é igual ao
número máximo de filhos que um determinado nó pode ter e L é igual ao número
máximo de registros de dados armazenados em um nó folha.
 
Uma árvore B + da ordem M é uma árvore que satisfaz uma das propriedade
abaixo, assinale qual.
.Cada nó tem no máximo M filhos.
.Cada nó tem no máximo M filhos.
Resposta correta. Uma árvore B+ da ordem M é uma árvore que cada nó tem
no máximo M filhos.
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 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.
.AVL e B+.
.AVL e B+.
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 7
As tabelas de hashing podem ser usadas para implementar a inserção e encontrar
operações em tempo médio constante. É especialmente importante prestar atenção
a detalhes como fator de carga ao usar tabelas de hashing, pois caso contrário os
limites de tempo não são válidos. Também é importante escolher a função hashing
1 em 1 pontos
1 em 1 pontos
1 em 1 pontos
08/02/2021 Blackboard Learn
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_PLAYER&COURSE_ID=_668368_1&PA… 4/5
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
com cuidado quando a chave não for uma sequência curta ou um número inteiro.
 
Entre as configurações a seguir, quais funções de hashing são consideradas
satisfatória?
 
I. Rápido de calcular o O(1) 
II.Tem menos colisões 
III.Tem mais colisões 
IV. Distribui as chaves de forma não uniforme na tabela
V.Espalha as chaves uniforme na tabela hashing 
 
Agora, assinale a alternativa que apresenta os conceitos de uma boa funções
hashing.
I, II e V.
I, II e V.
Resposta correta. Uma função hashing é considerada satisfatória quando é rápida de
calcular o O(1) e apresenta poucas colisões, assim como as chaves são espalhadas
de forma distribuída entre a tabela de dispersão.
Pergunta 8
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 9
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 pesquisar dados 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 oacesso sequencial, enquanto a pesquisa binária acessa
dados aleatoriamente. 
1 em 1 pontos
1 em 1 pontos
08/02/2021 Blackboard Learn
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_PLAYER&COURSE_ID=_668368_1&PA… 5/5
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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 10
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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
 
. 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.
1 em 1 pontos