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.
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.
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.
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.
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).
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.
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.
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.
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).
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.
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.
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
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.
* 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;
#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)
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.
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.
* 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 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)
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) ; }
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.
ResponderExcluirImaginando-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!
Este comentário foi removido pelo autor.
ExcluirA resposta do somatório é = 22
ResponderExcluirseguindo 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