estrutura de dados simulado

Prévia do material em texto

1a
          Questão 
	Acerto: 1,0  / 1,0 
	
	A forma correta para imprimir o valor do último elemento de um vetor v com n posições é:
		
	
	cout << v[n+1];
	
	cout << v[n-1];
	
	cout << v[ultimo];
	
	cout << v[n];
	
	cin >> v[-1];
	Respondido em 18/11/2020 21:11:42
	
		2a
          Questão 
	Acerto: 1,0  / 1,0 
	
	O que será mostrado na tela pelo programa abaixo ? 
#include < iostream >
using namespace std;
int a,b;
void dobro(int x){ //x passado por valor
 x=2*x;
}
int triplo(int y){ //y passado por valor
 return 3*y;
}
void altera(int x, int &y) { //x passado por valor e y passado por referencia
 x=x+a;
 y=x+b;
} 
 
int main (){
 a=2;
 b=3;
 dobro(a);
 b=triplo(b);
 altera(a,b);
 cout<< a << " e " << b << endl;
}
 
		
	
	9 e 16
	
	2 e 9
	
	2 e 13
	
	4 e 12
	
	4 e 9
	Respondido em 18/11/2020 21:36:29
	
	Explicação: 
Executando o programa, passo a passo, temos :
Na main, a recebe 2 e b recebe 3.  Note que a e b são variáveis globais.
Daí, ainda na main, a função dobro é chamada. Ao executar dobro, temos que o valor 2 é passado e x (local à dobro) recebe 2 * 2, que dá 4.
Ao terminar a função dobro, volta-se para a main, mas o valor de a passado não mudou, continuando 2.
Após a execução de dobro, a função triplo é chamada na main e é passado o valor de b,  que é  3.  Iniciando a execução da função triplo, temos que y recebe 3 e a função retorna 3 * 3, que é 9. Voltando para a main, temos que b recebe o valor retornado pela função, que é 9.
Até este ponto, temos que a vale 2 e b mudou para 9.
Em seguida, a função altera é chamada e são passados 2 e 9, respectivamente, para x e y.  Executando a função altera, temos que x recebe 2+2, que dá 4 e y recebe 4+9, que dá 13.  Como x é passado por valor e y por referência, temos que a mudará e b mudará (ambas na main).
Então, voltando para main temos que a vale 2 e que b vale 13. Assim, será impresso na tela
           2  e   13
	
		3a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Com relação à struct, é correto afirmar que :
		
	
	Cada elemento da struct é chamado componente.
	
	Cada elemento da struct é denominado membro ou campo, sendo que a struct pode armazenar elementos de tipos diferentes ou não.
	
	Não é possível criar um vetor de structs, pois o vetor trabalha apenas com dados do mesmo tipo.
	
	A struct é sempre definida dentro da main.
	
	Cada elemento da struct é chamado campo e cada campo deve ser, obrigatoriamente, de um tipo de dados distinto de outro campo.
	Respondido em 18/11/2020 21:20:48
	
		
	Gabarito
Comentado
	
	
	
		4a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Em uma pesquisa sequencial a lista deve estar?
		
	
	sempre desordenada.
	
	desordenada somente da metade da lista até o final.
	
	ordenada somente do início até a metade da lista.
	
	ordenada somente o primeiro da lista.
	
	ordenada ou desordenada.
	Respondido em 18/11/2020 21:18:59
	
	Explicação: 
A busca sequencial pode se usada para listas ordenadas ou não ordenadas, não havendo qualquer restrição a parte ou à  totalidade da lista na ordenação.  Já a busca binária só pode ser usada para listas ordenadas.
	
		
	Gabarito
Comentado
	
	
	
		5a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Considere as seguintes afirmações sobre Listas Sequenciais:
I  - São estruturas lineares que utilizam as primeiras posições de um vetor para armazenar os dados de interesse.
II - São compostas pelo conjunto dos dados que se deseja armazenar e por uma variável inteira que indica a quantidade de dados armazenados.
III - Os dados são sempre inseridos ou removidos no final da lista, tomando-se o cuidado de atualizar a quantidade de dados da mesma.
IV - A lista pode admitir ou não admitir que haja dados repetidos (listas podem ser com ou sem repetição).
Marque a opção que contém apenas todas  as afirmações verdadeiras:
		
	
	I, II, IV
	
	I, III, IV
	
	I, II
	
	I, II, III, IV
	
	I, II, III
	Respondido em 18/11/2020 21:26:06
	
	Explicação: 
Analisando cada afirmativa :
 
