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

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.

Montar HD-Externo no Ubuntu Server 9.0 E 10.0

[Linux] Primeiramente para montar o HD-Externo você precisa saber o caminho dele no sistema, com o comando   fdisk -l   você pode fazer isso facilmente, veja o exemplo: //Essa primeira linha abaixo indica qual o caminho do disco e qual o tamanho total do disco em seguinte os detalhes. Disk /dev/sda: 1000.2 GB, 1000204886016 bytes 255 heads, 63 sectors/track, 121601 cylinders Units = cylinders of 16065 * 512 = 8225280 bytes Sector size (logical/physical): 512 bytes / 4096 bytes I/O size (minimum/optimal): 4096 bytes / 4096 bytes Disk identifier: 0x00052079 Device Boot Start End Blocks Id System /dev/sda1 * 1 120137 964998144 83 Linux /dev/sda2 120137 121602 11761665 5 Extended Partition 2 does not start on physical sector boundary. /dev/sda5 120137 121602 11761664 82 Linux swap / Solaris Disk /dev/sdb: 1000.2 GB, 1000204886016 bytes 255 heads, 63 sectors/track, 121601 cylinders Units = cyli...

Remover Mapeamento pelo Registro do Windows

Já aconteceram casos em que ao criar um mapeamento de uma unidade de rede, não conseguir excluí-lo pelo modo tradicional, clicando com o botão direito e desconectar. Quando isso acontecer, será possível forçar a exclusão do mapeamento pelo Registro do Windows. Acessar o Editor de Registro do Windows. 1-) Iniciar – Executar 2-) Digitar: regedit 3-) Confirmar Acessar a chave: HKEY_CURRENT_USER/Software/Microsoft/Windows/CurrentVersion/Explorer/MapNetworkDriveMRU Serão exibidos todos os mapeamentos existentes. Exclua ou altere o mapeamento desejado. REF: http://www.upware.com.br/remover-mapeamento-pelo-registro-do-windows/