Atividade 2_ Estrutura de Dados

Prévia do material em texto

Atividade 2
Entrega 22 de out de 2023 em 23:59
Pontos 1
Perguntas 5
Disponível 14 de ago de 2023 em 0:00 - 22 de out de 2023 em 23:59
Limite de tempo Nenhum
Tentativas permitidas 2
Instruções
Este teste não está mais disponível, pois o curso foi concluído.
Histórico de tentativas
Tentativa Tempo Pontuação
MAIS RECENTE Tentativa 1 847 minutos 0,6 de 1
Pontuação desta tentativa: 0,6 de 1
Enviado 17 de out de 2023 em 10:06
Esta tentativa levou 847 minutos.

Pergunta 1
0 / 0,2 pts
Importante:
Caso você esteja realizando a atividade através do aplicativo "Canvas Student", é necessário que
você clique em "FAZER O QUESTIONÁRIO", no final da página.
Leia o trecho abaixo:
 
Um algoritmo é projetado em função de tipos abstratos de dados. Para implementá-los em uma
linguagem de programação é necessário representá-los de alguma maneira nessa linguagem,
utilizando tipos e operações suportadas pelo computador. Na representação do tipo abstrato de
dados, emprega-se uma estrutura de dados. É durante o processo de implementação que a
estrutura de armazenamento dos valores é especificada e os algoritmos que desempenharão o
papel das funções (operações) são projetados. Uma estrutura de dados é um meio para armazenar
e organizar dados com o objetivo de facilitar o acesso e as modificações. As estruturas diferem umas
das outras pela disposição ou manipulação de seus dados, de modo que não se pode separar as
estruturas de dados e os algoritmos associados a elas. Todos os problemas a serem resolvidos por
algoritmos possuem dados que precisam ser armazenados, e o são em estruturas, de acordo com o
contexto do problema. A escolha de um algoritmo para resolver um problema depende também do
tipo de estrutura utilizada para armazenamento dos dados. Assim, uma estrutura é escolhida de
A+
A
A-
10/06/2024, 14:58 Atividade 2: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158714?module_item_id=878030 1/9
https://famonline.instructure.com/courses/31357/quizzes/158714/history?version=1
Resposta correta
 
Projetamos um algoritmo para obter a solução de um determinado problema. Um problema pode ser resolvido de
mais de uma maneira.
 
Escrevemos algoritmos sempre passo a passo. A escrita de algoritmos é um processo e é executado assim que o
domínio do problema foi descoberto.
 
A eficiência de um algoritmo pode ser analisada somente após a implementação. Esta é uma análise empírica de
um algoritmo.
Você respondeu
 
Os algoritmos são criados dependentes das linguagens subjacentes, um algoritmo pode ser implementado em uma
linguagem de programação.
Esta alternativa é incorreta, pois algoritmo é um procedimento passo a passo, que define um
conjunto de instruções a serem executadas em uma determinada ordem para obter a saída
desejada. Os algoritmos geralmente são criados independentemente das linguagens subjacentes, ou
seja, um algoritmo pode ser implementado em mais de uma linguagem de programação.
Desse modo, a alternativa correta é aquela que diz que projetamos um algoritmo para obter a
solução de um determinado problema. Um problema pode ser resolvido de mais de uma maneira.
Assim, muitos algoritmos de solução podem ser derivados para um determinado problema. O
próximo passo é analisar os algoritmos de solução propostos e implementar a solução mais
adequada.
 
Há padrões bem definidos para escrever algoritmos. Os algoritmos sempre são escritos para suportar um código
de programação específico.

Pergunta 2
0,2 / 0,2 pts
acordo com as operações que podem ser realizadas sobre ela e com o custo de cada uma dessas
operações.
 
Fonte: ASCENCIO, A. F. G.; ARAÚJO, G. S. Estrutura de Dados: algoritmos, análise da
complexidade e implementações em Java e C/C++. São Paulo: Contentus, 2010.
 
Considerando as informações apresentadas, assinale a opção correta.
Leia o texto a seguir:
 
A+
A
A-
10/06/2024, 14:58 Atividade 2: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158714?module_item_id=878030 2/9
 das colisões.
Correto!
 da função hash usada.
A alternativa está correta, pois a eficiência do mapeamento depende da eficiência da função hash
usada. Uma função de hash pega um grupo de caracteres (chaves) e o mapeia para um valor de um
determinado comprimento (valor de hash ou hash).
 dos pares de valores-chave.
 dos bancos de dados.
 da implementação de objeto.
