ESTRUTURA DE DADOS 3° AULA (7)

Prévia do material em texto

1a Questão
	
	
	
	
	IFMT - Técnico em Tecnologia 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]
	
	[3-4-6-8-10]
	
	[2-1-3-4-6-8]
	 
	[4-6-8-10-1-2]
	
	[3-4-6-8-10-1]
	Respondido em 02/04/2020 15:20:31
	
Explicação:
Temos a fila inicialmente 
  3 4 6 8  10
Após inserir 1, a fila ficará :  3 4 6  8 10 1
Após isnerir 2 : 3 4 6  8 10 1 2
Após uma remoção :  4 6  8 10 1 2
	
	
	 
	
	 2a Questão
	
	
	
	
	Uma fila duplamente terminada, isto é, uma estrutura linear que permite inserir e remover de ambos os extremos é chamada de:
		
	 
	Deque.
	
	Árvore.
	
	Autômato.
	
	Boyer-Moore.
	
	Shift-and.
	Respondido em 02/04/2020 15:21:04
	
Explicação:
Em ciência da computação, uma fila duplamente terminada (frequentemente abreviada como deque, do inglês double ended queue) é um tipo de dado abstrato que generaliza uma fila, para a qual os elementos podem ser adicionados ou removidos da frente (cabeça) ou de trás (cauda). Também é chamada de lista encadeada cabeça-cauda, apesar de propriamente isto se referir a uma implementação de estrutura de dados específica.
As deques são filas duplamente ligadas, isto é, filas com algum tipo de prioridade. Por exemplo, sistemas distribuídos sempre necessitam que algum tipo de processamento seja mais rápido, por ser mais prioritário naquele momento, deixando outros tipos mais lentos ou em fila de espera, por não requerem tanta pressa. Ele pode ser entendido como uma extensão da estrutura de dados Fila.
A implementação de um deque por alocação estática ou seqüencial é feita por meio de um arranjo de dimensão máxima predefinida e de duas variáveis inteiras que indicam o topo e a base (head e tail, respectivamente). Da mesma forma que ocorre com a fila, o deque deve ser implementado segundo a abordagem circular, que confere eficiência à estrutura ao mesmo tempo em que evita o desperdício de memória.
	
	
	 
	
	 3a Questão
	
	
	
	
	Considere uma fila simples F  de inteiros,  do tipo Fila definido abaixo. Tal fila deverá armazenar códigos de agentes de uma firma de espionagem, desde que haja espaço para um novo agente.  Assinale a opção que corretamente enfileira o código de um agente, sabendo que a fila F foi inicializada de acordo com o trecho de código abaixo.
struct Fila {     in t v[100], inicio, fim; } ;
Fila F;
F. inicio = 0;
F.fim = -1;
 
 
		
	
	 
void enfileirar(Fila &F, int codigo)  {
    F.v[F.fim] = codigo;
     F.fim++;
}
	
	void enfileirar(Fila &F, int codigo)  {
       if (F.fim == 99)
            cout <<  "Não há espaço na firma para mais agentes. " << endl;
      else
           F.fim++;
    F.v[F.fim] = codigo;
}
 
 
	 
	void enfileirar(Fila &F, int codigo)  {
       if (F.fim == 99)
            cout << "Não há espaço na firma para mais agentes. " << endl;
      else  {
         F.fim++;
        F.v[F.fim] = codigo;
    }
}
 
	
	void enfileirar(Fila F, int codigo)  {
     F.fim++;
    F.v[F.fim] = codigo;
}
 
	
	void enfileirar(Fila F, int codigo)  {
       if (F.fim == 100)
            cout << "Não há espaço na firma para mais agentes. " << endl;
     else  {
         F.fim++;
        F.v[F.fim] = codigo;
   }
}
 
	Respondido em 05/04/2020 11:42:29
	
	
	Gabarito
Coment.
	
	 
	
	 4a 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:
		
	
	pilha sequencial
	
	lista sequencial
	
	pilha circular
	
	lista circular
	 
	fila circular
	Respondido em 05/04/2020 11:42:36
	
	
	Gabarito
Coment.
	
	 
	
	 5a Questão
	
	
	
	
	Um órgão público adotou dois sistemas de senhas para atender os cidadãos na ordem de chegada. O sistema I atende os não idosos. O sistema II atende os idosos. Nessa situação:
		
	
	tanto o sistema I, quanto o II, adotam o esquema vetor de organização de dados.
	
	o sistema I, adota o esquema FIFO de organização de dados e o II, o esquema LIFO.
	 
	tanto o sistema I, quanto o II, adotam o esquema FIFO de organização de dados.
	
	tanto o sistema I, quanto o II, adotam o esquema LIFO de organização de dados.
	
	o sistema I, adota o esquema LIFO de organização de dados e o II, o esquema FIFO.
	Respondido em 05/04/2020 11:42:53
	
