Colaborar - Av - Subst 2 - Algoritmos e Estrutura de Dados

Prévia do material em texto

Portal Digital
do Aluno
(/index/index)
Início (/)   Sistemas de Informação - Bacharelado - 3º S…   Algoritmos e Estrutura de Dados (/aluno/ti…   Av - Subst. 2 - Algoritmos e Estrutura de Da…
Av - Subst. 2 - Algoritmos e Estrutura de Dados

(/notificacao/index)
Meus Cursos (/index/index) Serviços Online Apoio ao Estudo Oportunidades Ajuda  Area do Usuário  Sair
Informações Adicionais
Período: 06/06/2023 00:00 à 10/06/2023 23:59
Situação:
Tentativas: 0 / 3
A atividade está fora do período do cadastro
1) Apesar da diferença entre as estruturas, as Tabelas de Espalhamento podem utilizar as Listas Ligadas, Vetores ou Árvores como estruturas auxiliares para
armazenamento de informações. O armazenamento e busca de uma informação é realizada calculando-se o valor da Função de Espalhamento para a chave, e
direcionando para o índice da lista correspondente.
 
Caso o tamanho das listas seja grande, a busca pode se tornar ineficiente, pois a busca nas listas se torna sequencial. Esta frase foi o início da conversa entre
Márcio e Luiz que estamos discordando em relação a utilização de Tabelas de Espalhamento ou Listas Ligadas. Luiz quer utilizar Listas Ligadas, mas Márcio insiste
em utilizar as Tabelas de Espelhamento.
 
Considerando o contexto apresentado, avalie as seguintes asserções e a relação proposta entre elas.
Esse site utiliza cookies para oferecer uma melhor experiência de navegação, analisar como você interage em nosso site, otimizar o desempenho e
personalizar o conteúdo. Ao utilizar este site, você concorda com o uso de cookies. Saiba mais em nosso Portal de Privacidade
(https://www.canaldatransparencia.com.br/cogna/).
Ok
https://colaboraread.com.br/index/index
https://colaboraread.com.br/
https://colaboraread.com.br/aluno/dashboard/index/3332022703
https://colaboraread.com.br/aluno/timeline/index/3332022703?ofertaDisciplinaId=1969752
https://colaboraread.com.br/notificacao/index
https://colaboraread.com.br/index/index
https://www.canaldatransparencia.com.br/cogna/
a)
b)
c)
d)
e)
2)
 
I. Luiz não queria utilizar a Tabela de Espelhamento pois a ordem dos conteúdos das informações acessados deveria ser preservada.
 
PORQUE 
 
II. Embora permita o acesso direto ao conteúdo das informações, o uso das Tabelas de Espalhamento possui uma desvantagem em relação as Listas Ligadas, pois
apesar de realizar a indexação dos elementos, a Tabela de Espalhamento não preserva a ordem em que são disponibilizados para a Função de Espalhamento.
A respeito dessas asserções, assinale a alternativa correta.
Alternativas:
as asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
as asserções I e II são proposições verdadeiras e a II é uma justificativa da I.
a asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
a asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
as asserções I e II são proposições falsas.
Conhecido também como re-hash, a Função de Espalhamento Duplo, ao invés de incrementar a posição do elemento até a próxima posição vazia, ela utiliza
uma função de espalhamento auxiliar para calcular qual o incremento que será dado à posição, levando em consideração o valor da chave.
 
Segundo Celes, Cerqueira, Rangel (2004), neste caso para o primeiro cálculo é utilizada a função h(k) = k mod N, onde h é a função, k é a chave e N é o número de
posições da tabela. Caso haja uma colisão, inicialmente calculamos h2(k), que pode ser definida como h2(k) = 1 + ( k mod (N-1) ). Em seguida é calculada a função
re-hashing como sendo: rh(i,k) = ( i + h2(k) ) mod N, sendo i o índice gerado.
 
Abaixo apresenta-se uma tabela com 8 índices.
 
