[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 quarta, 5 jun 2024, 16:19
Estado Finalizada
Concluída em quarta, 5 jun 2024, 17:03
Tempo
empregado
44 minutos 1 segundo
Avaliar 6,40 de um máximo de 10,00(64%)
Comentários
Questão 1
Correto
Atingiu 1,00 de 1,00
Sobre o método da divisão para criar funções hash (h(k)), é 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. Uma chave k é mapeada para uma das m posições da tabela hash, na qual a função hash é h(k) = k / m
b. Um número primo não muito próximo de uma potência exata de 2 é uma boa escolha para m
(tamanho da tabela).

c. Não é possível utilizar chaves que são cadeias de caracteres neste método.
d. Ao utilizar o método de divisão, em geral, evita-se certos valores de m (tamanho da tabela). Por
exemplo, m não deve ser uma potência de 2, já que, se m = 2p, então, h(k) será somente o grupo de p
bits de ordem mais baixa de k.

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 2
Incorreto
Atingiu 0,00 de 1,00
Questão 3
Incorreto
Atingiu 0,00 de 1,00
Questão 4
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
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. II e III estão corretas
c. I, II e III estão corretas
d. I e III estão corretas
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 
Questão 5
Incorreto
Atingiu 0,00 de 1,00
Questão 6
Correto
Atingiu 1,00 de 1,00
Na implementação de listas de prioridades, podemos utilizar três abordagens, mais detalhadas abaixo.
Classifique os trechos com V(verdadeiro) ou F (falso) e escolha uma das alternativas:
 Na implementação por lista não ordenada, um novo nó da tabela pode ser colocado em qualquer posição
conveniente, dependendo do tipo de alocação utilizada, sequencial ou encadeada e a remoção implica
percorrer a tabela em busca do elemento de maior prioridade; 
 Na implementação por lista ordenada, a remoção é imediata porque, estando as prioridades já ordenadas,
o primeiro elemento é o que interessa 
 Na implementação por lista não ordenada, a inserção obriga a um percurso pela lista para procurar sua
posição correta; 
 Na implementação por heap, o campo de prioridade aparece como rótulo do nó e os nós são numerados
sequencialmente da raiz para os níveis mais baixos, da esquerda para a direita; 
 Na implementação por heap, a tabela não pode ser disposta numa árvore binária completa, na qual o
elemento de maior prioridade seja sempre o primeiro da ordenação, isto é, a raiz da árvore.
Escolha uma opção:
a. F, F, V, F, V
b. V, F, F, V, F
c. V, F, F, F, V
d. V, V, F, V, V
e. V, V, F, V, F
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 linear
b. tentativa binária
c. hash duplo
d. tentativa quadrática
Questão 7
Parcialmente correto
Atingiu 0,80 de 1,00
Questão 8
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(70) 
h(54)  
h(32) 
h(47) 
h(72) 
1 2
1 2
5
10
4
3
3
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 
 
Questão 9
Correto
Atingiu 1,00 de 1,00
Questão 10
Parcialmente correto
Atingiu 0,60 de 1,00
Ao comparar duas formas comuns de implementação de listas de prioridade, uma usando lista ordenada e
outra usando heap binária, ambos armazenados em vetor, conclui-se que:
Escolha uma opção:
a. Heap binária é mais indicada, pois apresenta complexidade O(1) para inserção e remoção e O(log n)
para consulta;
b. Lista ordenada é mais indicada, pois apresenta complexidade O(1) para inserção, remoção e consulta;
c. Heap binária é mais indicada, pois apresenta complexidade O(log n) para inserção e remoção e O(1)
para consulta;

d. Ambas as escolhas são boas, pois apresentam as mesmas complexidades para inserção, remoção e
consulta;
e. Lista ordenada é mais indicada, pois, apesar de sua complexidade de inserção ser O( n ), suas
complexidades de remoção e consulta são O( 1 );
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 busca
O(1)
operação de inserção
comprimento da lista
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 ►
Manter contato
Suporte Técnico ao Usuário
 https://suporteagetic.ufms.br
 (67) 3345-7613
https://ava.ufms.br/mod/quiz/view.php?id=738679&forceview=1
https://ava.ufms.br/mod/url/view.php?id=738683&forceview=1
https://suporteagetic.ufms.br/
tel:(67) 3345-7613
 suporte.agead@ufms.br

mailto:suporte.agead@ufms.br
https://api.whatsapp.com/send?phone=556733457613