Trabalho_Academico(AV1)_EstruturaDeDados_2021_1

Prévia do material em texto

Estrutura de Dados – 2021.1
 TRABALHO ACADÊMICO (AV1)
Instruções:
1) é obrigatório usar a folha de respostas modelo que está disponível no AVA no Card
Espaço para AV1;
2) é obrigatório apresentar o desenvolvimento ou justificativa de todas as questões;
3) colocar o nome e a matrícula de todos os componentes do grupo;
4) é obrigatório que a folha de resposta esteja no formato PDF para o envio;
5) caso necessário, assistir o vídeo “Instruções para realizar e enviar o Trabalho
Acadêmico da AV1”, que está no AVA no Card Espaço para AV1.
Questão 01 (2.0 ponto)
“O estudo das estruturas de dados envolve duas metas complementares. A primeira meta é
identificar e desenvolver entidades e operações matemáticas úteis e determinar que classes
de problemas podem ser solucionadas, usando essas entidades e operações. A segunda
meta é determinar representações para essas entidades abstratas e implementar as
operações abstratas sobre essas representações concretas.”
No texto acima, a primeira meta se refere ao conceito TAD (tipo abstrato de dados). Com
base neste texto e no que foi estudado em aula especifique um TAD Cliente. Dica: pense
em dados e operações que fazem sentido, ou seja, que se espera que um TAD Cliente
tenha.
Questão 02 (2.0 ponto)
Um lista linear é um conjunto de n >= 0 nós (elementos) L[1], L[2], ..., L[n] tais que suas
propriedades estruturais decorrem, unicamente da posição relativa dos nós dentro da
sequência linear. Tem–se:
- se n>0, L[1] é o primeiro nó;
- para 1 < k <= n, o nó L[k] é precedido por por L[k-1].
Dentre as listas lineares encontramos a Lista Linear Sequencial. Nesse tipo de lista a
alocação da memória é feita de forma sequencial em posições contíguas de memória
(posições de memória que estão em sequência). Dessa forma, esse tipo de lista apresenta
vantagens e desvantagens. Com base nessas informações:
a) O que é alocação estática de memória?
b) Cite uma situação em que é aconselhável usar na implementação uma Lista Linear
Sequencial ao invés de uma Lista Linear Encadeada.
Prof. Lincoln Faria - lfaria@unicarioca.edu.br
Questão 03 (2.0 ponto)
Uma lista encadeada é uma coleção linear de objetos (elementos) de uma uma classe
autorreferenciada, chamados de nós, conectados por links de ponteiros – daí o termo lista
“encadeada”. As listas encadeadas são caracterizadas por serem implementas por alocação
dinâmica de memória. Com base nessas informações:
a) O que é alocação dinâmica de memória?
b) Cite uma desvantagem das Listas Lineares Encadeadas, sobre as Listas Lineares
Sequenciais.
c) Cite uma situação em que é aconselhável usar na implementação uma Lista Linear
Encadeada ao invés de uma Lista Linear Sequencial.
Questão 04 (2.0 ponto)
As listas lineares, como outras estruturas de dados, possuem como principais operações a
inserção, a remoção e a busca de elementos. Entretanto, dependendo da política de acesso
a uma lista linear, ou seja, dependendo das restrições sobre as inserções e remoções de
dados, tal lista pode ser conhecida como ou uma fila, ou uma pilha, ou um deque.
Um exemplo computacional que pode ser implementado com o uso de uma estrutura de
dados do tipo FILA é o seguinte: 
(Exemplo 1) “Os sistemas computacionais geralmente devem fornecer uma “área de
espera” para mensagens entre dois processos ou programas internos, ou entre dois sistemas
em uma rede. Essa área de retenção é normalmente chamada de “buffer” e é
frequentemente implementada como uma fila, porque queremos que a ordem de tempo de
espera da mensagem seja mantida como em uma fila de pessoas em um banco, onde a
última pessoa a chegar é a última a ser atendida.”
Um exemplo computacional que pode ser implementado com o uso de uma estrutura de
dados do tipo PILHA é o seguinte:
(Exemplo 2) “Os navegadores de internet, tais como Chrome e FireFox, possuem um
botão (o botão voltar (←)) que permite ao usuário retornar à página anteriormente visitada.
Se o usuário clicar várias vezes nesse botão, ele retornará às últimas páginas visitadas em
ordem cronologicamente inversa, ou seja, as primeiras páginas que foram visitadas serão
as últimas retornadas. As informações cronológicas das páginas (sites) visitadas são
armazenadas em uma pilha, de forma que quando o botão voltar é acionado, o elemento (a
informação) no topo dessa pilha é recuperado, conduzindo o usuário para a última página
anteriormente visitada.”
a) Observando o Exemplo 1 citado acima, cite um outro exemplo de aplicação
computacional onde a implementação requer o uso de uma estrutura de dados do tipo
FILA.
b) Observando o Exemplo 2 citado acima, cite um exemplo de aplicação computacional
onde a implementação requer o uso de uma estrutura de dados do tipo PILHA.
Prof. Lincoln Faria - lfaria@unicarioca.edu.br