A alternativa está correta, pois a eficiência do mapeamento depende da eficiência da função hash
usada. Uma função de hash pega um grupo de caracteres (chaves) e o mapeia para um valor de um
determinado comprimento (valor de hash ou hash).

Pergunta 3
0,2 / 0,2 pts
O que é uma Tabela Hash?
Uma tabela hash, tabela de dispersão ou ainda tabela de espalhamento, é uma estrutura de dados
utilizada para tornar o processo de busca mais eficiente. Assim, esta estrutura de dados é muito
utilizada não para inserções ou remoções, mas quando há a necessidade de realizar muitas buscas
e com rápido tempo de resposta.
Imagine um vetor, estrutura de dados homogênea [...]. Para descobrir se um dado elemento está ou
não no vetor precisamos percorrer todo o vetor procurando pelo elemento. Isso pode ser muito
demorado dependendo da quantidade de buscas necessárias e principalmente do tamanho do vetor.
Em uma tabela hash é possível acessar diretamente a posição da tabela onde o elemento deve estar
caso ele exista, tornando o processo de busca muito mais eficiente.
Como implementar uma tabela hash?
Uma tabela hash pode ser implementada de diferentes formas [...] usando vetor e lista encadeada.
 
Fonte: GASPAR, W. O que é e como funciona a estrutura de dados Tabela Hash? Wagner Gaspar,
30 ago. 2021. Disponível em: https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-
de-dados-tabela-hash/ (https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-
tabela-hash/) . Acesso em: 27 set. 2022.
 
Hashing é uma técnica ou processo de mapeamento de chaves e valores na tabela de hash usando
uma função de hash. Isso é feito para acesso mais rápido aos elementos. A eficiência do
mapeamento depende da eficiência
A+
A
A-
10/06/2024, 14:58 Atividade 2: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158714?module_item_id=878030 3/9
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-tabela-hash/
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-tabela-hash/
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-tabela-hash/
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-tabela-hash/
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-tabela-hash/
 II, apenas.
 I e III, apenas.
Leia o texto a seguir:
 
Um exemplo de função hash pode ser aquele que leva em consideração o resto de uma divisão para
definir a posição na estrutura de dados. Porém uma função hash não apresenta uma fórmula
definida, e deve ser projetada levando-se em consideração o tamanho do conjunto de dados, seu
comportamento e os tipos de dados-chave utilizados. As funções hash são o cerne na construção
das tabelas hashing, e o desenvolvimento de uma boa função de hash é essencial para que o
armazenamento dos dados, a busca e o tratamento de colisões [...] ocorram de forma mais eficiente
possível. Uma boa função hash, em suma, deve ser:
Fácil de ser calculada. De nada valeria termos uma função com cálculos tão complexos e lentos
que todo o tempo que seria ganho no acesso a informação com complexidade 0(1), seria perdido
calculando uma custosa função de hash;
Capaz de distribuir palavras-chave o mais uniforme possível;
Capaz de minimizar colisões. Os dados devem ser inseridos de uma forma que as colisões sejam
as mínimas possíveis, reduzindo o tempo gasto resolvendo colisões e também reavendo os
dados;
Capaz de resolver qualquer colisão que ocorrer.
 
Fonte: BORIN, Vinicius Pozzobon. Estrutura de dados. São Paulo: Contentus, 2020.
 
Considerando as informações, avalie as afirmaçõesa seguir:
 
I. Uma vantagem da sondagem linear é a tendência de agrupamento, ou seja, os itens ficam
agrupados na tabela. Isso terá um impacto em outros itens que estão sendo inseridos.
 
II. Se a função hash for perfeita, as colisões nunca ocorrerão. No entanto, como isso geralmente não
é possível, a resolução de colisões se torna uma parte muito importante do hash.
 
III. Uma maneira de lidar com o agrupamento é estender a técnica de sondagem linear para que, em
vez de procurar sequencialmente o próximo slot aberto, pulemos slots.
 
É correto o que se afirma em:
A+
A
A-
10/06/2024, 14:58 Atividade 2: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158714?module_item_id=878030 4/9
Correto!
 II e III, apenas.
