Questões de Concurso

Considere uma estrutura de dados do tipo tabela de dispersão (hash table), utilizada para armazenar e recuperar dados de forma eficiente por meio de uma função de espalhamento (hash). Durante a inserção de elementos, pode ocorrer colisão, isto é, quando duas chaves diferentes são mapeadas para a mesma posição da tabela. Para tratar colisões, pode-se utilizar a técnica de endereçamento aberto (Open Addressing), na qual, ao ocorrer uma colisão, o sistema procura outra posição disponível na própria tabela, verificando sequencialmente as próximas posições livres (por exemplo: se a posição 2 está ocupada, tenta a 3, depois a 4, e assim sucessivamente). Nesse contexto, qual técnica de tratamento de colisões é descrita?

Analise as seguintes afirmativas sobre os conceitos relacionados às tabelas de dispersão.

I. Esse método aproveita a possibilidade de acesso randômico à memória para alcançar uma complexidade temporal média por operação de O(1), sendo o pior caso, entretanto, O(log n), em que n é a quantidade de chaves a serem armazenadas na tabela.
II. Uma das estratégias conhecidas para tratar colisões consiste em armazenar as chaves com o mesmo endereço-base em listas encadeadas. As listas podem se encontrar no exterior da tabela ou compartilhar o mesmo espaço dela.
III. A ideia básica do método de endereçamento aberto para tratamento de colisões é, caso ainda haja espaço, armazenar as chaves com o mesmo endereço-base na própria tabela, mas sem a necessidade da criação de listas encadeadas.

Com relação a essas afirmativas, pode-se afirmar que

A função hash é utilizada para inserir ou buscar um elemento, mas podem ocorrer colisões quando a função hash produz o mesmo endereço para chaves diferentes. 



Assinalar a alternativa que explica corretamente o que a imagem acima representa:

Estruturas de dados são fundamentais para a eficiência de algoritmos, influenciando diretamente o desempenho de operações como busca, inserção e remoção. Entre essas estruturas, a tabela hash uliliza uma função hash para mapear chaves a posições em uma estrutura de armazenamento, proporcionando alto desempenho quando bem distribuída.
Considerando o cenário ideal de funcionamento de uma tabela hash, em que a função hash distribui uniformemente as chaves e há baixa ocorrência de colisões, assinale a alternativa que representa CORRETAIVENTE a complexidade da operação de busca nessa estrutura.

Um importante problema de segurança para os sistemas operacionais é a autenticação, um processo de segurança que visa comprovar a identidade de um usuário. O sistema de proteção deve identificar os usuários para prover a correta autorização de acesso aos recursos do sistema. Um processo de autenticação amplamente utilizado pelos sistemas é a validação de credenciais de acesso formadas por nome e senha. Para proteger as senhas armazenadas no banco de dados, é comum temperar a senha (password salting) e usar um algoritmo de HASH.
As técnicas de salting e HASH são adotadas simultaneamente nos esquemas