COM-160-SEMANA-4

Prévia do material em texto

<p>Fazer teste: Semana 4 - Atividade Avaliativa</p><p>Informações do teste</p><p>Descrição</p><p>Instruções Atividade para avaliação</p><p>Consulte os gabaritos dessa disciplina no menu lateral.</p><p>Olá, estudante!</p><p>1. Para responder a esta atividade, selecione a(s) alternativa(s) que você considerar correta(s);</p><p>2. Após selecionar a resposta correta em todas as questões, vá até o �m da página e pressione “Enviar teste”.</p><p>3. A cada tentativa, as perguntas e alternativas são embaralhadas</p><p>Pronto! Sua atividade já está registrada no AVA.</p><p>Várias tentativas Este teste permite 3 tentativas. Esta é a tentativa número 2.</p><p>Forçar conclusão Este teste pode ser salvo e retomado posteriormente.</p><p>Suas respostas foram salvas automaticamente.</p><p>Uma tabela hash recebe como chave valores inteiros. Internamente, a tabela hash foi implementada como um vetor de tamanho 13, com elementos indexados de 0 a 12.</p><p>Para tratamento de colisões, é usado o teste linear. Vamos assumir que a seguir temos uma tabela hash obtida após algumas operações de inserção.</p><p>Note que "-1" indica uma posição vazia. Dito isso, assinale a alternativa correta.</p><p>Observando a con�guração atual da tabela hash, podemos concluir que apenas uma colisão ocorreu, dado que apenas um elemento está posicionado em lugar diferente daquele indicado pela função de espalhamento.</p><p>Se removermos o 98 e depois inserirmos o elemento 15, este último �cará na posição 7.</p><p>Se tentarmos inserir o elemento 24, criaremos uma colisão com o elemento 52, sendo que esta colisão será tratada pelo teste linear adicionando o 24 na posição 1.</p><p>Se inserirmos o elemento 60, ele será �sicamente colocado exatamente na posição indicada pela função de espalhamento.</p><p>Se quisermos inserir o elemento 20, ele será mapeado pela função de espalhamento para a posição onde está o elemento 98. Nesse caso, o teste linear tentaria colocar na posição seguinte, que também está ocupada pelo elemento 99, restando então colocar o elemento 20 na posição 9, que está livre.</p><p>PERGUNTA 1 1,42 pontos   Salva</p><p>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á con�itos de localização, algum algoritmo de separação é adotado.</p><p>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 con�itos, 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:</p><p>a. 2</p><p>b. N / log2(N)</p><p>c. N/2</p><p>d. N*log2(N)</p><p>e. log2(N)</p><p>PERGUNTA 2 1,42 pontos   Salva</p><p>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.</p><p>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) ______________.</p><p>Preencha as lacunas escolhendo a alternativa CORRETA</p><p>a. índice; comunicação; links</p><p>b. número aleatório; bom desempenho; links</p><p>c. número aleatório; bom desempenho; chaves de entrada</p><p>d. número aleatório; comunicação; chaves de entrada</p><p>e. índice; bom desempenho; chaves de entrada</p><p>PERGUNTA 3 1,44 pontos   Salva</p><p>As tabelas hash minimizam a complexidade de tempo para as operações dinâmicas como Inserção, Remoção, Busca e Modi�cação. Admita as seguintes a�rmações:</p><p>I. A função hash(chave) deve ser determinística. Para uma determinada chave, a função sempre retorna o mesmo valor de hash.</p><p>II. Por ser utilizada como uma função de indexação, a função de hash deve sempre retornar um valor de hash dentro dos limites da tabela [0,N], em que N é o tamanho da tabela.</p><p>III. O método aproveita a possibilidade de acesso randômico à memória para alcançar uma complexidade média de O(log(n)).</p><p>Assinalar a alternativa correta:</p><p>a. Apenas a II.</p><p>b. Todas estão corretas, I, II e III.</p><p>c. Apenas I e II.</p><p>d. Apenas a I</p><p>e. Apenas I e III</p><p>PERGUNTA 4 1,44 pontos   Salva</p><p>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.</p><p>Com base nesses aspectos, assinale a alternativa que descreve a função que mapeia chaves em números inteiros.</p><p>a. Função de colisão</p><p>b. Função de encadeamento</p><p>c. Função de vetorização</p><p>d. Função de tempo constante</p><p>e. Função de espalhamento</p><p>PERGUNTA 5 1,44 pontos   Salva</p><p>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.</p><p>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.</p><p>Preencha as lacunas escolhendo a alternativa CORRETA:</p><p>a. listas encadeadas; endereços; cadeia</p><p>b. ponteiros; endereços; chave</p><p>c. ponteiros; nós; chave</p><p>d. listas encadeadas; nós; cadeia</p><p>e. listas encadeadas; endereços; chave</p><p>PERGUNTA 6 1,42 pontos   Salva</p><p>A tentativa linear h(x,k) é uma implementação muito simples, em que o endereço-base x é 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.</p><p>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.</p><p>a. h(x, k) = (h′(x) + k) mod m, 0 ≤ k ≤ m – 1</p><p>b. h(x, k) = (h′(x) + k+1) mod m</p><p>c. h(x, k) = (h′(x) + k+1) mod m 0 < k <= m+1</p><p>d. h(x, k+1) = (h(x, k – 1) + k) mod m, 0 < k <= m</p><p>e. h(x) = k mod m</p><p>PERGUNTA 7 1,42 pontos   Salva</p><p>Estado de Conclusão da Pergunta:</p><p>Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas. Salvar todas as respostas Salvar e Enviar</p><p>Estruturas de Dados - COM160 - Turma 001</p><p>Informações do teste</p><p>Descrição</p><p>Instruções Atividade para avaliação</p><p>Consulte os gabaritos dessa disciplina no menu lateral.</p><p>Olá, estudante!</p><p>1. Para responder a esta atividade, selecione a(s) alternativa(s) que você considerar correta(s);</p><p>2. Após selecionar a resposta correta em todas as questões, vá até o �m da página e pressione “Enviar teste”.</p><p>3. A cada tentativa, as perguntas e alternativas são embaralhadas</p><p>Pronto! Sua atividade já está registrada no AVA.</p><p>Várias tentativas Este teste permite 3 tentativas. Esta é a tentativa número 1.</p><p>Forçar conclusão Este teste pode ser salvo e retomado posteriormente.</p><p>Suas respostas foram salvas automaticamente.</p><p>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.</p><p>Com base nesses aspectos, assinale a alternativa que descreve a função que mapeia chaves em números inteiros.</p><p>a. Função de tempo constante</p><p>b. Função de vetorização</p><p>c. Função de colisão</p><p>d. Função de espalhamento</p><p>e. Função de encadeamento</p><p>PERGUNTA 1 1,44 pontos   Salva</p><p>É dada a implementação da função de hash abaixo (incompleta) apresentada na videoaula. Considere que nesta implementação estamos</p><p>simplesmente garantindo que não colocaremos um registro fora dos limites do vetor (considera a não existência de colisões). Indique qual é alternativa correta para a linha 15 do código a seguir:</p><p>return aluno.getRa() % max_items;</p><p>return  aluno.index:max_items;</p><p>return  aluno.get() > max_items;</p><p>return aluno.index % max_items;</p><p>return  aluno.get() % max_items;</p><p>PERGUNTA 2 1,44 pontos   Salva</p><p>As tabelas hash minimizam a complexidade de tempo para as operações dinâmicas como Inserção, Remoção, Busca e Modi�cação. Admita as seguintes a�rmações:</p><p>I. A função hash(chave) deve ser determinística. Para uma determinada chave, a função sempre retorna o mesmo valor de hash.</p><p>II. Por ser utilizada como uma função de indexação, a função de hash deve sempre retornar um valor de hash dentro dos limites da tabela [0,N], em que N é o tamanho da tabela.</p><p>III. O método aproveita a possibilidade de acesso randômico à memória para alcançar uma complexidade média de O(log(n)).</p><p>Assinalar a alternativa correta:</p><p>a. Apenas I e II.</p><p>b. Apenas a II.</p><p>c. Apenas a I</p><p>d. Apenas I e III</p><p>e. Todas estão corretas, I, II e III.</p><p>PERGUNTA 3 1,44 pontos   Salva</p><p>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.</p><p>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.</p><p>Preencha as lacunas escolhendo a alternativa CORRETA:</p><p>a. listas encadeadas; endereços; chave</p><p>b. listas encadeadas; nós; cadeia</p><p>c. ponteiros; nós; chave</p><p>d. ponteiros; endereços; chave</p><p>e. listas encadeadas; endereços; cadeia</p><p>PERGUNTA 4 1,42 pontos   Salva</p><p>Dada as propriedades de estruturas de dados a seguir:</p><p>Estrutura 1: estrutura que mapeia a chave de busca diretamente para um endereço de memória (endereço base).</p><p>Estrutura 2: estrutura linear em que o primeiro elemento a entrar tem que ser o primeiro a sair.</p><p>Estrutura 3: estrutura linear em que as inserções e remoções ocorrem na mesma posição.</p><p>Assinale a alternativa que apresenta, em ordem, as estruturas para as quais se referem as de�nições.</p><p>a. tabela dinâmica , �la, pilha, respectivamente.</p><p>b. tabela hash, tabela hash, pilha, respectivamente.</p><p>c. tabela hash, �la, pilha, respectivamente.</p><p>d. �la, tabela hash, pilha, respectivamente.</p><p>e. tabela hash, pilha, �la, respectivamente.</p><p>PERGUNTA 5 1,42 pontos   Salva</p><p>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.</p><p>Diante disso, assinale a alternativa correta que demonstra o que cada um desses métodos faz.</p><p>a. 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.</p><p>b. 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.</p><p>c. 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.</p><p>d. 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.</p><p>e. 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</p><p>PERGUNTA 6 1,42 pontos   Salva</p><p>Com chaves diferentes é possível encontrar o mesmo endereço-base, esse problema podemos denominar como colisão. Um método para diminuir esse problema de colisões é diminuir o fator de carga, e à medida que o fator carga aumenta, a possibilidade de dar colisões também aumenta. Com isso, as tabelas de dispersão atendem necessariamente a esse problema, que é a previsão de algum método de tratamento de colisões.</p><p>Uma ideia simples para resolver a questão de colisões é realizar o procedimento para que cada endereço seja um ___________ para uma lista encadeada. As colisões acontecem quando __________ são(é) iguais(l), impedindo diretamente a inserção de um novo elemento. Para resolver isso, é possível utilizar um espaço de _____________ ou um espaço no próprio vetor.</p><p>Preencha as lacunas escolhendo a alternativa CORRETA.</p><p>a. ponteiro; duas chaves; memória adicional</p><p>b. elemento; dado; locação de espaço</p><p>c. elemento; dado; memória adicional</p><p>d. ponteiro; dado; memória adicional</p><p>PERGUNTA 7 1,42 pontos   Salva</p><p>Estado de Conclusão da Pergunta:</p><p>ALTERNATIVA ERRADA</p>