I  - São estruturas lineares que utilizam as primeiras posições de um vetor para armazenar os dados de interesse.
Verdadeiro.  As inserções vão ocorrendo do início do vetor (índice zero) em direção ao fim.
II - São compostas pelo conjunto dos dados que se deseja armazenar e por uma variável inteira que indica a quantidade de dados
armazenados.
Verdadeiro. Armazenam-se os dados  e controla-se a quantidade de dados na lista.
III - Os dados são sempre inseridos ou removidos no final da lista, tomando-se o cuidado de atualizar a quantidade de dados 
da mesma.
Falso. A inserção pode ser no início,  no meio ou no final da lista. Na verdade, pode ocorrer inserção e remoção em qualquer  posição.
IV - A lista pode admitir ou não admitir que haja dados repetidos (listas podem ser com ou sem repetição).
Verdadeiro.  Uma lista pode ou não ter dados repetidos.
Resposta certa : As afirmativas I, II, IV estão certas
	
		6a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Existem vários tipos de estruturas de dados do tipo dinâmicas, entretanto, uma estrutura considerada simples são as listas. Pode-se implementar vários tipos de listas, entretanto, a estrutura que apresenta o conceito de LIFO é:
		
	
	Pilha
	
	Struct
	
	Ponteiro
	
	Fila
	
	Matriz
	Respondido em 18/11/2020 21:16:09
	
		
	Gabarito
Comentado
	
	
	
		7a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Qual estrutura de dados é mais adequada para armazenar em um sistema operacional os processos que estão prontos para utilizar o processador? 
		
	
	Lista
	
	Grafo
	
	Fila
	
	Pilha
	
	Árvore
	Respondido em 18/11/2020 21:15:00
	
	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.
	
		8a
          Questão 
	Acerto: 0,0  / 1,0 
	
	Considere a função em C++ que manipula  uma lista simplesmente encadeada :
void imprime (Lista  *l)   {
   Lista* p; 
   for (p = l;   p != NULL;   p = p->prox) 
         cout  <<"Info  =  "  <<  p->info; 
}
sendo 
struct Lista {
                            int info;
                            struct Lista *prox;
};
 
		
	
	Função para liberar a lista
	
	Função que retira um elemento da lista
	
	Função que percorre os elementos da lista
	
	Função de busca
	
	Função que verifica se lista está vazia
	Respondido em 18/11/2020 21:30:20
	
	Explicação: 
Veja que existe um loop em que o ponteiro é inicializado e a cada rodada do for,  imprime o dado da lista e passa a apontar para o próximo nó da lista. Logo, a função percorre a lista.
 >> Não poderia ser verificar lista vazia porque para isso teríamos que testar se o ponteiro é NULL.
>> Não pode ser busca, pois seria  preciso testar cada elemento da lista. Se encontrasse deveria retornar o endereço do nó, caso contrário deveria retornar NULL.
>> Para retirar elemento teríamos que usar delete, para liberar memória, entre outros. Logo, não pode ser.
>> PAra liberar a lista teríamos que repetidamente usar delete, em um loop. Não pode ser.
	
		9a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Para converter de decimal para binário usamos a estrutura de dados pilha. Assinale a opção que, corretamente, indica as ações corretas para empilhar o resto da divisão gerado no processo de conversão, considerando uma lista simplesmente encadeada. Considere o tipo definido abaixo : 
struct no { 
int dado; 
struct no *link; 
}; 
		
	
	Não é necessário alocar memória com new. Basta criar uma struct do tipo no, armazenar o resto da divisão número por 2 no campodado e aterrar o campo link.
	
	Basta alocar memória com new e armazenar o resto da divisão do número por 2 no campo dado do novo nó . 
	
	Basta alocar memória com new, armazenar o resto da divisão do número por 2 no campo dado do novo nó e aterrar o link do novo nó.
	
	É preciso armazenar o resto da divisão do número por 2 no campo dado do primeiro nó da lista e retornar o ponteiro para este nó.
	
	É preciso alocar memória com new, armazenar o resto da divisão do número por 2 no campo dado do novo nó, apontar o link do novo nó para o início da lista e enfim, retornar o ponteiro para o novo nó.
	Respondido em 18/11/2020 21:25:08
	
		
	Gabarito
Comentado
	
	
	
		10a
          Questão 
	Acerto: 0,0  / 1,0 
	
	   Considere uma lista duplamente encadeada não circular em que
 
struct nodupla {
		 int dado;
		 struct nodupla *dlink; // aponta p/ o nó à direita
		 struct nodupla *elink; // aponta p/ o nó à esquerda
 };
 
sendo nodupla *p; //ponteiro para o início da lista
 
   A opção que corretamente mostra as instruções para inserir um valor no início da lista apontada por p é :
		
	
	 
 nodupla *novo;
 
	novo = new nodupla;
	novo->dado = valor;
	 novo->dlink = p;
	novo->elink = NULL;
 p->elink = novo;
	p = novo;
 
	
	 