Esse site utiliza cookies para oferecer uma melhor experiência de navegação, analisar como você interage em nosso site, otimizar o desempenho e
personalizar o conteúdo. Ao utilizar este site, você concorda com o uso de cookies. Saiba mais em nosso Portal de Privacidade
(https://www.canaldatransparencia.com.br/cogna/).
https://www.canaldatransparencia.com.br/cogna/
a)
b)
c)
d)
e)
3)
Sobre a aplicação da Função de Espalhamento Duplo na tabela apresentada, analise as afirmativas a seguir:
 
I. Ao inserir o elemento 17, o elemento será alocado na posição do índice 1.
II. Ao inserir o elemento 31, o elemento será alocado na posição do índice 3.
III. Ao inserir o elemento 32, o elemento será alocado na posição do índice 6.
IV. Ao inserir o elemento 34, o elemento será alocado na posição do índice 1.
Agora, assinale a alternativa que apresenta a correta:
Alternativas:
Apenas a afirmativa III está correta.
Apenas as afirmativas I e IV estão corretas.
Apenas as afirmativas II e III estão corretas.
Apenas as afirmativas I, II e IV estão corretas.
Apenas as afirmativas I, II, III e IV estão corretas.
Dentro da estrutura de Armazenamento Associativo, a função de Mapas Associativos é realizar a associação entre elementos dentro da estrutura, realizando a
associação entre uma chave e um valor recebidos, permitindo a recuperação rápida de um valor associado a uma chave. Umas das principais aplicações é na
construção de tabelas de símbolos, com plena utilização em compiladores e montadores.
 
Marcio é um desenvolvedor líder de um equipe muito competente que foi designada para desenvolver um sistema de caixa para um supermercado. Ele entende
que a utilização de uma chave em mapa, permite armazenar e localizar elementos que possam ser localizados rapidamente.
 
Esse site utiliza cookies para oferecer uma melhor experiência de navegação, analisar como você interage em nosso site, otimizar o desempenho e
personalizar o conteúdo. Ao utilizar este site, você concorda com o uso de cookies. Saiba mais em nosso Portal de Privacidade
(https://www.canaldatransparencia.com.br/cogna/).
https://www.canaldatransparencia.com.br/cogna/
a)
b)
c)
d)
e)
4)
Com base no contexto apresentado, analise as asserções abaixo.
 
I - Marcio irá utilizar a estrutura de Armazenamento Associativo e a função de Mapas Associativos.
PORQUE
II - Marcio irá utilizar o código de barras presente em todos os produtos para controlar as vendas e os estoques.
 
A respeito dessas asserções, assinale a alternativa correta.
Alternativas:
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
As asserções I e II são proposições falsas.
Os Mapas são estruturas de dados que implementam o tipo de situação de mapeamento em associação. Uma das formas mais simples de implementar um
Mapeamento é guardar as associações pertencentes a ele dentro de uma Lista podendo ser acessado por meio de um índice.
 
Pode-se implementar o trecho de código a seguir como um exemplo de verificação de existência de chave. Marcos escreveu este código, mas deixou seu
computador desprotegido e sua filha Luiza acabou apagando parte do código.
using namespace std;
/* Cria a estrutura da lista */
  struct Materias{
  string codigo;
  string disciplina;
};
Esse site utiliza cookies para oferecer uma melhor experiência de navegação, analisar como você interage em nosso site, otimizar o desempenho e
personalizar o conteúdo. Ao utilizar este site, você concorda com o uso de cookies. Saiba mais em nosso Portal de Privacidade
(https://www.canaldatransparencia.com.br/cogna/).
https://www.canaldatransparencia.com.br/cogna/
a)
b)
c)
d)
e)
int main(){
int chave;
/* Cria o Mapa com Lista */
map<int, Materias> MapaLista;
Materias mat;
/* Informa os dados para a associação */
mat.codigo = "103";
mat.disciplina = "ESTRUTURA DE DADOS I";
MapaLista[1] = mat;
mat.codigo = "203";
mat.disciplina = "ESTRUTURA DE DADOS II";
MapaLista[2] = mat;
mat.codigo = "303";
mat.disciplina = "ESTRUTURA DE DADOS III";
MapaLista[3] = mat;
printf("Informe a chave da disciplina: ");
scanf("%s",&chave);
/* Se achou a chave pesquisada, escreve Encontrou, caso contrario Nao Encontrou */
------------ linha apagada pela filha de Marcos  ------
    cout << "Nao Encontrado!\n" << endl;
else
    cout << "Encontrado!\n" << endl;
return 0;
}
 
