ESTRUTURA_LISTA_06(1)

Prévia do material em texto

ESTRUTURA DE DADOS 
LISTA DE EXERCÍCIOS-06 
FILAS E PILHAS 
ESTRUTURA-LISTA-06 MANUEL 
 
1 
 
01- Mostre a situação de uma fila F, inicialmente vazia, após a execução de cada 
uma das seguintes operações: 
Enqueue(F, a); 
Enqueue(F, b); 
Enqueue(F, c); 
Enqueue(F, d); 
Dequeue(F); 
Dequeue(F); 
Enqueue(F, e); 
Dequeue(F); 
Enqueue(F, f); 
Dequeue(F); 
Enqueue(F, g); 
Enqueue(F, Dequeue(F)); 
 
02- Insira os dados de entrada numa FILA. Em seguida retire cada dado da FILA e 
insira numa PILHA. Mostre a PILHA. Depois retire os dados da PILHA e insira na 
FILA. Mostre a FILA. 
Dados de entrada: 11, 12, 23, 14, 25, 50, 8, 18, 29, 10 
As estruturas mostradas ficam: 
I. Pilha: (topo) 10 - 29 - 18 - 8 - 50 - 25 - 14 - 23 - 12 - 11 
II. Fila: (começo) 11 - 12 - 23 - 14 - 25 - 50 - 8 - 18 - 29 - 10 (fim) 
III. Fila: (começo) 10 - 29 - 18 - 8 - 50 - 25 - 14 - 23 - 12 - 11 (fim) 
IV. Pilha: (topo) 11 - 12 - 23 - 14 - 25 - 50 - 8 - 18 - 29 - 10 
V. A fila mostrada fica com os elementos em ordem invertida dos dados de entrada 
Está correto o que se afirma APENAS em 
(A) III e IV. 
(B) II e IV. 
(C) I, II e III. 
(D) I, III e V. 
(E) I, IV e V. 
 
ESTRUTURA DE DADOS 
LISTA DE EXERCÍCIOS-06 
FILAS E PILHAS 
ESTRUTURA-LISTA-06 MANUEL 
 
2 
03- A melhor definição para a estrutura de dados chamada FILA é(são): 
A) É uma estrutura de dados linear, que também pode ser linear e dinâmica. É 
composta por nós que apontam para o próximo elemento. 
B) São estruturas baseadas no princípio FIFO (first in, first out), em que os 
elementos que foram inseridos no início são os primeiros a serem removidos. 
C) São estruturas baseadas no princípio LIFO (last in, first out), na qual os dados 
que foram inseridos por último na pilha serão os primeiros a serem removidos. 
D) É uma estrutura de dados em que cada elemento tem um ou mais elementos 
associados. 
E) São estruturas de dados lineares e estáticas, isto é, são compostas por um 
número fixo (finito) de elementos de um determinado tipo de dados. O tempo de 
acesso aos elementos é muito rápido, porém, a remoção de elementos pode ser 
custosa se não for desejável que haja espaços "vazios" no meio da estrutura. 
 
04- Uma fila duplamente terminada, isto é, uma estrutura linear que permite inserir e 
remover de ambos os extremos é chamada: 
 a) Árvore. 
 b) Shift-and. 
 c) Autômato. 
 d) Deque. 
 e) Boyer-Moore. 
 
05- Assinale a opção correta relativa às operações básicas suportadas por pilhas. 
a) Push: insere um novo elemento no final da pilha. 
b) Pop: adiciona elementos ao topo da pilha. 
c) Pull: insere um novo elemento no interior da pilha. 
d) Top: transfere o último elemento para o topo da pilha. 
e) Top: acessa o elemento posicionado no topo da pilha. 
 
 
 
 
ESTRUTURA DE DADOS 
LISTA DE EXERCÍCIOS-06 
FILAS E PILHAS 
ESTRUTURA-LISTA-06 MANUEL 
 
3 
06- Observe os quadros I e II, relacionados à estrutura de dados pilha. 
 
QUADRO I – operações permitidas pela estrutura de dados pilha 
 
OPERAÇÃO DESCRIÇÃO 
Push(PILHA,w) Insere um elemento w na Pilha 
Pop(PILHA) Retira o elemento do topo da pilha 
Top(PILHA) Acessa sem remover o elemento do topo da pilha 
 
 
QUADRO-II – operações realizadas 
 
