[A1] Avaliação do Módulo 1 - Hash e Heap_ Revisão da tentativa

Prévia do material em texto

Painel Meus cursos 32010001871-T01-2024-1 📚 Módulo 1
✅ [A1] Avaliação do Módulo 1 - Hash e Heap
Iniciado em domingo, 2 jun 2024, 16:11
Estado Finalizada
Concluída em domingo, 2 jun 2024, 16:33
Tempo
empregado
22 minutos 22 segundos
Avaliar 9,33 de um máximo de 10,00(93,33%)
Comentários
02/06/2024, 16:34 ✅ [A1] Avaliação do Módulo 1 - Hash e Heap: Revisão da tentativa
https://ava.ufms.br/mod/quiz/review.php?attempt=976658&cmid=738681 1/6
https://ava.ufms.br/my/
https://ava.ufms.br/course/view.php?id=53721
https://ava.ufms.br/course/view.php?id=53721#section-2
https://ava.ufms.br/mod/quiz/view.php?id=738681
Questão 1
Correto
Atingiu 1,00 de 1,00
Questão 2
Correto
Atingiu 1,00 de 1,00
Questão 3
Correto
Atingiu 1,00 de 1,00
O hash duplo oferece um dos melhores métodos disponíveis para endereçamento aberto porque as
permutações produzidas têm muitas das características de permutações escolhidas aleatoriamente. Para um
dado d qualquer e uma tabela hash de tamanho M, o hash duplo usa uma função hash da forma: 
h(d) = (h (d) + passo * h (d)) % M
Considerando uma tabela hash T de tamanho M=11, h (d)=d mod M, h (d)=(1+ d mod 7) ,
simule a inserção, nesta ordem, das chaves: 54, 72, 32, 70, 47. Relacione abaixo cada chave com sua posição na
tabela.
h(72) 
h(47) 
h(70) 
h(54)  
h(32) 
1 2
1 2
6
3
5
10
4
Considerando a lista de max-prioridades formada, nesta ordem, pelos elementos 83,72,64,67,53,59,62,58,46,52,
determinar a lista resultante da alteração de prioridade do 9o. elemento de prioridade 46 para 84:
84  83  64  72  53  59  62  58  67  52 
 
Considere uma tabela Hash T com tamanho M = 7 e função de mapeamento pelo método da divisão. Qual o
número de colisões na tabela, se os seguintes valores forem inseridos nesta ordem: 70, 7, 12, 9, 23, 14?
Resposta: 3 
02/06/2024, 16:34 ✅ [A1] Avaliação do Módulo 1 - Hash e Heap: Revisão da tentativa
https://ava.ufms.br/mod/quiz/review.php?attempt=976658&cmid=738681 2/6
Questão 4
Correto
Atingiu 1,00 de 1,00
Questão 5
Parcialmente correto
Atingiu 0,33 de 1,00
Questão 6
Correto
Atingiu 1,00 de 1,00
Considerando a lista de min-prioridades formada pelos elementos  12,21,28,23,36,32,41,47,51,49, determinar qual
alternativa descreve a lista resultante da inclusão do elemento 18:
Escolha uma opção:
a. 12,18,28,21,23,32,41,47,51,49,36
b. 12,18,28,23,21,41,32,51,37,49,36
c. 08,12,28,23,21,32,41,47,51,49,36
d. 12,18,28,23,21,32,41,47,51,49,36
O tratamento de colisões por encadeamento utiliza listas encadeadas para armazenar chaves sinônimas. Tais
listas utilizam ponteiros, o que consome espaço. Para economizá-lo, desenvolveu-se o método denominado
endereçamento aberto. A ideia é armazenar as chaves sinônimas também na tabela. Porém, não há uso de
ponteiros. As chaves são armazenadas na tabela, sem qualquer informação adicional. Quando ocorre alguma
colisão, determina-se, também por cálculo, qual o próximo compartimento a ser examinado. Se ocorrer nova
colisão com alguma outra chave armazenada nesse último, um novo compartimento é escolhido mediante
cálculo, e assim por diante. Selecione abaixo os métodos que podem ser utilizados nas operações de busca,
inserção e remoção do endereçamento aberto:
Obs.: Cada alternativa errada que for marcada anula a pontuação que seria recebida por uma alternativa
correta.
Escolha uma ou mais:
a. tentativa quadrática
b. tentativa binária
c. tentativa linear
d. hash duplo
Considerando a sequência crescente 1,2,3,4,5,6,7 como dados de uma lista de prioridades tipo “min-heap” e
A,B,C,D,E,F,G como rótulos dos nós, escolha a alternativa correta abaixo:
Escolha uma opção:
a. E>B e A>B
b. A<B e B>D
c. E<A>D e B>A<E
d. G>C>A e D>B>A
e. Todas alternativas erradas.
02/06/2024, 16:34 ✅ [A1] Avaliação do Módulo 1 - Hash e Heap: Revisão da tentativa
https://ava.ufms.br/mod/quiz/review.php?attempt=976658&cmid=738681 3/6
Questão 7
Correto
Atingiu 1,00 de 1,00
Questão 8
Correto
Atingiu 1,00 de 1,00
Sobre o tratamento de colisões em endereçamento aberto, é correto afirmar que:
Obs.: Cada alternativa errada que for marcada anula a pontuação que seria recebida por uma alternativa
correta.
Escolha uma ou mais:
a. Ao procurar um elemento, examinam-se sistematicamente as posições da tabela até encontrar o
elemento desejado ou até confirmar que o elemento não está na tabela.

