ESTRUTURA DE DADOS 7ª aula

Prévia do material em texto

ESTRUTURA DE DADOS 
7a aula 
Lupa 
 
 
 
Vídeo 
 
PPT 
 
MP3 
 
 
 
 
 
Exercício: CCT0753_EX_A7_201801076693_V1 15/10/2018 09:31:54 (Finalizada) 
Aluno(a): SERGIO RICARDO SIMAO 2018.3 EAD 
Disciplina: CCT0753 - ESTRUTURA DE DADOS 201801076693 
 
 
 
 
 1a Questão 
 
 
 Marque a afirmativa que represente uma Lista Circular Simplesmente Encadeada: 
 
 
O ponteiro do "primeiro" nó não é NULL, mas sim aponta de volta para o "último" nó da lista, 
formando um ciclo. 
 
Cada ponteiro possui um só endereço que referencia o "primeiro" nó da lista. 
 
Cada nó possui um só ponteiro que referencia o próximo nó da lista. 
 
Além do campo relativo ao dado, cada nó possui dois ponteiros, 
 O ponteiro do "último" nó não é NULL, mas sim aponta de volta para o "primeiro" nó da lista. 
 
 
 
 
 
 2a Questão 
 
 
 As filas sequenciais são estruturas de dados utilizadas em diversas aplicações, tais como fila de 
processo, fila de impressão, sistemas de senha etc. Entretanto, nas aplicações onde há muita 
movimentação de dados, inserções e remoções de dados na fila, surgem espaços ociosos que 
podem levar ao fenômeno chamado de esgotamento de memória. Para sanar este problema pode-
se substituir a fila sequencial por: 
 
 
lista circular 
 
lista sequencial 
 
pilha circular 
 fila circular 
 
pilha sequencial 
 
 
 
 
 
 3a Questão 
 
 
 IFMT - Técnico em Técnologia da Informação - 2013 
 Considere a função insere(x: inteiro), que recebe como parâmetro um número inteiro e o insere em uma 
Fila, e ainda, a função remove(), que retira um valor de uma Fila. 
 Dada a Fila [3-4-6-8-10], executam-se os comandos na ordem: insere(1), insere(2), remove(). 
 Após a execução desses comandos, qual será a Fila resultante? 
 
 
[2-3-4-6-8-10] 
 [4-6-8-10-1-2] 
 
[2-1-3-4-6-8] 
 
[3-4-6-8-10] 
 
[3-4-6-8-10-1] 
 
 
Explicação: 
Dada a Fila [3-4-6-8-10], executam-se os comandos na ordem: insere(1), insere(2), remove(). ? 
Temos 3-4-6-8-10 e com a 1a. insere teremos 3-4-6-8-10 - 1 
Com a segunda insere teremos 3-4-6-8-10- 1-2 
E quando remover um valor, sairá o 1o. da fila. Então, a fila ficará assim : 4-6-8-10- 1-2 
 
 
 
 
 
 4a Questão 
 
 
 Seja Q uma estrutura de dados do tipo fila, em que ENQUEUE(X) significa a adição do elemento X à Q e que 
DEQUEUE(), a retirada de um elemento. Q está inicialmente vazia e sofre a seguinte sequencia de operações: 
ENQUEUE(1) 
ENQUEUE(2) 
DEQUEUE() 
ENQUEUE(3) 
ENQUEUE(4) 
DEQUEUE() 
DEQUEUE() 
ENQUEUE(5) 
Ao final da sequencia, a soma dos elementos de que (Q) será? 
 
 
0 
 
5 
 
6 
 
15 
 9 
 
 
 
 
 
 5a Questão 
 
 
 Qual estrutura de dados é mais adequada para armazenar em um sistema operacional os processos que 
estão prontos para utilizar o processador? 
 
 Fila 
 
Lista 
 
Grafo 
 
Árvore 
 
