ESTRUTURA DE DADOS 6º AULA

Prévia do material em texto

1.
		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 ...
	
	
	
	5 e a pilha terá os valores 6, 4 e 1.
	
	
	3 e a pilha terá os valores 6, 5, 4, 2 e 1.
	
	
	3 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.
	
	
	2 e a pilha terá os valores 6, 4 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.
	
	
	
	 
		
	
		2.
		Sobre as pilhas, marque a alternativa correta:
	
	
	
	Pilhas são estruturas de dados do tipo FIFO e permitem que os dados sejam manipulados diretamente no meio da estrutura.
	
	
	Pilhas são menos restritivas do que Listas, pois esta última impõe mais restrições às operações de inserção/remoção do que as primeiras.
	
	
	A operação de desempilhar um item de uma pilha e logo em seguida empilha-lo em outra pilha mantem a mesma ordem dos dados da primeira pilha na segunda pilha.
	
	
	A característica principal que define uma Pilha diz respeito às operações de inserção e remoção, que devem ser realizadas exclusivamente na mesma extremidade.
	
	
	Pilhas não podem ser implementadas usando vetores, pois não será possível reproduzir a inserção e remoção pela mesma extremidade.
	
Explicação:
Analisando cada item.
	
	Pilhas são estruturas de dados do tipo FIFO e permitem que os dados sejam manipulados diretamente no meio da estrutura.
	Falso. Pilha segue a lógica LIFO e as operações de inserção e remoção ocorrem apenas em uma extremidade, o topo da pilha 
	
	A operação de desempilhar um item de uma pilha e logo em seguida empilhá-lo em outra pilha mantém a mesma ordem dos dados da primeira pilha na segunda pilha.
	FAlso. Por exemplo, o elemento do topo da primeira pilha, será o 1o. elemento empilhado na 2a. pilha.  
	
	Pilhas não podem ser implementadas usando vetores, pois não será possível reproduzir a inserção e remoção pela mesma extremidade.
	Falso. É possível usar vetor ou lista encadeada para implementar pilha.
	
	Pilhas são menos restritivas do que Listas, pois esta última impõe mais restrições às operações de inserção/remoção do que as primeiras.
	FAlso. Em uma lista podemos inserir ou retirar de  qualquer posição. Em pilha, não.
	
	A característica principal que define uma Pilha diz respeito às operações de inserção e remoção, que devem ser realizadas exclusivamente na mesma extremidade.
	Vedadeiro.
	 
	
	
	
	 
		
	
		3.
		Observar os quadros abaixo e reponder o que se pede:
O que aparecerá no topo da PILHA apos os comandos do quadro II?
	
	
	
	SANTOS_AGOSTINHO
	
	
	SANTA_CATARINA
	
	
	SANTO_ESPEDITO
	
	
	SANTO_ANTONIO
	
	
	SANTA_GENOVEVA
	
Explicação:
FAzendo passo a passo...
empilha SANTO_ANTONIO e depois, SANTA_FILOMENA. Fica SANTA_FILOMENA no topo.
No item c) desempilha. Então, sai SANTA_FILOMENA da pilha.
No item d) empilha SANTO_AGOSTINHO. Então, fica SANTO_ANTONIO e logo no topo, SANTO_AGOSTINHO.
No item e) temos o elemento do topo que é SANTO_AGOSTINHO.
No item f) empilhamos SANTA_CATARINA.  Então, a sequência é SANTO_ANTONIO -> SANTO_AGOSTINHO - >SANTA_CATARINA (NO TOPO DA PILHA)
No item g, destaca-se o elemento do topo que é  SANTA_CATARINA.
No item h) empilha-se SANTO_EXPEDITO .  Então, a pilha fica assim : SANTO_ANTONIO -> SANTO_AGOSTINHO - >SANTA_CATARINA -> SANTO_EXPEDITO (este último no topo da pilha).
No item i) Desempilha-se o item do topo, ou seja, SANTO_EXPEDITO. Então, a pilha fica assim : SANTO_ANTONIO -> SANTO_AGOSTINHO - >SANTA_CATARINA
No item j) empilha-se o valor do topo . Então, a pilha fica assim : 
SANTO_ANTONIO -> SANTO_AGOSTINHO - >SANTA_CATARINA -> SANTA_CATARINA
No item k) Desempilha-se um valor e este valor é empilhado. Sai SANTA_CATARINA, mas o mesmo é empilhado. Então : 
SANTO_ANTONIO -> SANTO_AGOSTINHO - >SANTA_CATARINA -> SANTA_CATARINA (no topo)
No item l)  empilha-se SANTA_GENOVEVA. Então, a pilha fica assim : SANTO_ANTONIO -> SANTO_AGOSTINHO - >SANTA_CATARINA -> SANTA_CATARINA -> SANTA_GENOVEVA
No item m) É desempilhado SANTA_GENOVEVA. A pilha fica : SANTO_ANTONIO -> SANTO_AGOSTINHO - >SANTA_CATARINA -> SANTA_CATARINA
No item n) Pega-se o elemento do topo e o mesmo é empilhado. Então : 
ANTO_ANTONIO -> SANTO_AGOSTINHO - >SANTA_CATARINA -> SANTA_CATARINA - > SANTA_CATARINA  (no topo)
Logo, no topo da pilha temos SANTA_CATARINA
 
	
	
	
	 
		
	
		4.
		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 registro
	
	
	( ) área de código
	
	
	( ) área de dados
	
	
	( ) área de pilha
	
	
	( ) área de heap
	
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).
	
	
	
	 
		
	
		5.
		Inseriu-se em uma pilha os valores A,B,C e D, seguindo essa ordem. Se logo após são executadas duas operações de remoção, pode-se dizer que:
	
	
	
	Os valores removidos serão D e C, nessa ordem
	
	
	Os valores removidos serão A e B, nessa ordem
	
	
	A resposta depende da chave de busca, pois a remoção depende da chave fornecida
	
	
	Os valores removidos serão C e D, nessa ordem
	
	
	Nenhuma das alternativas anteriores
	
