Pular para o conteúdo principal

Exercícios De Estrutura de Dados Resolvidos.


Por Ariadne Costa Gomes

1.      Para que serve uma lista? 
  Uma lista serve para interligar os elementos de um conjunto.
2.      Quais operações podem ser realizadas com uma lista?
Podem ser realizadas com uma lista as seguintes operações: Inserir, Retirar e Localizar.
3.      Descreva sua facilidade durante a execução de um programa.
As listas são estruturas muito flexíveis, porque podem crescer sem diminuir de tamanho durante a execução de um programa, de acordo com a demanda.
4.      Como podem ser as operações com os itens na lista?
Itens podem ser acenados, inseridos ou retirados de uma lista.
5.      O que pode ser feito com uma lista muito grande ou duas listas pequenas?
Duas listas podem ser concatenadas para formar uma lista única, assim como uma lista pode ser partida em duas ou mais listas.
6.      Quando é aconselhável o seu uso?
Listas são adequadas para aplicações nas quais não é possível prever a demanda por memória, permitindo a manipulação de quantidades imprevisíveis de dados, de formato também imprevisível.
7.      Em que são úteis às listas?
Listas são úteis em aplicações tais como manipulação simbólica, gerência de memória, simulação e compiladores.
8.      Como é feita a definição em uma lista?
Uma lista linear é uma sequência de zero ou mais itens, x1, x2....,xn, na qual x1 é de um determinado item e xn representa o tamanho da lista linear.
9.      Descreva sua propriedade principal:
Sua principal propriedade estrutural envolve as posições relativas dos itens em uma dimensão. Assumindo n>=1, x1 é o primeiro item da lista e xn é o último item da lista.
– xi precede xi+1 para i = 1, 2, · · · , n − 1
– xi sucede xi−1 para i = 2, 3, · · · , n
– o elemento xi é dito estar na i-ésima posição da lista.
10.   Das várias estruturas que podem ser utilizadas, quais estudamos?
Listas Lineares.
11.   Descreva sobre os cinco pontos relacionados à implementação de uma lista.
1. FLVazia(Lista). Faz a lista ficar vazia.
2. Insere(x, Lista). Insere x após o último item da lista.
3. Retira(p, Lista, x). Retorna o item x que está na posição p da lista,
retirando-o da lista e deslocando os itens a partir da posição p+1
para as posições anteriores.
4. Vazia(Lista). Esta função retorna true se lista vazia; senão retorna
false.
5. Imprime(Lista). Imprime os itens da lista na ordem de ocorrência.
12.   Escreva a estrutura necessária para implementação de uma lista com arranjo.
Os itens são armazenados em
um array de tamanho suficiente
para armazenar a lista.
• O campo Último aponta para a
posição seguinte a do último ele-
mento da lista.
• O i-ésimo item da lista está arma-
zenado na i-ésima posição do ar-
ray, 1 ≤ i <Último.
• A constante MaxTam define o ta-
manho máximo permitido para a
lista.

13.  Escreva as funções utilizadas para operar sobre a lista.
void FLVazia(TipoLista Lista)
{ Lista−>Primeiro = INICIOARRANJO; Lista−>Ultimo = Lista−>Primeiro ; }
int Vazia(TipoLista Lista)
{ return ( Lista .Primeiro == Lista .Ultimo ) ; } / Vazia /
void Insere(TipoItem x , TipoLista Lista)
{ i f ( Lista −> Ultimo > MAXTAM)
pr int f ( "Lista esta cheia\n" ) ;
else { Lista −> Item[ Lista −> Ultimo − 1] = x;
Lista −> Ultimo++;
}
} / Insere /
void Retira(TipoApontador p, TipoLista Lista , TipoItem Item)
{ int Aux;
i f (Vazia(Lista ) | | p >= Lista > Ultimo)
{ pr int f ( "Erro : Posicao nao existe \n" ) ;
return;
} Item = Lista −> Item[p − 1];
Lista −> Ultimo−−;
for (Aux = p; Aux < Lista −> Ultimo ; Aux++)
Lista −> Item[Aux − 1] = Lista −> Item[Aux] ;
} / Retira /
void Imprime(TipoLista Lista)
{ int Aux;
for (Aux = Lista .Primeiro − 1; Aux <= (Lista .Ultimo − 2); Aux++)
pr int f ( "%d\n" , Lista . Item[Aux] .Chave) ;
} / Imprime /
14.  Escreva as vantagens de utilizar listas com arranjos.
Economia de memória (os apontadores são implícitos
nesta estrutura).
15.  Escreva as desvantagens de utilizar listas com arranjos.
– custo para inserir ou retirar itens da lista, que pode causar um
deslocamento de todos os itens, no pior caso;
– em aplicações em que não existe previsão sobre o crescimento da
lista, a utilização de arranjos em linguagens como o Pascal pode
ser problemática porque nesse caso o tamanho máximo da lista
tem de ser definido em tempo de compilação.
16.  Descreva a implementação de listas com apontadores.
• Cada item é encadeado com o seguinte mediante uma variável do tipo
Apontador.
• Permite utilizar posições não contíguas de memória.
• É possível inserir e retirar elementos sem necessidade de deslocar os
itens seguintes da lista.
• Há uma célula cabeça para simplificar as operações sobre a lista.
17.  Escreva as estruturas necessárias para implementar listas com apontadores.


