Buscar

EDD-SEMANA 04

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 3, do total de 7 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 6, do total de 7 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Prévia do material em texto

EDD-SEMANA 04 
Pergunta 1 
1. 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 hash, pilha, fila, respectivamente. 
 b. tabela hash, tabela hash, pilha, respectivamente. 
 c. tabela dinâmica , fila, pilha, respectivamente. 
 d. tabela hash, fila, pilha, respectivamente. 
 e. fila, tabela hash, pilha, respectivamente. 
Pergunta2 
1. 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: 
 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) = 0 
h(danielle) = 0 
h(larissa) = 0 
 
 b. 
h(ulisses) = 8 
h(danielle) = 0 
h(larissa) = 4 
 
 c. 
h(ulisses) = 0 
h(danielle) = 0 
h(larissa) = 4 
 
 d. 
h(ulisses) = 8 
h(danielle) = 3 
h(larissa) = 0 
 
 e. 
h(ulisses) = 0 
h(danielle) = 3 
h(larissa) = 4 
Pergunta 3 
1. Seja f a função de espalhamento ou mapeamento e x a chave, o endereço de 
memória será atribuído por f(x). Os valores serão distribuídos em um vetor de N 
posições, sendo formado em um intervalo entre 0 e N-1. 
 
Sobre a utilização da função de mapeamento ou função hash, avalie se são (V) 
verdadeiras ou (F) falsas as afirmativas a seguir. 
I. ( ) Utilizada para guardar uma coleção de strings. 
II. ( ) Utilizada para obter os registros de maneira eficiente em tempo 
constante. 
III. ( ) Utilizada para acessar os arquivos no computador. 
IV. ( ) Utilizada para ter acesso a uma determinada aplicação. 
 
Assinale a alternativa que apresenta a sequência CORRETA. 
 a. V - V - F - V 
 b. F - V - F - V 
 c. V - F - V - F 
 d. V - V - F - F 
 e. F - V - F - F 
Pergunta 4 
1. A função hash atribui um valor para cada chave no intervalo de 0 a N-1, 
no qual N será a capacidade total do arranjo. Algo que seja provável de 
acontecer numa função hash é as colisões, e para ser uma boa função 
hash, é necessário produzir um baixo números de colisões. 
Com base nesses aspectos, assinale a alternativa que descreve a 
melhor forma de ter uma boa função hash com baixas colisões. 
 a. Criar índices numéricos 
 b. Fazer exclusões de chaves idênticas 
 c. Verificar as chaves 
 d. Usa um N primo. 
 e. Fazer bloqueios 
Pergunta 5 
1. Seja f a função de espalhamento ou mapeamento e x a chave, o endereço 
de memória será atribuído por f(x). Os valores serão distribuídos em um 
vetor de N posições, sendo formado em um intervalo entre 0 e N-1. 
 
Sobre a utilização da função de mapeamento ou função hash, avalie se 
são (V) verdadeiras ou (F) falsas as afirmativas a seguir. 
I. ( ) Utilizada para guardar uma coleção de dados. 
II. ( ) Utilizada para obter os registros de maneira rápida. 
III. ( ) Utilizada para acessar os arquivos no computador. 
IV. ( ) Utilizada para ter acesso a uma determinada aplicação. 
 
Assinale a alternativa que apresenta a sequência CORRETA. 
 a. V - V - F - F 
 b. F - V - F - F 
 c. V - V - V - F 
 d. V - F - F - V 
 e. F - F - V - V 
Pergunta 6 
1. 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: 
 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 7 
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) = 4 
 
 b. 
h(ulisses) = 8 
h(danielle) = 4 
h(larissa) = 5 
 
 c. 
h(ulisses) = 8 
h(danielle) = 5 
h(larissa) = 4 
 
 d. 
h(ulisses) = 8 
h(danielle) = 3 
h(larissa) = 5 
 
 e. 
h(ulisses) = 5 
h(danielle) = 5 
h(larissa) = 4 
Pergunta 7 
1. 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. índice; comunicação; links 
 b. índice; bom desempenho; chaves de entrada 
 c. número aleatório; bom desempenho; chaves de entrada 
 d. número aleatório; bom desempenho; links 
 e. número aleatório; comunicação; chaves de entrada 
Pergunta 8 
1. 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 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. 
 
 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 
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. 
 
 c. 
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 
 
 d. 
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. 
 
 e. 
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. 
Pergunta 9 
1. A tentativa linear h(x,k) é uma implementação muito simples, em que o 
endereço-basex é h'(x) (k=0), suponhamos que existe outra chave, x', 
ocupando o mesmo endereço de h'(x). A ideia da tentativa linear é buscar 
armazenar um novo nó, no endereço próximo, que consiste em h'(x) + 1 
(k=1), se por acaso já estiver ocupado, ele irá tentar em h'(x) + 2 (k=2), e 
assim sucessivamente. 
Com base nos aspectos que existem no método de tentativa linear, 
assinale a alternativa que descreve a função da tentativa linear para a 
(k+1)-ésima tentativa. 
 a. h(x, k) = (h′(x) + k) mod m, 0 ≤ k ≤ m – 1 
 b. h(x, k+1) = (h(x, k – 1) + k) mod m, 0 < k <= m 
 c. h(x, k) = (h′(x) + k+1) mod m 
 d. h(x) = k mod m 
 e. h(x, k) = (h′(x) + k+1) mod m 0 < k <= m+1 
Pergunta 10 
1. 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 vetorização 
 b. Função de espalhamento 
 c. Função de colisão 
 d. Função de tempo constante 
 e. Função de encadeamento

Outros materiais