ESTRUTURA DE DADOS - SEMANA 4 - NOTA 10

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 1.</p><p>Forçar conclusão Este teste pode ser salvo e retomado posteriormente.</p><p>Suas respostas foram salvas automaticamente.</p><p>Um procedimento natural para resolver os problemas de colisões consiste em guardar as chaves sinônimas em listas encadeadas.</p><p>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</p><p>aos endereços-base serão apenas os principais dessas listas. Um campo para o encadeamento deve ser adicionado a cada nó. A</p><p>__________ 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; nós; cadeia</p><p>b. listas encadeadas; endereços; chave</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 1 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</p><p>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,</p><p>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</p><p>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+1) = (h(x, k – 1) + k) mod m, 0 < k <= m</p><p>d. h(x) = k mod m</p><p>e. h(x, k) = (h′(x) + k+1) mod m 0 < k <= m+1</p><p>PERGUNTA 2 1,42 pontos   Salva</p><p>Dada as propriedades de estruturas de dados a seguir:</p><p>Estrutura 1: estrutura linear em que o primeiro elemento a entrar tem que ser o primeiro a sair.</p><p>Estrutura 2: estrutura que mapeia a chave de busca diretamente para um endereço de memória (endereço base).</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>pilha, grafo, �la.</p><p>árvore, tabela hash, �la.</p><p>�la, tabela hash, pilha.</p><p>pilha, vetor ordenado, �la.</p><p>grafo, �la, tabela hash.</p><p>PERGUNTA 3 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 simplesmente</p><p>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</p><p>do código a seguir:</p><p>return  aluno.index:max_items;</p><p>return  aluno.get() > max_items;</p><p>return aluno.getRa() % max_items;</p><p>l</p><p>PERGUNTA 4 1,44 pontos   Salva</p><p>Estado de Conclusão da Pergunta:</p><p>29/08/24, 21:01 Fazer teste: Semana 4 - Atividade Avaliativa – ...</p><p>https://ava.univesp.br/webapps/assessment/take/launch.jsp?course_assessment_id=_194717_1&course_id=_13337_1&content_id=_1579387_1… 1/2</p><p>Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.</p><p>return  aluno.get() % max_items;</p><p>return aluno.index % max_items;</p><p>A presença de colisões, quando duas chaves k1 e k2 geram h(k1) = h(k2), impede que se faça imediatamente a inserção de um novo item (k,v)</p><p>diretamente em A[h(k)] no arranjo A.</p><p>Para resolver essa colisão, devemos:</p><p>a. utilizar tanto um espaço de memória adicional quanto um espaço no próprio arranjo.</p><p>b. somar as chaves k1 e k2.</p><p>c. criar um novo arranjo.</p><p>d. não é possível resolver essa colisão.</p><p>e. deletar o item k1.</p><p>PERGUNTA 5 1,44 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</p><p>para diminuir esse problema de colisões é diminuir o fator de carga, e à medida que o fator carga aumenta, a possibilidade de dar</p><p>colisões também aumenta. Com isso, as tabelas de dispersão atendem necessariamente a esse problema, que é a previsão de algum</p><p>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</p><p>uma lista encadeada. As colisões acontecem quando __________ são(é) iguais(l), impedindo diretamente a inserção de um novo</p><p>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. elemento; dado; memória adicional</p><p>b. ponteiro; duas chaves; memória adicional</p><p>c. ponteiro; dado; memória adicional</p><p>d. elemento; dado; locação de espaço</p><p>e. elemento; duas chaves; locação de espaço</p><p>PERGUNTA 6 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:</p><p>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</p><p>programador deve executá-lo em cada linha. O segundo analisa as colisões, separando-as em conjuntos de até 4 colunas.</p><p>b. 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</p><p>utilizada caso seja a primeira, última ou esteja exatamente no meio de hash. Caso essas posições estejam ocupadas, será apresentado erro no</p><p>fim da execução do código</p><p>c. 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</p><p>apresentar erro n o final. Isso dependerá exclusivamente dos comandos utilizados na estrutura do código.</p><p>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</p><p>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</p><p>números e comandos se repetem, diminuindo o tamanho do código.</p><p>e. O separate chaining é o encadeamento separado, que não procura por posições vagas dentro do array que define a tabela, enquanto o open</p><p>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</p><p>elementos são armazenados na própria tabela hash.</p><p>PERGUNTA 7 1,42 pontos   Salva</p><p>Salvar todas as respostas Salvar e Enviar</p><p>29/08/24, 21:01 Fazer teste: Semana 4 - Atividade Avaliativa – ...</p><p>https://ava.univesp.br/webapps/assessment/take/launch.jsp?course_assessment_id=_194717_1&course_id=_13337_1&content_id=_1579387_1… 2/2</p>