n  nodupla *novo;
 
	novo = new nodupla;
	novo->dado = valor;
	novo->elink = NULL;
	if (p != NULL)
	 p->elink = novo;
	p = novo;
 
 
	
	   
   nodupla *novo;
 
	novo = new nodupla;
	novo.dado = valor;
	novo.dlink = p;
	novo.elink = NULL;
	if (p != NULL)
	 p.elink = novo;
	p = novo;
	
	n  
   
   nodupla *novo;
 
	novo = new nodupla;
	 novo->dado = valor;
	novo->dlink = p;
	if (p != NULL)
	 p->elink = novo;
	p = novo;
	
	   nodupla *novo;
 
	novo = new nodupla;
	novo->dado = valor;
	novo->dlink = p;
	novo->elink = NULL;
	if (p != NULL)
 p->elink = novo;
	p = novo;
Struct
· Cada elemento da struct é denominado membro ou campo, sendo que a struct pode armazenar elementos de tipos diferentes ou não.
Pilha 
· estrutura de dados que permite a inserção/ remoção de itens dinamicamente seguindo a norma de último a entrar, primeiro a sair (LIFO) empilhamento
· manipulação dos dados sempre se dá no topo.
· Após a operação de remoção decrementa a variável indicadora de posição
· retirar um elemento de uma pilha que já está vazia causa Underflow
· 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.
Pilha estática
· Ordenar é uma operação que não se faz com pilha. 
· Inserir dados é uma operação que se faz com a pilha. 
· Verificar se a Pilha está cheia é necessário quando se deseja inserir nela. 
Lista 
· Na fila, o primeiro a entrar é o primeiro a sair, pois segue a lógica FIFO. 
· Em uma lista tanto as inserções quanto as remoções podem ser feitas em qualquer posição.
· estrutura de dados é mais adequada para armazenar em um sistema operacional os processos que estão prontos para utilizar o processador
· Em uma lista circular, o1o. elemento aponta para o segundo elemento, mas o último elemento aponta para o 1º. elemento da lista.
· Para remover um elemento de uma lista duplamente encadeada, deve-se alterar o encadeamento dos elementos anterior e próximo ao elemento removido. A sequência correta de cima para baixo
· lista duplamente encadeada permite na cadeia movimentos para frente e para trás apenas e pode ser percorrida com igual facilidade para a direita ou para a esquerda, pois existem dois ponteiros.
Listas Sequenciais:
· São estruturas lineares que utilizam as primeiras posições de um vetor para armazenar os dados de interesse.
· São compostas pelo conjunto dos dados que se deseja armazenar e por uma variável inteira que indica a quantidade de dados armazenados.
· A lista pode admitir ou não admitir que haja dados repetidos (listas podem ser com ou sem repetição).
Fila 
· 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
·    Dada a Fila [3-4-6-8-10], executam-se os comandos na ordem: insere(1), insere(2), remove(). ------ [4-6-8-10-1-2]
Fila encadeada com alocação dinâmica
· Fila é uma lista que segue a lógica FIFO.
· Remove sempre o primeiro insere (3,5,8) remove (3)
Grafos
· É um exemplo de TAD Não Linear
Árvore 
· estrutura do diretório do sistema de arquivos
Registro
· estruturas de dados é classificada como heterogênea
Deque 
· Uma fila duplamente terminada, isto é, uma estrutura linear que permite inserir e remover de ambos os extremos
Alocação estática de memória: Toda a memória utilizada pela aplicação não muda durante toda a sua execução 
Alocação estática e dinâmica de memória: A memória utilizada pela aplicação é inicialmente estática, mas pode mudar
Ordenação Bolha(BubbleSort): método que utiliza a estratégia de ordenação por trocas de vizinhos e é considerado o método mais simples. As únicas que são ordenações por troca são Bubblesort e Quicksort. Quicksort, trabalha com pivô.
Bubble sort é o algoritmo mais simples, mas o menos eficientes. Neste algoritmo cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 2 será comparado com o elemento da posição 3. Caso o elemento da posição 2 for maior que o da posição 3, eles trocam de lugar e assim sucessivamente. Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes.
 O Quicksort é o algoritmo mais eficiente na ordenação por comparação. Nele se escolhe um elemento chamado de pivô, a partir disto é organizada a lista para que todos os números anteriores a ele sejam menores que ele, e todos os números posteriores a ele sejam maiores que ele. Ao final desse processo o número pivô já está em sua posição final. Os dois grupos desordenados recursivamente sofreram o mesmo processo até que a lista esteja ordenada.