a) PUSH (P, S_ANTÔNIO) 
b) PUSH (P, S_FILOMENA) 
c) POP(P) 
d) PUSH (P, S_AGOSTINHO) 
e) TOP(P) 
f) PUSH (P, S_CATARINA) 
g) TOP(P) 
h) PUSH (P, S_EXPEDITO) 
i) POP(P) 
j) PUSH(P, TOP(P) ) 
k) PUSH(P, POP(P) ) 
l) PUSH (P, S_GENOVEVA) 
m) POP(P) 
n) PUSH(P, TOP(P) ) 
 
 
Após a execução de todas as operações indicadas no quadro II, o elemento de topo 
da pilha será igual a: 
 
A) S_CATARINA 
B) S_EXPEDITO 
C) S_GENOVEVA 
D) S_FILOMENA 
E) S_AGOSTINHO 
 
ESTRUTURA DE DADOS 
LISTA DE EXERCÍCIOS-06 
FILAS E PILHAS 
ESTRUTURA-LISTA-06 MANUEL 
 
4 
07- Os algoritmos abaixo apresentam uma versão muito simples de uma estrutura de 
dados conhecida. Para isso, é utilizado um vetor e não há preocupações com 
possíveis erros de operação ou de limites ultrapassados. 
 
VETOR[1..MÁXIMO] É UM VETOR DE NÚMEROS 
TOPO É UM NÚMERO INTEIRO COM VALOR INICIAL 0 
TEMP É UM NÚMERO INTEIRO COM VALOR INICIAL 0 
 
FUNÇÃO COLOCA(ENTRADA : NÚMERO) NÃO RETORNA VALOR 
 TOPO:=TOPO+1 
 VETOR[TOPO]:=ENTRADA 
FIM 
 
FUNÇÃO RETIRA() RETORNA NÚMERO 
 TEMP := VETOR[TOPO] 
 TOPO:=TOPO-1 
 RETORNA TEMP 
FIM 
 
Qual a denominação da estrutura de dados implementada? 
(A) Árvore binária 
(B) Fila 
(C) Lista encadeada 
(D) Pilha 
(E) Registro 
 
 
 
ESTRUTURA DE DADOS 
LISTA DE EXERCÍCIOS-06 
FILAS E PILHAS 
ESTRUTURA-LISTA-06 MANUEL 
 
5 
08- Considere o algoritmo abaixo. 
Algoritmo Pilha 
... 
Inicio 
IniciarPilha(s) 
enquanto (não for o final das entradas) faca 
leia num 
se (num <> 3) 
entao Empilhar(s, num) 
senao Desempilhar(s) 
 x  ElementoTopo(s) 
fim-se 
fim-enquanto 
Fim-Algoritmo 
Considere que, no trecho do programa 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 programa, o valor de x será igual a 
A) 2 e a pilha terá os valores 6, 4 e 1. 
B) 3 e a pilha terá os valores 6, 4 e 1. 
C) 5 e a pilha terá os valores 6, 4 e 1. 
D) 3 e a pilha terá os valores 6, 5, 4, 2 e 1. 
E) 5 e a pilha terá os valores 6, 3, 5, 4, 3, 2 e 1. 
 
09- Pilha é uma estrutura de dados 
(A) cujo acesso aos seus elementos segue tanto a lógica LIFO quanto a FIFO. 
(B) cujo acesso aos seus elementos ocorre de forma aleatória. 
(C) que pode ser implementada somente por meio de vetores. 
(D) que pode ser implementada somente por meio de listas. 
(E) cujo acesso aos seus elementos segue a lógica LIFO, apenas. 
 
10- O almoxarife de um órgão pediu ao técnico de informática que elaborasse um 
sistema de custeio que, para cada saída de material, considerasse o custo do mais 
recente que houvera dado entrada no almoxarifado. O técnico deve desenvolver um 
algoritmo para tratar com uma estrutura de dados do tipo: 
(A) FIFO. (B) TABLE. (C) LIFO. (D) HEAP. (E) ARRAY. 
 
 
ESTRUTURA DE DADOS 
LISTA DE EXERCÍCIOS-06 
FILAS E PILHAS 
ESTRUTURA-LISTA-06 MANUEL 
 