typedef int TipoChave;
typedef struct {
TipoChave Chave;
/ outros componentes /
} TipoItem;
typedef struct TipoCelula TipoApontador ;
typedef struct TipoCelula {
TipoItem Item;
TipoApontador Prox;
} TipoCelula;
typedef struct {
TipoApontador Primeiro , Ultimo;
} TipoLista;
• A lista é constituída de células.
• Cada célula contém um item da
lista e um apontador para a cé-
lula seguinte.
• O registro TipoLista contém um
apontador para a célula cabeça
e um apontador para a última cé-
lula da lista.


18.  Escreva as funções necessárias para trabalha com listas utilizando apontadores.
void FLVazia(TipoLista Lista)
{ Lista−>Primeiro = (TipoApontador ) malloc(sizeof (TipoCelula ) ) ;
Lista−>Ultimo = Lista−>Primeiro ; Lista−>Primeiro−>Prox = NULL;
}
int Vazia(TipoLista Lista)
{ return ( Lista .Primeiro == Lista .Ultimo ) ; }
void Insere(TipoItem x , TipoLista Lista)
{ Lista−>Ultimo−>Prox = (TipoApontador ) malloc(sizeof (TipoCelula ) ) ;
Lista−>Ultimo = Lista−>Ultimo−>Prox; Lista−>Ultimo−>Item = x;
Lista−>Ultimo−>Prox = NULL;
}
void Retira(TipoApontador p, TipoLista Lista , TipoItem Item)
{ /−−O item a ser retirado e o seguinte ao apontado por p−−/
TipoApontador q;
i f (Vazia(Lista ) | | p == NULL | | p>Prox == NULL)
{ pr int f ( " Erro : Lista vazia ou posicao nao existe \n" ) ;
return;
}
q = p−>Prox; Item = q>Item; p>Prox = q>Prox;
i f (p−>Prox == NULL) Lista−>Ultimo = p;
free(q) ;
}
void Imprime(TipoLista Lista)
{ TipoApontador Aux;
Aux = Lista .Primeiro−>Prox;
while (Aux != NULL)
{ pr int f ( "%d\n" , Aux −>Item.Chave) ; Aux = Aux −>Prox ; }
}
19.  Quais as vantagens de utilizar listas com apontadores?
– Permite inserir ou retirar itens do meio da lista a um custo constante
(importante quando a lista tem de ser mantida em ordem).
– Bom para aplicações em que não existe previsão sobre o
crescimento da lista (o tamanho máximo da lista não precisa ser
definido a priori).
20.  Qual a desvantagem de utilizar listas com apontadores?
Utilização de memória extra para armazenar os apontadores.

Comentários

+ Vistas

Exercícios Estrutura de Dados - Resolvidos

Lista de Exercícios Dê o conceito de: Algoritmo R: É uma sequencia de ações executáveis para obtenção de uma solução para um determinado problema. Tipo de dados R: Conjunto de valores a que uma constante pertence, ou podem ser assumidos por uma variável ou expressão a que podem ser gerados por uma função. Tipo abstrato de dados R: Pode ser visto como um modelo matemático, acompanhado das operações definidas sobre um modelo. Qual a descrição de algoritmos segundo Dijkstra? R: descreve como uma descrição de um padrão de comportamento, expresso em termos de um conjunto finito de ações. Descreva o conceito de programar para estrutura de dados. R: consiste em estruturar dados e construir algoritmos, sendo formulações concretas de algoritmos abstratos, baseados em representações e estruturas específicas de dados, representando uma classe especial de algoritmos capazes de serem seguidos por computadores Cite os tipos de ope...

O PVA NÃO FUNCIONA COM O JAVA 7 (RESOLVIDO)

Eu encontrei um problema na hora de instalar o PVA do Sped ICMS e SPED Contribuições, pois o java não executava a aplicação corretamente, ele apresentava um erro <JAVA HOME>. Mais eis a solução para o problema: Baixe o arquivo Jdk1.6.0_20   Download Jdk1.6.0_20   depois descompacte o mesmo e copie a pasta que foi gerada com a descompactação para a pasta java C:\Program Files (x86)\Java "isso windows 7 64bits" no XP é normal. Vualá, pode instalar os PVA's que vai funcionar que uma beleza. Espero que tenha ajudado.

Baixar Debian Lenny 6.0.7 Full + Updates

Debian  é simultaneamente o nome de uma distribuição não comercial livre (gratuita e de  código fonte aberto ) de  GNU / Linux (amplamente utilizada) e de um grupo de voluntários que o mantêm à volta do mundo. Uma vez que o Debian se baseia fortemente no projecto GNU, é usualmente chamado  Debian GNU/Linux . O Debian é especialmente conhecido pelo seu sistema de gestão de pacotes, chamado  APT , que permite: atualizações relativamente fáceis a partir de versões realmente antigas; instalações quase sem esforço de novos pacotes e remoções limpas dos pacotes antigos. Atualmente o Debian Stable se encontra na versão 7.0, codinome "Wheezy". O Debian Stable procura sempre manter os pacotes mais estáveis, assim, ele mantém o Gnome 3 e o KDE 4.4 por padrão. O fato dele conter pacotes mais antigos, garantindo a estabilidade, é o grande foco para servidores. O projecto Debian é mantido por doações através da organização sem fins lucrativos  Software in the Publi...