A alternativa está correta.
A afirmação I está incorreta, pois uma desvantagem da sondagem linear é a tendência de
agrupamento, ou seja, os itens ficam agrupados na tabela. Isso significa que, se ocorrerem muitas
colisões no mesmo valor de hash, vários slots circundantes serão preenchidos pela resolução de
sondagem linear. Isso terá um impacto em outros itens que estão sendo inseridos.
A afirmação II está correta, pois quando dois itens fazem hash para o mesmo slot, devemos ter um
método sistemático para colocar o segundo item na tabela de hash. Este processo é chamado de
resolução de colisão. Se a função hash for perfeita, as colisões nunca ocorrerão. No entanto, como
isso geralmente não é possível, a resolução de colisões se torna uma parte muito importante do
hash.
A afirmação III está correta, pois uma maneira de lidar com o agrupamento é estender a técnica de
sondagem linear para que, em vez de procurar sequencialmente o próximo slot aberto, pulemos
slots, distribuindo assim de maneira mais uniforme os itens que causaram colisões. Isso reduzirá
potencialmente o clustering que ocorre.
 I e II, apenas.
 III, apenas.

Pergunta 4
0 / 0,2 pts
Leia o texto a seguir:
 
Uma tabela hashing é uma generalização de um vetor com m posições. Cada posição na tabela
representa um endereço. Os elementos a serem armazenados nela possuem um valor-chave que é
utilizado para calcular o endereço na tabela onde serão alocados.
Dado um conjunto C de chaves a serem armazenadas na tabela hashing, uma tabela de tamanho m,
com endereços variando de 0 a m-1 e dado um elemento x ∈ C , existe uma função de
espalhamento ou dispersão (ou função de hashing) que calcula o endereço (ou índice) onde x será
armazenado. A função de espalhamento tem o objetivo de reduzir o espaço de endereços para
armazenar os elementos de C. Em vez de ICI endereços, tem-se o espaço de m endereços.
A maioria das funções de hashing assume que os elementos-chave são números naturais. Mas é
possível encontrar casos em que strings são os elementos-chave. Nesses casos, utiliza-se como
número natural a soma dos códigos ASCII de cada caractere da string.
Um dos métodos para criar funções de hashing é o método da divisão. Uma chave x é mapeada em
um dos m endereços da tabela hashing calculando o resto da divisão de x por m , ou seja, a função
A+
A
A-
10/06/2024, 14:58 Atividade 2: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158714?module_item_id=878030 5/9
 I e II, apenas.
Você respondeu
 II, III e IV, apenas.
A alternativa está incorreta.
A afirmação I está correta, pois a ideia essencial por trás de uma tabela de dispersão é que todas as
informações sejam armazenadas em um array de tamanho fixo. O hashing é usado para identificar a
posição onde um item deve ser armazenado.
A afirmação II está incorreta, pois na realidade, não podemos esperar que as chaves sejam sempre
números inteiros. Dependendo da aplicação, as chaves podem ser letras, cadeias de caracteres ou
até mesmo estruturas de dados mais complexas.
de hashing é dada por h(x) = x mod m . Por exemplo, em uma tabela hashing com tamanho m = 8, a
chave x = 100 seria armazenada no endereço 4 [...].
 
Fonte: ASCENCIO, A. F. G.; ARAÚJO, G. S. Estrutura de Dados: algoritmos, análise da
complexidade e implementações em Java e C/C++. São Paulo: Contentus, 2010.
 
Um paradigma muito comum no processamento de dados envolve o armazenamento de informações
em uma tabela e, posteriormente, a recuperação das informações ali armazenadas.
 
Considerando as informações, avalie afirmações abaixo:
 
I. A ideia essencial por trás de uma tabela de dispersão é que todas as informações sejam
armazenadas em um array de tamanho fixo.
 
II. No dia a dia da aplicação de funções hash, na estrutura de dados, podemos esperar que as
chaves sejam sempre números inteiros.
 
III. Um método alternativo de lidar com colisões que elimina totalmente a necessidade de links e
encadeamento é chamado de endereçamento aberto.
 
IV. Funções de criptografia simétrica são muito mais rápidas do que funções hash computacionais.
 