6 
11- A figura abaixo mostra uma aplicação da estrutura de dados pilha denominada 
MEC, inicialmente vazia, suportando três operações básicas, conforme definidas no 
Quadro I. Observe que o Quadro II apresenta uma sequência de operações sobre a 
estrutura. 
QUADRO I – operações permitidas pela estrutura de dados pilha 
 
OPERAÇÃO DESCRIÇÃO 
Push(PILHA,w) Insere um elemento w na Pilha 
Pop(PILHA) Retira o elemento do topo da pilha 
Top(PILHA) Acessa sem remover o elemento do topo da pilha 
 
QUADRO-II – operações realizadas 
PUSH(MEC,operacional) 
PUSH(MEC,gerencial) 
PUSH(MEC,organizacional) 
PUSH(MEC,táticol) 
TOP(MEC) 
PUSH(MEC,POP(MEC)) 
PUSH(MEC,estrangeiro) 
PUSH(MEC,TOP(MEC)) 
POP(MEC) 
POP(MEC) 
Ao final das operações, o elemento que se encontra no topo da pilha é: 
(A) organizacional 
(B) operacional 
(C) estratégico 
(D) gerencial 
(E) tático 
 
12- As estruturas de dados podem ser caracterizadas como forma organizada de armazenar 
dados ou informações na memória, de modo a otimizar o acesso de algoritmos de 
manipulação de dados associados a estas estruturas. Sendo assim, 
(A) as pilhas são estruturas que recuperam os dados na ordem reversa em que eles foram 
armazenados. 
(B) as pilhas são estruturas que recuperam os dados na ordem direta em que eles foram 
armazenados. 
(C) as filas são estruturas que recuperam os dados na ordem reversa em que eles foram 
armazenados. 
(D) as filas são estruturas que recuperam os dados na ordem reversa em que eles foram 
retirados. 
(E) as filas e as pilhas são estruturas que recuperam os dados na ordem direta em que eles 
foram armazenados 
 
ESTRUTURA DE DADOS 
LISTA DE EXERCÍCIOS-06 
FILAS E PILHAS 
ESTRUTURA-LISTA-06 MANUEL 
 
7 
13- A estrutura de dados apropriada para armazenar umasequência de requisições HTTP, 
que chegam à um servidor Web e que devem ser processadas de forma sequencial, é a: 
(A) pilha; 
(B) fila; 
(C) árvore de difusão; 
(D) tabela de dispersão; 
(E) árvore B. 
14- Sobre estruturas de dados e seus tipos, para cada afirmativa abaixo, informe se é 
verdadeira (V) ou falsa (F). Em seguida, marque a opção que corresponde à sequência 
CORRETA. 
( ) Inteiro e caractere são tipos primitivos de dados. 
( ) Em uma lista encadeada, cada elemento ocupa posição sucessiva ao elemento anterior. 
( ) Uma variável do tipo apontador sempre armazena o endereço de memória da posição 
onde se encontra o elemento a ser acessado. 
( ) O tipo de dado abstrato constitui uma ferramenta útil para especificar as propriedades 
lógicas de um tipo de dado. 
(A) F - F - V - V 
(B) F - F - F - V 
(C) V - F - V - F 
(D) V - F - V – V 
(E) V - V - V - F 
 
15- Sobre as estruturas de dados lineares, analise as proposições abaixo. 
1) Uma pilha é uma lista com acesso restrito a apenas uma das extremidades, tanto para 
inserir quanto para remover. 
2) Uma fila é uma lista com acesso restrito a ambas as extremidades: uma apenas para 
inserção e a outra apenas para remoção. 
3) Devido a sua característica dinâmica, uma lista não pode ser implementada em um 
arranjo. 
4) Uma fila é mais eficientemente implementada, em uma lista simplesmente encadeada, se 
as remoções são realizadas na cabeça da lista, e as inserções na cauda da lista. 
Estão corretas: 
A) 1, 2, 3 e 4. 
B) 1, 2 e 3, apenas. 
C) 1, 2 e 4, apenas. 
D) 1, 3 e 4, apenas. 
E) 2, 3 e 4, apenas. 
 
16- Em um sistema de memória virtual que utiliza paginação, todas as molduras de páginas 
podem estar ocupadas quando requeridas por um processo. Na estratégia de substituição 
de páginas que substitui a página que está há mais tempo no sistema, utiliza-se a estrutura 
(A) FIFO. (B) Pilha. (C) LIFO. (D) Árvore. (E) Escalonamento. 
ESTRUTURA DE DADOS 
LISTA DE EXERCÍCIOS-06 
FILAS E PILHAS 
ESTRUTURA-LISTA-06 MANUEL 
 
