Exercícios de Fixação - Aula 6

Prévia do material em texto

ESTRUTURA DE DADOS 
6a aula 
 
 
Lupa 
 
 
 
Vídeo 
 
PPT 
 
MP3 
 
 
 
Exercício: CCT0753_EX_A6_201801039844_V1 22/05/2019 (Finaliz.) 
Aluno(a): MAIKON CARDOSO LEMOS 2019.1 EAD 
Disciplina: CCT0753 - ESTRUTURA DE DADOS 201801039844 
 
 
 
 
 1a Questão 
 
 
Quando executado, um programa tem acesso à áreas de memória. A área de memória que se destina, 
principalmente, à alocação dos registros de ativação denomina-se: 
 
 
 ( ) área de pilha 
 
( ) área de heap 
 
( ) área de código 
 
( ) área de dados 
 
( ) área de registro 
 
 
Explicação: 
Chamamos área de pilha uma espaço de memória especialmente reservado para organização de uma pilha 
de dados. Esta pilha é usada como memória auxiliar durante a execução de uma aplicação. 
As operações sobre esta área são push (empilha) e pop (desempilha). 
 
 
 
 
 
 2a Questão 
 
 
Algoritmo Pilha 
Inicio 
IniciarPilha(s) 
enquanto (não for o final das entradas) faca 
leia (num) 
se (num != 3) então 
 Empilhar (s, num) 
senão 
 Desempilhar(s) 
 x := ElementoTopo(s) 
fimse 
fimenquanto 
fimalgoritmo 
Considere que, no trecho do algoritmo acima, representado por seu pseudocódigo, seja fornecido 
para num, sucessivamente, os valores inteiros 1, 2, 3, 4, 5, 3 e 6. Nesse caso, ao final da execução do 
algoritmo, o valor de x será igual a ... 
 
 
 
3 e a pilha terá os valores 6, 4 e 1. 
 
3 e a pilha terá os valores 6, 5, 4, 2 e 1. 
 
2 e a pilha terá os valores 6, 4 e 1. 
 5 e a pilha terá os valores 6, 4 e 1. 
 
5 e a pilha terá os valores 6, 3, 5, 4, 3, 2 e 1. 
 
 
Explicação: 
Seguindo o fluxo do algoritmo, serão empilhados 1 e 2. Ao chegar no 3, o valor 2 será desempilhado e 
armazenado em x. 
Continuando o loop, 4 é mepilhado, depois 5 é empilhado e ao chegar novamente em 3, o 5 é deempilhado 
e armazenado em x. Continuando o loop enquanto existe entrada, empilha-se o 6. 
Dessa forma temos que o valor em 5 é 5 e a pilha possui os valors 6, 4 e 1, sendo 6 no topo da pilha. 
Logo, a opção correta é 5 e a pilha terá os valores 6, 4 e 1. 
 
 
 
 
 
 3a Questão 
 
 
Considere dados sendo manipulados em uma pilha sequencial em 
que as operações possíveis são: inserção - push(novo valor) ou 
remoção - pop(). 
Se realizarmos a seguinte sequencia de operações: 
push(A),push(B),push(C),pop(),pop(),push(D),pop(),pop(),pop(). 
Pode-se dizer que interior da pilha apresenta-se: 
 
 
 Apenas com o dado A 
 Vazio 
 Com os dados A e D 
 Com os dados A e B 
 Apenas com o dado D 
 
 
Gabarito 
Coment. 
 
 
 
 
 4a Questão 
 
 
Pilha é uma estrutura de dados 
 
 
 
Cujo acesso aos seus elementos ocorre de forma aleatória. 
 
Que pode ser implementada somente por meio de listas. 
 
Cujo acesso aos seus elementos segue tanto a lógica LIFO quanto a FIFO. 
 
Que pode ser implementada somente por meio de vetores. 
 Cujo acesso aos seus elementos segue a lógica LIFO. 
 
 
Explicação: 
Pilha é uma lista que segue a lógica LIFO para inserções e remoções. Pode ser implementada com vetores 
ou listas encadeadas. 
Fila é uma lista que segue a lógica FIFO. 
 
 
Gabarito 
Coment. 
 
 
 
 
 5a Questão 
 
 