É correto o que se afirma em:
A+
A
A-
10/06/2024, 14:58 Atividade 2: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158714?module_item_id=878030 6/9
A afirmação III está correta, pois um método alternativo de lidar com colisões que elimina totalmente
a necessidade de links e encadeamento é chamado de endereçamento aberto. A ideia básica é
definir uma sequência de sondagem para cada chave que, quando seguida, sempre leva à chave em
questão.
A afirmação IV está incorreta, pois funções hash computacionais são muito mais rápidas do que
funções de criptografia simétrica. Esses são aspectos relacionados à eficiência da operação hash.
 I e IV, apenas.
 II e IV, apenas.
Resposta correta
 I e III, apenas.

Pergunta 5
0,2 / 0,2 pts
Leia o texto a seguir:
Adotar números primos, especialmente aqueles não muito próximos aos valores de potência de 2,
tende a ser uma boa escolha para o tamanho do vetor com palavras-chaves alfanuméricas. Por
exemplo, suponhamos que temos 2000 conjuntos de caracteres para serem colocadas em uma
tabela hashing. Por projeto, definiu-se que realizar uma busca, em média, em até três posições
antes de encontrar um espaço vazio é considerado aceitável. Se fizermos . Para o valor
de m podemos adotar um número primo não muito próximo de um múltiplo de 2. Podemos usar o
valor 701. Nossa função hash resultante seria h(k) = k MOD 701.
Por fim, quando trabalhamos com valores-chave sendo conjuntos de caracteres, devemos tomar
cuidado com palavras que contenham as mesmas letras, mas em ordens diferentes (anagrama). Por
exemplo, uma palavra-chave com quatro caracteres chamada ROMA poderá gerar o mesmo
resultado que uma palavra-chave chamada AMOR, pois os caracteres são os mesmos rearranjados
de outra maneira. Uma função de hash deve ser cuidadosamente definida para tratar este tipo de
problema, caso ele venha a ser recorrente; caso contrário, teremos excessivas colisões [...]
 
Fonte: BORIN, Vinicius Pozzobon. Estrutura de dados. São Paulo: Contentus, 2020.
 
Considerando as informações, avalie as afirmações abaixo:
 
A+
A
A-
10/06/2024, 14:58 Atividade 2: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158714?module_item_id=878030 7/9
 I, III e IV, apenas.
 II e IV, apenas.
Correto!
 I, II e III, apenas.
A alternativa está correta.
A afirmação I está correta, pois os algoritmos de hash fornecem a camada extra de proteção
necessária para proteger a transmissão de uma mensagem ao seu destinatário. Na ciência da
computação, o hashing é uma prática comum usada para diversos fins, incluindo criptografia,
indexação de dados e compactação de dados.
A afirmação II está correta, pois os algoritmos de hash são frequentemente usados para impedir que
terceiros interceptem mensagens digitais. Tanto o hash quanto a criptografia protegem os dados
transformando-os em um formato seguro. No entanto, enquanto a criptografia usa um processo
chamado criptografia, o hashing usa uma fórmula matemática chamada função hash para truncar um
valor em outro.
A afirmação III está correta, pois uma colisão de hash ocorrequando um algoritmo de hash produz o
mesmo valor de hash para dois valores de entradas diferentes. Se colisões ocorrerem, os hackers
podem enganar o computador para dar-lhes acesso erroneamente sempre que fizerem login com
uma senha próxima o suficiente da senha original para produzir o mesmo hash.
A afirmação IV está incorreta, pois a melhor abordagem é usar os algoritmos de hash mais recentes
para impedir que invasores façam engenharia reversa dos valores de hash originais. Idealmente,
uma boa função de hash deve processar o valor de entrada rapidamente, minimizando a
possibilidade de colisão.
I. Os algoritmos de hash fornecem a camada extra de proteção necessária para proteger a
transmissão de uma mensagem ao seu destinatário.
 
II. Os algoritmos de hash são frequentemente usados para impedir que terceiros interceptem
mensagens digitais.
 
III. Uma colisão de hash ocorre quando um algoritmo de hash produz o mesmo valor de hash para
dois valores de entradas diferentes.
 
IV. A melhor prática é usar os algoritmos de hash tradicionais para autorizar que invasores façam
engenharia reversa dos valores de hash originais.
 
É correto o que se afirma em:
A+
A
A-
10/06/2024, 14:58 Atividade 2: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158714?module_item_id=878030 8/9
 III e IV, apenas.
 I e II, apenas.
Pontuação do teste: 0,6 de 1
A+
A
A-
10/06/2024, 14:58 Atividade 2: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158714?module_item_id=878030 9/9