8 
 
17- Uma lista linear é um conjunto de informações de qualquer tipo, organizadas 
sequencialmente. A organização sequencial estabelece uma relação de ordem, decorrendo 
daí a possibilidade de identificar qualquer elemento da lista: o primeiro ou último ou qual 
elemento precede ou sucede qualquer outro. 
Partindo dessa organização, as operações básicas em listas lineares são: 
a) Inserção e inclusão. 
b) Busca, inserção e remoção. 
c) Busca e arquivamento. 
d) Inserção, remoção e arquivamento. 
e) Aqruivamento e remoção 
 
18- Acerca de estrutura de dados, julgue os itens. 
I- A fila é uma lista de elementos em que os itens são sempre inseridos em uma das 
extremidades e excluídos da outra. 
II- No tipo abstrato de dados denominado fila, a inserção ou eliminação de um item é 
realizada em uma única extremidade, ao passo que na pilha a inserção é feita em uma 
extremidade e a remoção, na outra. 
III- A implementação de lista por meio de apontadores permite utilizar posições não 
contíguas de memória, de modo a se poder inserir e retirar elementos sem que haja 
necessidade de deslocar os itens seguintes da lista. 
IV- A estrutura de uma lista encadeada mantém uma coleção de itens em ordem linear, sem, 
no entanto, exigir que eles ocupem posições consecutivas na memória. 
Estão correto apenas os itens: 
(A) I e II 
(B) I e III 
(C) II, III e IV 
(D) I, II e IV 
(E) I, III e IV 
 
19- Considere o tipo abstrato de dados Pilha com as seguintes especificações: 
Pilha é uma lista (LIFO) de itens com a restrição de que inserções (Push) e retiradas 
(Pop) de itens só podem ser feitas no final da lista (Topo da lista). 
CriarP cria uma pilha P vazia. - Push(P, i) insere o item i no Topo da pilha P. 
Pop(P) retira e retorna da pilha P o item que está no Topo da pilha P. 
Pop(P) para pilha P vazia = Erro. 
Com essa especificação, quais são, respectivamente, os resultados das expressões: 
Pop(Push(CriarP, X)) ; Pop (CriarP) e Pop(Push(P,(Pop(Push(CriarP,X))))) ? 
(A) X, X, X 
(B) X, Erro, Erro 
(C) X, Erro, X 
(D) Erro, Erro, Erro 
(E) Erro, Erro, X 
 
 
ESTRUTURA DE DADOS 
LISTA DE EXERCÍCIOS-06 
FILAS E PILHAS 
ESTRUTURA-LISTA-06 MANUEL 
 
9 
20- A tabela abaixo mostra as operações para a manipulação de uma pilha 
 
PUSH Coloca um novo elemento no topo da pilha. 
POP Retira o elemento do topo da pilha. 
Operação 
unária 
Efetua a operação sobre o elemento do topo 
da pilha e substitui o elemento do topo pelo 
resultado. Operações disponíveis: 
DEC (subtrai o valor 1 do elemento). 
Operação 
binária 
Efetua a operação sobre os dois elementos 
no topo da pilha; retira os dois elementos do 
topo da pilha e coloca o resultado da 
operação no topo da pilha. Operações 
disponíveis: ADD (adição, X + Y), SUB 
(subtração, X -Y),MPY (multiplicação, X * Y) e 
DIV (divisão, X / Y), onde Y é o elemento no 
topo da pilha e X o elemento abaixo de Y. 
 
Utilizando as definições acima, a sequência de instruções a seguir foi implementada para 
avaliar o resultado de uma expressão, sendo A, B, C, D e E os operandos desta expressão. 
O resultado da avaliação é acumulado em F. 
PUSH A 
PUSH B 
SUB 
PUSH C 
PUSH D 
PUSH E 
MPY 
ADD 
DEC 
DIV 
POP F 
Com base no que foi exposto acima, se A, B, C, D e E apresentarem, respectivamente, os 
valores 9, 3, 2, 1 e 1, qual o valor armazenado em F após a execução da instrução POP F? 
(A) 2 
(B) 3 
(C) 4 
(D) 5 
(E) 6 
 
 
 
 
 
A simplicidade é o último grau de sofisticação. 
Leonardo Da Vinci