Pular para o conteúdo principal

Exercícios Resolvidos de Estrutura de Dados 2ª Etapa.


Lista de Exercícios

1.      Dê o conceito de Pilha.
R: É uma lista linear em que todas as inserções, e retiradas e, geralmente todos os acessos são feitos em apenas um extremo da lista.

2.      Qual é o modelo utilizado?
R: O Modelo é o de um monte de pratos em uma prateleira, sendo conveniente retirar ou adicionar pratos na parte superior.

3.      Explique a disposição dos itens em uma pilha.
R: Os itens são colocados um sobre o outro.  O item inserido mais recentemente está no  topo, e o inserido menos recentemente está no fundo.

4.      Qual teoria está associada e explique o seu funcionamento associado à Pilha?
R: Esta imagem está associada com a teoria de autômato, na qual o topo de uma pilha é considerado como o receptáculo de uma cabeça de leitura/gravação que pode empilhar e desempilhar itens da pilha.

5.      Qual é sua propriedade?
R: O último item inserido é o primeiro item que pode ser retirado da lista .  São chamadas listas LIFO (“last-in, First-out).

6.      Qual a ordem utilizada?
R: Existe uma ordem linear para pilhas, do mais recente para o menos recente.

7.      Para que é ideal?
R: É ideal pra estruturas aninhadas de profundidade imprevisível.



8.      Explique sobre a seqüência de obrigações.
R: A ordem de remoção garante que as estruturas mais internas serão processadas antes das mais externas.

9.      Qual a natureza de sua estrutura?
R:  As pilhas ocorrem em estruturas de natureza recursiva(como árvores).

10.  Comente sobre os três itens de estruturas em aplicações.
R:  1ª – Quando é necessário caminhar em um conjunto de dados e guardar uma lista de coisas a fazer posteriormente.
      2ª – O controle de seqüência de chamadas de subprogramas.
      3ª – A sintaxe de expressões aritméticas.

11.  Descreva o conjunto de operações e suas finalidades.
FPVazia(pilha). Faz a pilha ficar vazia.
Vazia(Pilha). Retorna true se a pilha está vazia; caso contrário retorna false.
Empilha(x,pilha). Insere o item x no topo da pilha.
Desempilha(Pilha,x). Retorna o item x no topo da pilha, retirando-a da pilha.
Tamanho(Pilha). Essa função retorna o número de itens da pilha.

12.  Comente sobre implementação de Pilhas por meio de Arranjo.
R: Os itens da pilha são armazenados em posições contíguas de memória

13.  Quais os três itens observados para a estrutura de Pilhas com Arranjo?
* Os itens são armazenados  em um array do tamanho da pilha.
* O outro campo de mesmo registro contém um apontador para o item no topo da pilha.
* A constante MaxTam define o tamanho máximo permitido para a pilha.





14.  Escreva a estrutura de uma Pilha usando Arranjo.
#difine MaxTam 1000
typedef int TipoApontador
typedef int TipoChave
typedef struct {
TipoChave Chave;
}TipoItem;
typedef struct {
TipoItem Item;
TipoApontador Topo;
}TipoPilha;

15. Escreva as funções utilizadas por Pilhas utilizadas por Arranjo.

void FPVazia(TipoPilha _Pilha)
     { Pilha>Topo = 0; }
    int Vazia(TipoPilha Pilha)
    { return (Pilha .Topo == 0); }
    void Empilha(TipoItem x , TipoPilha _Pilha)
    { i f (Pilha>Topo == MaxTam) pr int f ( "Erro : pilha esta cheia\n" ) ;
    else { Pilha>Topo++; Pilha>Item[Pilha>Topo 1] = x ; }
    }
    void Desempilha(TipoPilha _Pilha , TipoItem _Item)
    { i f (Vazia(_Pilha ) ) pr int f ( "Erro : pilha esta vazia\n" ) ;
    else { _Item = Pilha>Item[Pilha>Topo 1]; Pilha>Topo −−; }
    }
    int Tamanho(TipoPilha Pilha)
    { return (Pilha .Topo) ; }

16.  Descreva sobre implementação de Pilhas por Apontadores.
R: Há uma célula cabeça no topo para facilitar a implementação das operações empilha e desempilha quando a pilha está fazia.

17.  Quais os três itens observados para construção de Pilhas com Apontadores?
* O campo tamanho evita a contagem do número de itens na função tamanho.
* Cada célula de uma pilha contém um item da pilha e um apontador para outra célula.
* O Registro TipoPilha contém um apontador para o topo da pilha (célula cabeça) e um apontador para o fundo da pilha.

18. Escreva a estrutura de uma Pilha por meio de Apontadores.

typedef int TipoChave;
     typedef struct {
     int Chave;
     /_ outros componentes _/
     } TipoItem;
     typedef struct TipoCelula _TipoApontador;
     typedef struct TipoCelula {
     TipoItem Item;
     TipoApontador Prox;
     } TipoCelula;
     typedef struct {
     TipoApontador Fundo, Topo;
     int Tamanho;
     } TipoPilha;

19. Escreva as funções utilizadas por Pilha com Apontadores.

