Estruturas de Dados - Semana 4 - Atividade Avaliativa UNIVESP 2023

Prévia do material em texto

Estruturas de Dados - Semana 4 - Atividade Avaliativa UNIVESP 2023 
 
PERGUNTA 1 
Um procedimento natural para resolver os problemas de colisões consiste em guardar as chaves 
sinônimas em listas encadeadas. Existem duas opções: as listas podem se localizar no exterior da 
tabela ou compartilhar o mesmo espaço da tabela. 
 O encadeamento exterior consiste em manter _____________, uma para cada endereço-base 
possível. Os _________ correspondentes aos endereços-base serão apenas os principais dessas 
listas. Um campo para o encadeamento deve ser adicionado a cada nó. A __________ interna 
consiste nos nós que correspondem a cada endereço de encadeamento possível. 
 
Preencha as lacunas escolhendo a alternativa CORRETA: 
 a. listas encadeadas; endereços; cadeia 
 b. ponteiros; endereços; chave 
 c. ponteiros; nós; chave 
 x d. listas encadeadas; nós; cadeia 
 e. listas encadeadas; endereços; chave 
1,44 pontos 
PERGUNTA 2 
Dada as propriedades de estruturas de dados a seguir: 
Estrutura 1: estrutura que mapeia a chave de busca diretamente para um endereço de memória 
(endereço base). 
Estrutura 2: estrutura linear em que o primeiro elemento a entrar tem que ser o primeiro a sair. 
Estrutura 3: estrutura linear em que as inserções e remoções ocorrem na mesma posição. 
Assinale a alternativa que apresenta, em ordem, as estruturas para as quais se referem as 
definições. 
 a. tabela dinâmica , fila, pilha, respectivamente. 
 b. fila, tabela hash, pilha, respectivamente. 
 x c. tabela hash, fila, pilha, respectivamente. 
 d. tabela hash, pilha, fila, respectivamente. 
 e. tabela hash, tabela hash, pilha, respectivamente. 
1,44 pontos 
PERGUNTA 3 
Uma tabela recebe chaves do tipo string e armazena os dados internamente como um vetor. A 
função de espalhamento da tabela Hash utiliza o seguinte procedimento para mapear as strings em 
inteiros: 
 
1 – Mapeamento de caracteres: os três primeiros caracteres são mapeados em inteiros da forma: 
https://ava.univesp.br/webapps/blackboard/execute/courseMain?course_id=_10667_1
 
 
 
 
 De a até f: mapeado para 1 
 De g até n: mapeado para 3 
 De o até s: mapeado para 5 
 De t até z: mapeado para 11 
 
2 – Os inteiros associados a cada um dos três primeiros caracteres são multiplicados entre si. 
 
3 – O resto da divisão por 11 é computado, dado que o vetor possui tamanho 11. 
 
Dadas as seguintes strings: ULISSES, DANIELLE e LARISSA, aplicando a função de espalhamento 
apresentada, indique a alternativa correta que apresenta a string e a posição obtida. 
 a. h(ulisses) = 8 
h(danielle) = 3 
h(larissa) = 0 
 b. h(ulisses) = 0 
h(danielle) = 0 
h(larissa) = 0 
 x c. h(ulisses) = 0 
h(danielle) = 3 
h(larissa) = 4 
 d. h(ulisses) = 8 
h(danielle) = 0 
h(larissa) = 4 
 e. h(ulisses) = 0 
h(danielle) = 0 
h(larissa) = 4 
1,42 pontos 
PERGUNTA 4 
Um método de busca bastante utilizado, conhecido como hash, baseia-se na utilização que mapeia 
chaves em endereços de memória, de modo que os dados associados a cada chave possam ser 
rapidamente localizados e lidos. Quando há conflitos de localização, algum algoritmo de separação é 
adotado. 
Considere uma tabela hash armazenada em um arquivo no disco rígido. Supondo-se que a mesma 
possua uma função de hash razoavelmente protegida de conflitos, o número médio de acessos ao 
disco, necessários para localizar uma chave em um universo de N chaves, é mais próximo de: 
 a. log2(N) 
 b. N/2 
 c. N*log2(N) 
 x d. 2 
 e. N / log2(N) 
1,42 pontos 
 
 
 
 
PERGUNTA 5 
Como o teste linear é usado quando há uma colisão em uma tabela de hash? Existem dois jeitos de 
lidar com uma colisão presente na tabela hash: separate chaining e open addressing. 
Diante disso, assinale a alternativa correta que demonstra o que cada um desses métodos faz. 
 a. O primeiro separa os erros por linhas e colunas, enquanto o segundo busca 
uma posição ainda não ocupada em hash. Esta posição só pode ser 
utilizada caso seja a primeira, última ou esteja exatamente no meio de 
hash. Caso essas posições estejam ocupadas, será apresentado erro no fim 
da execução do código 
 b. O primeiro define a tabela de acordo com a formatação do código, sempre 
levando em conta o resultado final; caso apresente erro, o programador 
deve executá-lo em cada linha. O segundo analisa as colisões, separando-as 
em conjuntos de até 4 colunas. 
 x c. O separate chaining é o encadeamento separado, que não procura por 
posições vagas dentro do array que define a tabela, enquanto o open 
addressing é o endereçamento aberto, que, no caso de uma colisão, 
percorre a tabela hash, buscando por uma posição ainda não ocupada. Os 
elementos são armazenados na própria tabela hash. 
 d. O primeiro define a tabela de acordo com a formatação do código, sempre 
levando em conta o resultado final. Caso apresente erro, o programador 
deve executá-lo em cada linha. O segundo analisa as posições ocupadas na 
tabela e copia em uma posição na qual apenas números e comandos se 
repetem, diminuindo o tamanho do código. 
 e. Ambos métodos têm a mesma função: são encadeamentos separados que 
não procuram posições vagas dentro do array e que podem ou não 
apresentar erro n o final. Isso dependerá exclusivamente dos comandos 
utilizados na estrutura do código. 
1,42 pontos 
PERGUNTA 6 
Uma função de dispersão deve satisfazer a necessidade de ser uniforme, em que todos os 
compartilhamentos tenham a mesma probabilidade de escolha. Deve também ter um bom aspecto 
para ser processado, sempre buscando um tempo menor de acesso, e produzir o menor número de 
colisões, para isso é necessário existir uma forma padrão para as chaves. 
 
A função de dispersão ou de espelhamento é responsável por criar um __________ para ter uma 
chave particular, se a função for mal escolhida, logo a tabela não terá um(a) ___________. A função 
de dispersão irá fornecer sempre índices únicos com as(os) ______________. 
 
 
Preencha as lacunas escolhendo a alternativa CORRETA 
 a. número aleatório; comunicação; chaves de entrada 
 b. número aleatório; bom desempenho; links 
 c. número aleatório; bom desempenho; chaves de entrada 
 x d. índice; bom desempenho; chaves de entrada 
 
 
 
 
 e. índice; comunicação; links 
1,43 pontos 
PERGUNTA 7 
As tabelas hash podem ser acessadas ao longo do tempo para que possam ser organizadas na 
memória como arrays. As chaves podem ser de qualquer tipo de dados, mas as pesquisas de matriz 
exigem uma função que mapeia as chaves para números inteiros. 
 
Com base nesses aspectos, assinale a alternativa que descreve a função que mapeia chaves em 
números inteiros. 
 a. Função de colisão 
 b. Função de tempo constante 
 c. Função de vetorização 
 d. Função de encadeamento 
 x e. Função de espalhamento