Pilha 
 
 
Explicação: 
Pode se ter uma fila de processos para a CPU (processador), visto 
que o primeiro processo a chegar à fila será atendido primeiro e 
sairá da fila primeiro, o que faz a lógica FIFO, que rege a fila. 
Observe a característica linear do problema. Por tudo isso, a 
resposta é fila. 
 
Lista : linear e não segue FIFO. Insere-se em qualquer posição e 
retira-se de qualquer posição ou se mantém a ordem, se for 
ordenada. 
 
Pilha : segue LIFO 
 
Árvore e Grafo : estrutura de dados não linear. 
 
 
 
 
 
 6a Questão 
 
 
 Pode-se citar os seguintes exemplos de aplicação da estrutura fila: Fila de arquivos para impressão: 
 Atendimento de processos requisitados a um sistema operacional. 
 Buffer para gravação de dados em mídia. 
 O tratamento do armazenamento das teclas que estão sendo digitadas antes da tecla enter ser 
pressionada. 
Agora analise as seguintes afirmativas: 
 I- Uma fila guarda a ordem direta em que os elementos foram armazenados. 
 II- Uma fila guarda a ordem reversa em que os elementos foram armazenados. 
 III- O algoritmo que é implementado em uma fila é baseao no princípio: " O último a entrar é o primeiro a 
sair". 
IV- O algoritmo que é implementado em uma fila é baseao no princípio: " O primeiro a entrar é o primeiro a 
sair". 
 Marque a alternativa correta: 
 
 I e IV estão corretas 
 
I e III estão corretas 
 
Apenas a IV está correta 
 
II e Iv estão corretas 
 
II e III estão corretas 
 
 
 
 
 
 7a Questão 
 
 
 Escolha a opção verdadeira : 
 
 
Pilhas e filas não podem ser implementadas através do uso de listas encadeads 
 Em uma estrutura de dados que segue a lógica LIFO, os dados são excluídos na ordem inversa em que 
foram incluídos. 
 
Uma pilha, a depender de sua configuração, pode funcionar como uma fila 
 
Uma estrutura de dados que segue a lógica FIFO equivale a uma estrutura de dados que segue a lógica 
LIFO. 
 
Uma estrutura de dados que segue a lógica FIFO permite inclusões apenas no topo da estrutura de 
dados. 
 
 
Explicação: 
Analisando cada opção : 
 
Uma estrutura de dados que segue a lógica FIFO permite inclusões apenas no topo da estrutura de dados. 
Falso. Uma estrutura de dados que segue a lógica FIFO, que é a estrutura de dados fila, permite 
inclusões no fim e retiradas do início. 
 
 
Em uma estrutura de dados que segue a lógica LIFO, os dados são excluídos na ordem inversa em que 
foram incluídos. 
Verdadeiro. O último a entrar, será o 1o. a sair. Então, poderá ser o primeiro a ser excluído da pilha. 
 
 
Uma estrutura de dados que segue a lógica FIFO equivale a uma estrutura de dados que segue a lógica 
LIFO. 
FAlso. Pilha segue a lógica LIFO e fila segue a lógica FIFO. 
 
 
Uma pilha, a depender de sua configuração, pode funcionar como uma fila 
FAlso. Pilha segue a lógica LIFO e fila segue a lógica FIFO. 
 
 
Pilhas e filas não podem ser implementadas através do uso de listas encadeadas 
Falso. Tais estruturas podem ser implementadas de forma sequencial e de forma encadeada. 
 
 
 
 
 
 
 8a Questão 
 
 
 Assumindo que estamos com uma estrutura de dados do tipo FIFO, as operações abaixo vão resultar em que 
elementos na mesma: ENFILEIRAR(4), ENFILEIRAR(5), ENFILEIRAR(6), DESENFILEIRAR(), 
DESENFILEIRAR(), ENFILEIRAR(5), ENFILEIRAR(7), DESENFILEIRAR() 
 
 
4 5 
 
4 6 7 
 
4 5 6 
 
7 5 
 5 7