void FPVazia(TipoPilha _Pilha)
{ Pilha>Topo = (TipoApontador ) malloc(sizeof(TipoCelula ) ) ;
Pilha>Fundo = Pilha>Topo;
Pilha>Topo>Prox = NULL;
Pilha>Tamanho = 0;
}
int Vazia(TipoPilha Pilha)
{ return (Pilha .Topo == Pilha .Fundo) ; }
void Empilha(TipoItem x , TipoPilha _Pilha)
{ TipoApontador Aux;
Aux = (TipoApontador ) malloc(sizeof(TipoCelula ) ) ;
Pilha>Topo>Item = x;
Aux>Prox = Pilha>Topo;
Pilha>Topo = Aux;
Pilha>Tamanho++;
}

void Desempilha(TipoPilha _Pilha , TipoItem _Item)
{ TipoApontador q;
i f (Vazia(_Pilha ) ) { pr int f ( "Erro : l ista vazia\n" ) ; return; }
q = Pilha>Topo;
Pilha>Topo = q>Prox;
_Item = q>Prox>Item;
free(q) ; Pilha>Tamanho−−;
}
int Tamanho(TipoPilha Pilha)
{ return (Pilha .Tamanho) ; }

Comentários

  1. Sabe-se que S e T são duas estruturas de dados do tipo PILHA e as operações PUSH (n) e POP() são comandos respectivos para empilhar um número "n" e desempilhar um elemento na pilha.

    Imaginando-se que ambas as pilhas, S e T, encontram-se vazias, é executada a seguinte sequência de operações:

    S.push (3);
    T.push (4);
    S.push (5);
    S.push (5);
    T.pop ();
    T.push (7);
    T.push (8);
    S.pop ();
    S.pop ();
    T.pop ();
    T.push (9);

    Ao termino de sua execução, se forem somados os valores retirados nas duas pilhas teremos como total:
    (A) 13
    (B) 17
    (C) 19
    (D) 22
    (E) 28

    Como resolvo essa questão. Alguém sabe explicar? Obrigado!

    ResponderExcluir
  2. A resposta do somatório é = 22
    seguindo a sequencia de mostrada acima quando aparece o primeiro t.pop()
    retirase o t.push(4)
    o primeiro s.pop() remove o ultimo s.´push(5), quando o s.pop() aparece novamente remove o s.push(5) que ficou la por ultimo na pilha s
    já na pilha t quando aparece novamente o t.pop() remove se o t.push(8) que até o t.pop() ser chamado é o ultimo da pliha t
    o somatório dos numero 4+5+5+8 é = ao resultado mostrado no inicio: 22

    ResponderExcluir

Postar um comentário

+ Vistas

Mais uma inovação da Google.

Sabe aqueles filmes em que um cientista possui um laboratório secreto onde faz seus experimentos mais malucos? O Google tem algo parecido, chamado "Google X". A operação foi descoberta e mostrada ao mundo neste domingo (13/11) em uma matéria do New York Times. E é de lá que podem sair duas tecnologias com potencial de mudar a forma como conhecemos os carros atualmente. De acordo com o site Electronista, uma fonte que não quis se identificar afirmou que a empresa planeja construir carros que dispensam a necessidade de motoristas. O Google os fabricaria nos EUA e os venderia para empresas locais que queiram eliminar a figura do condutor de seu quadro de funcionários. A outra invenção do Google X é relacionada à robótica. Máquinas poderiam, por exemplo, substituir os motoristas do Google Street View, encarregados de dirigir pelas cidades enquanto o sistema fotografa as ruas. Na equipe do Google X estão Sebastian Thrun, um dos maiores experts em robótica e inteligência a...

Existe uma fórmula padrão de Calculo de Estoque Mínimo e Máximo?

  Na verdade, não existe uma fórmula única e universal para calcular o estoque mínimo e máximo ideal para uma empresa de varejo, pois diversos fatores influenciam esses valores. No entanto, existem algumas fórmulas e métodos básicos que podem te ajudar a estimar esses níveis de forma eficiente, considerando as características específicas do seu negócio. Fórmula básica para o estoque mínimo: Estoque mínimo = Consumo médio diário x Tempo de reposição Essa fórmula leva em conta a quantidade média de produtos que você vende por dia e o tempo que leva para receber novos produtos do seu fornecedor. O objetivo é garantir que você tenha estoque suficiente para atender à demanda durante esse período de reposição, mesmo que haja imprevistos. Fórmula básica para o estoque máximo: Estoque máximo = Estoque médio + Lote de compra Essa fórmula considera o seu estoque médio, que é a quantidade média de produtos que você costuma ter em estoque, e o tamanho do lote de compra que você costuma fazer. ...

Instalando o plugin Java 6.20 no Google Chrome

Instalando o plugin Java 6.20 no Google Chrome Faça o download do Java nesse link:  http://www.java.com/pt_BR/download/ Use o comando abaixo para criar a pasta chamada java (você pode instalar em outro diretório. Eu prefiro instalar nesse por uma questão de organização): # mkdir /opt/java Depois mova o arquivo  jre-6u20-linux-i586.bin  para esse diretório. # cp /diretorio_do_download/ jre-6u20-linux-i586.bin /opt/java Entre no diretório e execute os comandos abaixo: # cd /opt/java # chmod +x jre-6u20-linux-i586.bin # ./jre-6u20-linux-i586.bin Após esse processo o Java já estará instalado. Agora vamos instalar o Google Chrome. Baixe o arquivo de instalação do site:  http://www.google.com.br/chrome/eula.html?platform=linux_ubuntu_i386 Entre no terminal como root e digite: # dpkg -i google-chrome-stable_current_i386.deb O Google Chrome já esta instalado! Agora siga os seguintes passos para ativar o plugins do Java no Google Chrome: Criamos a pasta "plugins" no di...