Colaborar - Av2 - Algoritmos e Estrutura de Dados

Prévia do material em texto

1) Conforme Celes, Cerqueira, Rangel (2004), tanto na função de Cálculo de endereços, como na
função de Divisão, ao inserirmos um elemento na tabela e este elemento colide com outro elemento no endereço de índice, o elemento a ser inserido é armazenado no próximo índice disponível de própria tabela.
Apresenta-se abaixo uma tabela de 10 posições e a seguinte sequência de chaves: 18, 77, 548, 195, 174, já inserida na tabela.
	Chave
	Cálculo da Função
	Endereço
	18
	(18 mod 10)
	8
	77
	(77 mod 10)
	7
	548
	(548 mod 10)
	8
	195
	(195 mod 10)
	5
	174
	(174 mod 10)
	4
Diante da tabela apresentada acima e o tratamento em caso de colisão, escolha a Tabela de Espelhamento que representa os corretamente os dados apresentados.
Alternativas:
índice	0	1	2	3	4	5	6	7	8	9
02/11/2023 18:17
Colaborar - Av2 - Algoritmos e Estrutura de Dados
https://www.colaboraread.com.br/aluno/avaliacao/index/3671177301?atividadeDisciplinaId=15057424
1/7
a)valor
174
195
77
18
548
índice
0
1
2
3
4
5
6
7
8
9
valor
18
77
548
195
174
índice
0
1
2
3
4
5
6
7
8
9
b)
c) valor
174 195 548
18	77
d) índice	0 valor
1	2	3
174
4	5
195
6	7
77 18
8	9
548
Alternativa assinalada
índice	0	1	2	3	4	5	6	7	8	9
e) valor
174
195
77 548
2) Segundo Silva (2007), na função linear, também conhecido como Overflow Progressivo, consiste em procurar a próxima posição vazia depois do índice-base da chave. É uma função que possui como vantagem a simplicidade em definir o índice da Tabela de Espalhamento. No entanto, sua desvantagem está no caso de ocorrerem muitas colisões, pode ocorrer um agrupamento (clustering) de chaves em um determinado índice. Isso pode fazer com que sejam necessários muitos acessos para recuperar um determinado elemento.
Pode-se observar o esquema de Função de Espalhamento Linear, utilizando o método de divisão para encontrar o índice. Abaixo encontramos um exemplo da Função de Espalhamento Linear.
Obs. as posições sem alocação de elementos são identificados com -1 (menos um).
Sobre a Função de Espalhamento Linear e utilizando o método de divisão para encontrar o índice analise as afirmações abaixo.
I - Se utilizarmos a tabela apresentada e inserirmos o elemento 24, o índice onde ele será inserido será o 1.
II - Se utilizarmos a tabela apresentada e inserirmos o elemento 24 e logo em seguida o elemento 40, os índices onde eles serão inseridos são o 1 e o 2 respectivamente.
III - Se utilizarmos a tabela apresentada e inserirmos o elemento 24, depois o 40 e logo em seguida o elemento 48, os índices onde eles serão inseridos são o 1, 2 e 6 respectivamente.
IV - Se utilizarmos a tabela apresentada e inserirmos o elemento 23, o índice onde ele será inserido será o 6.
Agora, assinale a alternativa que apresenta a correta: Agora assinale a alternativa correta.
Alternativas:
a) Apenas a afirmativa IV está correta.
b) Apenas as afirmativas I e IV estão corretas.
c) Apenas as afirmativas II e III estão corretas.
d) Apenas as afirmativas I, II e III estão corretas.Alternativa assinalada
e) Apenas as afirmativas I, II, III e IV estão corretas.
3) Uma Tabela de Espalhamento pode ter seu desempenho comprometido à medida que ela vai
ficando cheia. Enquanto ela possui poucos elementos, a busca é muito eficiente e rápida para qualquer tipo de Função de Espalhamento adotada.
O desempenho da tabela diminui devido à falta de posições disponíveis, ocasionando o problema lentidão e uma solução seria necessário aumentar a tabela e reinserir todos os elementos novamente, operação ineficiente para ser executada. Considerando o contexto apresentado, avalie as seguintes asserções e a relação proposta entre elas.
I - Como forma de melhorar a performance de uma Função de Espalhamento, Luiz sugeriu a implementação da tabela dinâmica na Função de Espalhamento conforme o código abaixo:
int insere_nova(item chave) { int i = espalha(chave, NN);
/* Busca a próxima posição livre */
/* Com a tabela duplicada, sempre haverá posição disponível */ while (q[ i ] != VAZIO) {
i = (i+1) % NN; /* Cálcula o índice */
}
/* Insere na posição livre encontrada */ q[ i ] = chave;
return i;
}
void expande() {
int i, NN = 2*N;
q = malloc(NN*sizeof(item)); 12
limpa(q, NN);
/* Insere todos os elementos na nova tabela */ for (i = 0; i < N; i++)
if (p[ i ] != VAZIO)
insere_nova(p[ i ]); N = NN;
free(p); p = q;
}
void insere(item chave) { int i;
//Verifica se o tamanho da tabela é menor que a soma da quantidade de elementos da tabela if (N < M+M)
expande(); /* Chama a função para expandir a tabela */ i = espalha(chave, N);
/* Busca a próxima posição livre */ while (p[ i ] != VAZIO) {
if (p[ i ] == chave)
return –1; /* Retorna se o elemento já existe na tabela */ i = (i+1) % N; /* Calcula o índice */
}
/* Insere na posição livre encontrada */ p[ i ] = chave;
M++;
return i;
}
PORQUE
II - Para melhorar o espalhamento, uma solução é a utilização de tabelas dinâmicas na estrutura ao invés de utilizar uma Lista Ligada para armazenar os valores, podendo ser utilizada tanto com a Função de Espalhamento Linear, como com a Função de Espalhamento Duplo. Assim, quando utilizamos este método, no momento em que a tabela passa de N/2 elementos, dobramos o seu tamanho, fazendo com que a tabela sempre tenha menos da metade dos elementos ocupados.
A respeito dessas asserções, assinale a alternativa correta.
Alternativas:
a) As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
b) As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.Alternativa assinalada
c) A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
d) A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
e) As asserções I e II são proposições falsas.
4) Conforme Pereira (2008), 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.
Os Mapas Associativos são estruturas de dados que permitem implementarmos as seguintes funcionalidades apresentadas na Coluna 1. Na Coluna 2 são apresentados seus respectivos exemplos de código.
Coluna 1
I - Adicionar uma associação.
II - Remover uma associação de uma chave especifica.
III - Verificar se existe uma associação para uma determinada chave. IV - Informar a quantidade de associações na estrutura.
Coluna 2
Código 01
#include <iostream> /* Utiliza a biblioteca iostream da linguagem C++ */ #include <map> /* Utiliza a biblioteca map da linguagem C++ */
using namespace std; /* Este comando serve para definir um espaço de nome para evitar duplicidade
*/
int main ()
{
map <int, string > mapa; /* Definimos a estrutura do mapa com associação entre um número inteiro e	uma string */
mapa[1] = "KLS";
cout << mapa[1] << endl; return 0;
}
Código 02
#include <iostream> #include <map> using namespace std; int main ()
{
map <int, string> mapa; mapa[1] = "KLS";
cout << mapa[1] << endl; mapa.erase(1);
cout << mapa[1] << endl; return 0;
}
Código 03
#include <iostream> #include <map> using namespace std; int main ()
{
int chave;
map <int, string> mapa; mapa[1] = "KLS"; mapa[2] = "KROTON";
mapa[3] = "ESTRUTURA DE DADOS";
printf("Digite a chave: \n"); scanf("%d",&chave); if(mapa.find(chave) == mapa.end())
cout << "\nChave NAO existe!\n\n";
else
cout << "\nChave existe! - Valor: " + mapa[chave] + "\n\n"; return 0;
}
Código 04
#include <iostream> #include <map> using namespace std; int main ()
{
int chave;
map <int, string> mapa; mapa[1] = "KLS"; mapa[2] = "KROTON";
mapa[3] = "ESTRUTURA DE DADOS";
cout << "Tamanho da estrutura de Mapa: " << mapa.size() << endl; return 0;
}
Assinale a alternativa que contém a sequência correta da associação entre as colunas.
Alternativas:
a) Código 01 é associado a funcionalidade II -	Código 02 é associado a funcionalidade I - Código 03 é associado a funcionalidade IV -	Código 04 é associado a funcionalidade III.
b) Código 01 é associadoa funcionalidade IV -	Código 02 é associado a funcionalidade II - Código 03 é associado a funcionalidade III -	Código 04 é associado a funcionalidade I.
c) Código 01 é associado a funcionalidade IV -	Código 02 é associado a funcionalidade III - Código 03 é associado a funcionalidade II -	Código 04 é associado a funcionalidade I.
Código 01 é associado a funcionalidade I -	Código 02 é associado aAlternativa assinalada
d) funcionalidade II - Código 03 é associado a funcionalidade III -	Código 04 é associado a funcionalidade IV.
e) Código 01 é associado a funcionalidade II -	Código 02 é associado a funcionalidade III - Código 03 é associado a funcionalidade IV -	Código 04 é associado a funcionalidade I.
5) Para adicionar uma associação no Mapa é necessário verificar se a chave da nova associação não pertence a alguma associação da Lista e para isso precisamos verificar se a chave já existe na estrutura. Para remover uma associação no mapeamento, também é necessário verificar se uma chave está associada a algum elemento ou recuperar o elemento associado, sendo necessário percorrer a Lista para verificar a existência.
Analise os trechos de código apresentados na COLUNA 1 e suas respectivas funções na COLUNA 2.
COLUNA 1
Código 01
#include <iostream> #include <map>
using namespace std; struct Materias{ string codigo;
string disciplina;
};
Código 02
printf("Informe a chave para receber a ação: "); scanf("%d", &chave);
if(MapaLista.find(chave) == MapaLista.end())
{
cout << "Chave nao existente!\n" << endl;
} else
{
MapaLista.erase(MapaLista.find(chave));
}
Código 03
printf("Informe a chave para receber a ação: "); scanf("%d", &chave);
if(MapaLista.find(chave) == MapaLista.end())
{
cout << "Chavenao encontrada!\n" << endl;
} else {
cout	<<	"Chave	Encontrada!\nCodigo:	"	+	MapaLista[chave].codigo	+	"\nChave:	"	+ MapaLista[chave].disciplina + "\n" << endl;
}
Código 04
printf("Informe o codigo da disciplina: "); scanf("%s", &coddisc);
for (i = 1; i <= MapaLista.size(); i++)
{
printf("Posicao %d: ", i);
if(MapaLista[i].codigo == coddisc)
cout	<<	"Disciplina	Encontrada!\nCodigo:	"	+	MapaLista[i].codigo	+	"\n	Disciplina:	"	+ MapaLista[i].disciplina + "\n" << endl;
else
cout << "Disciplina nao encontrada!\n" << endl;
}
COLUNA 2
I - Implementação da remoção da associação com base na chave informada pelo usuário II - Recuperação de valores associados a chaves em um mapeamento com listas
III - Pesquisa de elementos em um mapeamento, realizando a pesquisa por meio do código da disciplina
IV - Declaração das bibliotecas e da estrutura da Lista
Assinale a alternativa que contém a sequência correta da associação entre as colunas.
Alternativas:
a) Código 01 é a função I ; Código 02 é a função II ; Código 03 é a função III ; Código 04 é a
função IV ;
b) Código 01 é a função IV ; Código 02 é a função III ; Código 03 é a função II ; Código 04 é a
função I ;
c) Código 01 é a função IV ; Código 02 é a função I ; Código 03 é a função II ;
Código 04 é a função III ;
d) Código 01 é a função IV ; Código 02 é a função I ; Código 03 é a função III ; Código 04 é a
função II ;
e) Código 01 é a função I ; Código 02 é a função IV ; Código 03 é a função II ; Código 04 é a função
III ;
Alternativa assinalada