b. Ao executar uma operação de inserção sobre a tabela, examina-se sucessivamente a tabela de
dispersão até encontrar uma posição vazia na qual inserir a chave ou detectar que está cheia.

c. Alguns elementos ficam na própria tabela de dispersão e outros fora. Isto é, cada entrada da tabela
contém um único elemento do conjunto ou uma lista de elementos.
d. De maneira similar ao tratamento de colisões por encadeamento, não existe nenhuma lista e nenhum
elemento armazenado fora da tabela.
e. Nessa forma de tratamento de colisões, a tabela de dispersão pode “ficar cheia”, de maneira que
nenhuma inserção adicional pode ser feita; o fator de carga α nunca pode exceder 1.

Uma função de dispersão h transforma uma chave x em um endereço-base h(x) da tabela de dispersão. Uma
função de dispersão ideal deve satisfazer às seguintes condições:
I) não produzir um número elevado de colisões;
II) o tempo consumido para calcular h(x) deve ser crítico;
III) a função h deve ser tal que todos os compartimentos possuam a mesma probabilidade de serem escolhidos.
É correto afirmar que:
Escolha uma opção:
a. I e II estão corretas
b. I e III estão corretas
c. II e III estão corretas
d. I, II e III estão corretas
02/06/2024, 16:34 ✅ [A1] Avaliação do Módulo 1 - Hash e Heap: Revisão da tentativa
https://ava.ufms.br/mod/quiz/review.php?attempt=976658&cmid=738681 4/6
Questão 9
Correto
Atingiu 1,00 de 1,00
Questão 10
Correto
Atingiu 1,00 de 1,00
No tratamento de colisões por encadeamento em uma tabela hash T, uma posição j qualquer da tabela possui
uma lista encadeada contendo todos os elementos que, após o hash, foram mapeados para a posição j; se não
houver nenhum desses elementos, a posição j possuirá uma  .
Nesse tipo de tratamento de colisão, o tempo de execução do pior caso para a 
em uma tabela hash com tratamento de colisões por encadeamento é  .  Para a
  , o tempo de execução do pior caso é proporcional ao
  .
lista vazia
operação de inserção
O(1)
operação de busca
comprimento da lista
Considere que uma lista de min-prioridades para caracteres está armazenada em um vetor, através de um
heap binário e que as posições desse vetor são indexadas começando no índice 1.
M,N,O,P,Q,R,S,T,U,V,W
Quais são, respectivamente, os caracteres armazenados no filho esquerdo, no filho direito e no pai do nó
correspondente ao índice 2?
Escolha uma opção:
a. R, O e N
b. M, N e P
c. M, W e P
d. P, Q e M 
e. N, P e R
Atividade anterior
◄ 📍 [Checkout de Presença] Módulo 1 - Hash e Heap
Seguir para...
Próxima atividade
▶ Videoaula Obrigatória - Módulo 2 - Unidade 1 - Conceitos, algoritmo de inserção e algoritmo de busca ►
02/06/2024, 16:34 ✅ [A1] Avaliação do Módulo 1 - Hash e Heap: Revisão da tentativa
https://ava.ufms.br/mod/quiz/review.php?attempt=976658&cmid=738681 5/6
https://ava.ufms.br/mod/quiz/view.php?id=738679&forceview=1
https://ava.ufms.br/mod/url/view.php?id=738683&forceview=1
Manter contato
Suporte Técnico ao Usuário
 https://suporteagetic.ufms.br
 (67) 3345-7613
 suporte.agead@ufms.br

02/06/2024, 16:34 ✅ [A1] Avaliação do Módulo 1 - Hash e Heap: Revisão da tentativa
https://ava.ufms.br/mod/quiz/review.php?attempt=976658&cmid=738681 6/6
https://suporteagetic.ufms.br/
tel:(67) 3345-7613
mailto:suporte.agead@ufms.br
https://api.whatsapp.com/send?phone=556733457613