Assinale a alternativa CORRETA que representa a linha de código apagada do código representado na linha.
Alternativas:
 if(MapaLista.find(chave) == MapaLista.erase(chave))
 if(MapaLista.erase(chave) == MapaLista.end())
 if(MapaLista.find(chave) == MapaLista.size())
 if(MapaLista.encontra(chave) == MapaLista.end())
 if(MapaLista.find(chave) == MapaLista.end())
Esse site utiliza cookies para oferecer uma melhor experiência de navegação, analisar como você interage em nosso site, otimizar o desempenho e
personalizar o conteúdo. Ao utilizar este site, você concorda com o uso de cookies. Saiba mais em nosso Portal de Privacidade
(https://www.canaldatransparencia.com.br/cogna/).
https://www.canaldatransparencia.com.br/cogna/
5)
a)
b)
Conforme Goodrich (2013), o principal objetivo do Mapa com Espalhamento é oferecer uma forma rápida de acessar o valor de uma chave desejada e assim
ter um desempenho da estrutura maior que as demais estruturas.
 
A utilização da técnica de Espalhamento pode obter um consumo de tempo médio constante para todas as operações. De acordo com este contexto, analise as
asserções abaixo:
 
I - A implementação ajuda a melhorar o desempenho:
/* Função para transformar a Tabela de Espalhamento em tabela dinâmica */void hashmapa_expand(HashMapa *hashmapa)
{  int i;  int hash_index;  int old_size = hashmapa -> map_size;  HashmapNo *hashmap_node;
hashmapa -> map_size = old_size * 2;  HashmapNo **new_node_list = malloc(hashmapa -> map_size * sizeof(HashmapNo*));  for (i = 0; i < hashmapa -> map_size;
i++)
{    new_node_list[i] = malloc(sizeof(HashmapNo));    new_node_list[i] = NULL;  }  for (i = 0; i < old_size; i++)
{    hashmap_node = hashmapa -> node_list[i];    if(hashmap_node != NULL)
{      hash_index = hashmapa_hash_func(hashmapa, hashmap_node -> hash_index);      hashmap_node -> hash_index = hash_index;      new_node_list[hash_index] =
hashmap_node;     }   free(hashmapa_node);  } hashmapa -> node_list = new_node_list;}
 
PORQUE
 
II -É preciso  tratar o problema da sobrecarga das Listas da Tabela de Espalhamento.  Assim, pode-se transformar a Tabela de Espalhamento em uma tabela
dinâmica, ou seja, em uma tabela que aumenta e diminui de tamanho conforme a necessidade do Mapa, utilizando uma função para expandir a Tabela.
A respeito dessas asserções, assinale a alternativa correta.
Alternativas:
as asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
as asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
Esse site utiliza cookies para oferecer uma melhor experiência de navegação, analisar como você interage em nosso site, otimizar o desempenho e
personalizar o conteúdo. Ao utilizar este site, você concorda com o uso de cookies. Saiba mais em nosso Portal de Privacidade
(https://www.canaldatransparencia.com.br/cogna/).
https://www.canaldatransparencia.com.br/cogna/
c)
d)
e)
a asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
a asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
as asserções I e II são proposições falsas.
Esse site utiliza cookies para oferecer uma melhor experiência de navegação, analisar como você interage em nosso site, otimizar o desempenho e
personalizar o conteúdo. Ao utilizar este site, você concorda com o uso de cookies. Saiba mais em nosso Portal de Privacidade
(https://www.canaldatransparencia.com.br/cogna/).
https://www.canaldatransparencia.com.br/cogna/