Considere que existe uma rotina para inserir um valor inteiro em uma pilha de inteiros com o protótipo 
abaixo: 
 int push (int pilha[], int valor, int &topo); //retorno: 1=empilhou; 0=não empilhou 
Considere que existe uma função que remove um valor de uma pilha, que possui o protótipo abaixo: 
 int pop (int pilha[], int &valor, int &topo);//retorno: 1=desempilhou; 0=não desempilhou 
Considere ainda a execução do seguinte trecho do programa principal: 
int primeira[5], topoP=-1, segunda[5], topoS=-1, numero; 
push (primeira, 3, topoP); 
push (primeira, 5, topoP); 
pop (primeira, numero, topoP); 
push (segunda, numero, topoS); 
push (segunda, 7, topoS); 
push (primeira, 1, topoP); 
 Ao final da execução do techo de código acima, responda, nesta ordem, quantos valores haverá na 
pilha primeira, quantos valores haverá na pilha segunda, qual é o valor no topo da pilha primeira 
e qual é o valor no topo da pilha segunda. 
 
 
 
3; 2; 3; 5 
 
2; 2; 3; 5 
 
2; 1; 1; 5 
 2; 2; 1; 7 
 
1; 2; 1; 7 
 
 
Explicação: 
Empilhamos o valor 3, depois o valor 5 em primeira, ficando o valor 5 no topo da pilha. 
Ao desempilhar de primeira, numero recebeu 5 e 3 ficou no topo da pilha. 
Então, seguimos para empilhar em segunda o valor 5 e depois, o valor 7. Logo, 7 ficou no topo da pilha. 
Ao final, mais um empilhamento em primeira com o valor 2, ficando 2 no topo da pilha. 
Portanto, existem 2 valores em primeira, 2 valores em segunda, sendo que no topo de primeira existe o 
valor 1 e no topo de segunda existe o valor 7. 
 
 
 
 
 
 6a Questão 
 
 
Ao remover um elemento armazenado em uma pilha é necessário a atualização da variável (Topo) 
indicadora de posição. Qual das alternativas abaixo está correta? 
 
 
 Após a operação de remoção decrementa a variável indicadora de posição. 
 
Antes a operação de remoção decrementa a variável indicadora de posição. 
 
Após a operação de remoção incrementa a variável indicadora de inicio. 
 
Após a operação de remoção incrementa a variável indicadora de posição. 
 
Antes da operação de remoção incrementa a variável indicadora de posição. 
 
 
Gabarito 
Coment. 
 
 
 
 
 7a Questão 
 
 
Pilhas são estruturas de dados que se utilizam do algoritmo 
LIFO, last in first out, ou melhor, o último a entrar é o primeiro a 
sair. Desta forma pode-se abstrair que existe apenas um local para 
a saída e a entrada de dados, ou seja o topo da pilha. 
Supondo que uma pilha seja implementada por um vetor de 
inteiros de tamanho 10 e que exista uma variável global 
chamada topo para indexar esta posição de entrada e saída de 
dados e ainda quando esta variável assume o valor -1 indica que 
a pilha está vazia. Marque a opção que melhor ilustra a função de 
exclusão de um dado do vetor pilha, supondo ainda que o vetor 
tenha sido declarado inicialmente de forma global. 
 
 
 void pop(){ if(pilha != -1) pilha[topo-1];} 
 void pop(){ if(topo != -1) topo++;} 
 void pop(){ if(pilha != -1) pilha[topo];} 
 void pop(){ if(topo != -1) topo--;} 
 void pop(){ if(topo != -1) pilha[topo-1];} 
 
 
Gabarito 
Coment. 
 
 
 
 
 8a Questão 
 
 
Assumindo que estamos com uma estrutura de dados do tipo LIFO, as operações abaixo vão resultar em 
que elementos na mesma: PUSH(2), PUSH(3), PUSH(4), POP(), POP(), PUSH(5), PUSH(7), POP() 
 
 
 2 5 
 
5 7 
 
2 4 7 
 
2 3 4 
 
3 4 5 
 
 
Gabarito 
Coment. 
 
 
Gabarito 
Coment. 
 
 
Gabarito 
Coment.