Explicação:
Como os dois sistemas usam a ordem de chegada, temos o uso de fila caracterizando os 2 sistemas.  Como fila segue a lógica FIFO, os 2 sistemas seguem esta lógica FIFO.
Note que LIFO é de pilha, o que não cabe aqui. Na pilha, o último a entrar é o primeiro a sair.
 
	
	
	 
	
	 6a Questão
	
	
	
	
	Considere as afirmativas a seguir:
I. As estruturas de dados pilhas, filas e listas armazenam coleções de itens. A característica que as distinguem é a ordem em que podem ser retirados os itens dessas coleções em relação à ordem em que foram inseridos.
II. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma fila. Necessariamente, o primeiro elemento a ser removido dessa fila é o elemento A.
III. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma pilha. Necessariamente, o último elemento a ser removido dessa pilha é o elemento E.
IV. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma lista. Necessariamente, o primeiro elemento a ser removido dessa lista é o elemento A.
		
	
	Somente as afirmativas III e IV são corretas.
	 
	Somente as afirmativas I e II são corretas.
	
	Somente as afirmativas I e IV são corretas.
	
	Somente as afirmativas II, III e IV são corretas.
	
	Somente as afirmativas I, II e III são corretas.
	Respondido em 05/04/2020 11:42:58
	
Explicação:
Analisando cada afirmativa :
I. As estruturas de dados pilhas, filas e listas armazenam coleções de itens. A característica que as distinguem é a ordem em que podem ser retirados os itens dessas coleções em relação à ordem em que foram inseridos.
Correto.  Na pilha insere-se no topo e retira-se do topo. Na fila, insere-se no fim e retira-se do início. E na lsita, insere-se e retira-se de qualquer posição.
II. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma fila. Necessariamente, o primeiro elemento a ser removido dessa fila é o elemento A.
Correto.  Fila segue a lógica FIFO, ou seja, o primeiro a entrar será o primeiro a sair.
III. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma pilha. Necessariamente, o último elemento a ser removido dessa pilha é o elemento E.
Errado.  O último a entrar foi o E, logo o E terá que ser o primeiro a sair e não o último.  Note que pilha segue a lógica LIFO.
IV. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma lista. Necessariamente, o primeiro elemento a ser removido dessa lista é o elemento A.
Errado. Qualquer elemento pode ser removido da lista.
Logo, a resposta certa é Somente as afirmativas I e II são corretas.
	
	
	 
	
	 7a Questão
	
	
	
	
	Sobre pilhas, lista e filas, considere as afirmativas a seguir. I. As estruturas de dados pilhas, filas e listas armazenam coleções de itens. A característica que as distinguem é a ordem em que podem ser retirados os itens dessas coleções e a ordem em que foram inseridos. II. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma fila. Necessariamente, o primeiro elemento a ser removido dessa fila é o elemento A. III. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma pilha. Necessariamente,o último elemento a ser removido dessa pilha é o elemento E. IV. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma lista. Necessariamente, o primeiro elemento a ser removido dessa lista é o elemento A.
		
	
	Somente as afirmativas I, II e III são corretas.
	 
	Somente as afirmativas I e II são corretas.
	
	Todas as afirmativas estão corretas
	
	Somente as afirmativas III e IV são corretas.
	
	Somente as afirmativas I e IV são corretas.
	Respondido em 05/04/2020 11:43:06
	
Explicação:
Analisando cad afirmativa:
 I. As estruturas de dados pilhas, filas e listas armazenam coleções de itens. A característica que as distinguem é a ordem em que podem ser retirados os itens dessas coleções e a ordem em que foram inseridos.
>>>>>Verdadeira. A pilha segue a lógica LIFO, fila segue a lógica FIFO e em uma lista insere-se e retira-se de qualquer posição.
II. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma fila. Necessariamente, o primeiro elemento a ser removido dessa fila é o elemento A.
>>>>> Verdadeira. O 1o. a entrar, será o 1o. a sair.
III. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma pilha. Necessariamente, o último elemento a ser removido dessa pilha é o elemento E.
>>>>> FAlso.  O último a entrar foi o E, portanto, pela lógica LIFO é o primeiro a sair.
IV. Considere que os itens A, B, C, D, E foram inseridos nessa ordem em uma lista. Necessariamente, o primeiro elemento a ser removido dessa lista é o elemento A.
>>>> Falso. Em uma lista insere-se em qualquer posição e retira-se de qualquer posição.
Logo, as afirmativa I e II estão corretas.
	
	
	 
	
	 8a Questão
	
	
	
	
	As estruturas de dados podem ser do tipo estática e dinâmica. As listas são estruturas parecidas com vetores podendo ser do tipo dinâmica. Entretanto, existem várias implementações de estruturas do tipo listas. Dessa forma, a estrutura que para o acesso de um dado, este precisa estar na saída, caso contrário, precisa remover os elementos a sua frente, é chamada de:
		
	
	Matriz
	
	Struct
	
	Pilha
	
	Bolha
	 
	Fila
	Respondido em 05/04/2020 11:43:12
	
	
	Gabarito
Coment.