Explicação:
Inseriu-se em uma pilha os valores A,B,C e D, seguindo essa ordem.
Analisando .... Daí temos que A está na posição 0, B na posição 1, C na posição 2 e D na posição 3, ficando no topo da pilha. 
Se logo após são executadas duas operações de remoção
Analisando .... Daí temos será removido primeiro o D, que está no topo da pilha e depois será removido o C, que terá ficado no topo logo após a saída do D.
Logo, saem D e C, nesta ordem.
	
	
	
	 
		
	
		6.
		Ling Tang, estudante de computação, precisou implementar parte de um jogo de cartões com figuras de animais.  Alguns jogadores teriam que jogar os cartões na mesa, enquanto outros deveriam devolver os cartões  na sequência inversa à jogada.  Ling Tang  estudou o mecanismo do jogo e decidiu usar a melhor estrutura de dados  na sua implementação. Qual a estrutura escolhida ?
	
	
	
	fila 
	
	
	 pilha
	
	
	 árvore
	
	
	 grafo
	
	
	lista
	
Explicação:
Pelas características do problema temos uma estrutura linear.  Como menciona-se que deve-se devolver os cartões na ordem inversa à jogada, temos caracterizada a estrutura de dados pilha.  Na pilha o último elemento a entrar será o primeiro a sair.
 
 
	
	
	
	 
		
	
		7.
		As pilhas sequenciais são estruturas que guardam a ordem reversa dos dados nelas armazenados, e isto em muitas ocasiões é muito vantajoso. A operação usada para inserir um elemento X numa pilha é conhecida na literatura como PUSH (X). Para remover um elemento de uma pilha a operação é o POP( ). Assim estas duas funções devem implentar o algoritmo LIFO (Last In - First Out ) ou o último a entrar é o primeiro a sair. Sendo assim se aplicarmos as seguintes operações em uma PILHA vazia:
PUSH(10),PUSH(5),POP(),PUSH(7),POP(),PUSH(2),POP(),POP( ).
Quais valores restarão na pilha?Apenas o 10
	
	
	10 e 2
	
	
	Nenhum, a pilha estará vazia.
	
	
	Apenas o 2
	
	
	7 e 2
	
Explicação:
Empilhando e Desempilhando
PUSH(10),PUSH(5),POP(),PUSH(7),POP(),PUSH(2),POP(),POP( ).
10  PUSH(10)
5 10 PUSH(5), PUSH(10)
10 POP() PUSH(10)
7 10 PUSH(7) PUSH(10)
10 POP() PUSH(10)
2 10 PUSH(11)PUSH(10)
10  POP() PUSH(10)
  POP() VAZIA Resposta CORRETA
		
	Gabarito
Comentado
	
	
	
	
	 
		
	
		8.
		Respeitando as ordens de inserção e de retirada dos dados, uma estrutura de:
	
	
	
	fila é também denominada LIFO ou LILO.
	
	
	pilha é também denominada FIFO ou FILO.
	
	
	pilha é também denominada LIFO ou FILO.
	
	
	fila é também denominada FIFO ou FILO.
	
	
	fila é também denominada FIFO ou LIFO.