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

Prévia do material em texto

ORGULHOSAMENTE FEITO COM 
Feito com  por conecti.me
ESTRUTURA DE DADOS-T01-2024-1
Painel Meus cursos 32010001871-T01-2024-1 📚 Módulo 1 ✅ [A1] Avaliação do Módulo 1 - Hash e Heap
Questão 1
Correto
Atingiu 1,00 de
1,00
Marcar
questão
Questão 2
Parcialmente
correto
Atingiu 0,50
de 1,00
Marcar
questão
Questão 3
Incorreto
Atingiu 0,00
de 1,00
Marcar
questão
Questão 4
Correto
Atingiu 1,00 de
1,00
Marcar
questão
Questão 5
Incorreto
Atingiu 0,00
de 1,00
Marcar
questão
Questão 6
Correto
Atingiu 1,00 de
1,00
Marcar
questão
Questão 7
Incorreto
Atingiu 0,00
de 1,00
Marcar
questão
Questão 8
Incorreto
Atingiu 0,00
de 1,00
Marcar
questão
Questão 9
Parcialmente
correto
Atingiu 0,40
de 1,00
Marcar
questão
Questão 10
Correto
Atingiu 1,00 de
1,00
Marcar
questão
Iniciado em segunda, 25 mar 2024, 11:55
Estado Finalizada
Concluída em segunda, 25 mar 2024, 13:47
Tempo
empregado
1 hora 51 minutos
Avaliar 4,90 de um máximo de 10,00(49%)
Comentários
Terminar revisão
Analise as sequências e associe corretamente:
14 18 24 32 17 29 33 36 35 
44 43 39 42 38 35 36 41 34 
Não é um Heap.
É um max-heap.
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  72  83  67  53  59  64  58  62  52 
 
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. 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 );

b. Lista ordenada é mais indicada, pois apresenta complexidade O(1) para inserção,
remoção e consulta;
c. Ambas as escolhas são boas, pois apresentam as mesmas complexidades para
inserção, remoção e consulta;
d. Heap binária é mais indicada, pois apresenta complexidade O(log n) para inserção
e remoção e O(1) para consulta;
e. Heap binária é mais indicada, pois apresenta complexidade O(1) para inserção e
remoção e O(log n) para consulta;
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 
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, F, V
c. V, F, F, V, F
d. V, V, F, V, F
e. V, V, F, V, F
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. Não é possível utilizar chaves que são cadeias de caracteres neste método.
b. 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.

c. Uma chave k é mapeada para uma das m posições da tabela hash, na qual a
função hash é h(k) = k / m
d. Um número primo não muito próximo de uma potência exata de 2 é uma boa
escolha para m (tamanho da tabela).

Um heap possui propriedades especiais que têm que ser mantidas por todas as
operações nele realizadas. Levando em consideração estas propriedades para um heap
de max-prioridades armazenado em um vetor, analise as afirmativas abaixo:
I  – 60,50,59,49,55,56 representa um heap sintaticamente correto;
II – Dado o heap 23,16,11,8,6, a inserção do elemento 14 se dá através dos passos:
23,16,11,8,6,14 →  23,16,14,8,6,11
III – Dado o heap 23,16,11,8,6, a retirada do elemento da primeira posição se dá
através dos passos:
6,16,11,8 → 16,6,11,8 → 16,8,11,6
É correto, apenas, o que se afirma em:
Escolha uma opção:
a. II e III
b. I e II
c. II
d. I
e. III
O fator de carga de qualquer tabela de dispersão é no máximo 1.
Escolha uma opção:
Verdadeiro
Falso 
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
comprimento da lista
O(1) operação de inserção
operação de busca
Sejam x1 e x2 dois dados quaisquer a serem armazenados em uma tabela hashing T. Seja
h(x) a função de dispersão utilizada. Uma colisão em T ocorre quando h(x1) ≠ h(x2).
Escolha uma opção:
Verdadeiro
Falso 
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 ►
Navegação do
questionário
ALAN DA COSTA SAUCEDO
Mostrar uma página por vez
Terminar revisão
1 2 3 4 5 6
7 8 9 10
Usuários Online
1 usuário online (últimos 5
minutos)
ALAN DA COSTA SAUCEDO

Manter contato
Suporte Técnico ao Usuário
 https://suporteagetic.ufms.br
 (67) 3345-7613
 suporte.agead@ufms.br











    
https://moodle.org/
https://moodle.org/
http://conecti.me/
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
https://ava.ufms.br/mod/quiz/view.php?id=738681
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://ava.ufms.br/user/view.php?id=56930&course=53721
https://ava.ufms.br/mod/quiz/review.php?attempt=879179&cmid=738681&showall=0
https://ava.ufms.br/mod/quiz/view.php?id=738681
https://ava.ufms.br/user/view.php?id=56930&course=53721
https://ava.ufms.br/user/view.php?id=56930&course=53721
https://suporteagetic.ufms.br/
tel:(67) 3345-7613
mailto:suporte.agead@ufms.br
https://api.whatsapp.com/send?phone=556733457613
javascript:void(0);
https://ava.ufms.br/user/index.php?id=53721
https://ava.ufms.br/theme/moove/certificates.php?id=53721
https://ava.ufms.br/admin/tool/lp/coursecompetencies.php?courseid=53721
https://ava.ufms.br/grade/report/index.php?id=53721
https://ava.ufms.br/my/
https://ava.ufms.br/?redirect=0
https://ava.ufms.br/calendar/view.php?view=month&course=53721
javascript:void(0);
https://ava.ufms.br/user/files.php
https://ava.ufms.br/