Apol2 Estrutura de Dados Nota 100

Prévia do material em texto

Questão 1/5 - Estrutura de Dados
No último tópico da AULA 2 vimos algoritmos de busca.
Acerca de algoritmos de busca sequencial e binária, assinale a alternativa INCORRETA:
Nota: 20.0
	
	A
	Uma busca binária pode ser implementada utilizando o princípio de dividir para conquistar, e portanto, complexidade O(n²).
Você acertou!
O(logn)
	
	B
	A busca binária só funcionará com um vetor de dados já ordenado. Portanto, além de sua complexidade, existe a complexidade atrelada a uma possível ordenação prévia dos dados.
	
	C
	O algoritmo de busca sequencial pode ser implementado com um só laço de repetição, caracterizando O(n).
	
	D
	A busca sequencial poderá funcionar com um conjunto de dados ordenação ou não ordenado.
	
	E
	A busca binária realiza seu algoritmo de localização do dado dividindo o conjunto de dados ao meio, e comparando o valor central com o buscado.
Questão 2/5 - Estrutura de Dados
No terceiro assunto de nossa disciplina estudamos estruturas de dados que se comportam como uma PILHA.
Acerca de PILHA, assinale a alternativa INCORRETA:
Nota: 20.0
	
	A
	Em uma pilha construída utilizando listas encadeadas. Desempilhar nela significa remover o primeiro elemento desta pilha.
Sim. Remoção no topo.
	
	B
	Uma pilha pode só pode ser construída empregando uma estrutura de dados que trabalhe de maneira não sequencial.
Você acertou!
Podemos construir com vetores (sequencial) ou listas (não sequencial).
	
	C
	Uma pilha trabalha com inserção e remoção no topo da pilha. Sendo impossível manipular qualquer outra posição da pilha.
Sim. Estrutura do tipo FILO.
	
	D
	Em uma pilha construída utilizando listas encadeadas. Empilhar nela significa inserir antes do primeiro elemento desta pilha.
Sim. Inserção no topo.
	
	E
	Em uma, a cada nova inserção, os elementos anteriores vão ficando para o final da pilha, só sendo possível removê-los desempilhando.
Sim. FILO.
Questão 3/5 - Estrutura de Dados
No terceiro assunto de nossa disciplina estudamos uma nova estrutura de dados denominada de LISTA ENCADEADA. Um tipo de lista encadeada é a chamada de LISTA ENCADEADA SIMPLES, ou LISTA SIMPLESMENTE ENCADEADA.
Acerca de listas encadeadas simples, assinale a alternativa INCORRETA:
Nota: 20.0
	
	A
	Uma lista encadeada simples pode ser do tipo circular. Isto significa que o seu último elemento conterá um ponteiro não nulo e que apontará de volta para ele mesmo, fechando círculo.
Você acertou!
O último elemento aponta para o início da lista de volta, e não para ele mesmo.
	
	B
	Uma lista encadeada simples conterá, em cada seu elemento, uma variável do tipo ponteiro que manterá o endereço do próximo elemento da lista encadeada.
	
	C
	O uso de ponteiros serve para que, embora cada elemento da lista encadeada esteja disperso na memória do programa, eles possam ser localizados e conectados em uma estrutura de dados.
	
	D
	Uma lista encadeada simples pode ser do tipo não circular. Isto significa que o seu último elemento conterá um ponteiro nulo (vazio).
	
	E
	Podemos realizar uma inserção em qualquer posição de uma lista encadeada, no início, no fim ou mesmo no meio desta lista.
Questão 4/5 - Estrutura de Dados
Uma função que implementa parte do algoritmo quick sort pode ser vista abaixo. Todo o resto do algoritmo foi omitido para que analisemos somente este método. O algoritmo completo pode ser visto no material PDF da Aula 2.
No código, a função chamada de particao refere-se à função que localiza um pivô no vetor de dados e faz as respectivas trocas dos valores, ordenando seguindo algum critério. 
No código, vet é o vetor de dados, e troca é a função que realiza uma troca entre dois valores destoantes utilizando uma variável auxiliar.
1. int particao(int vet[], int p, int u) 
2. {
3. int pivo, pivo_pos, i, j;
4. pivo_pos = (p + u) / 2;
5. pivo = vet[pivo_pos];
6. 
7. i = p - 1;
8. j = u + 1;
9. while (i < j)
10. {
11.      do 
12.      {
13.           j--;
14.      } while (vet[j] > pivo);
15. 
16.      do 
17.      {
18.           i++;
19.       } while (vet[i] < pivo);
20. 
21.       if (i < j)
22.           troca(vet, i, j);
23.       }
24.      return j;
25. }
Acerca deste algoritmo, assinale a alternativa INCORRETA:
Nota: 20.0
	
	A
	A variável pivo_pos localiza a posição a qual conterá o valor de referência para comparações com todos os outros valores do vetor.
	
	B
	Na linha 11 até a linha 14 comparamos o pivô com todos os valores ao lado direito do mesmo. Caso um valor seja menor que o pivô, ele deve ser colocado para uma posição anterior a do pivô, ou no máximo, no local do pivô.
	
	C
	Na linha 16 até a linha 19 comparamos o pivô com todos os valores ao lado esquerdo do mesmo. Caso um valor seja maior que o pivô, ele deve ser colocado para uma posição posterior a do pivô, ou no máximo, no local do pivô.
	
	D
	A troca (linha 21 e 22) pode acontecer entre um valor do lado esquerdo e do lado direito, ou entre o próprio pivô e um dos valores destoantes de cada um dos lados.
	
	E
	Na linha 4 acessamos a posição do pivô no vetor e na linha 5 acessamos a posição correspondente do vetor conforme calculado na linha 4.
Você acertou!
Primeiro localizamos a posição (linha 4) e depois o valor daquela posição (linha 5).
Questão 5/5 - Estrutura de Dados
No terceiro assunto de nossa disciplina estudamos estruturas de dados que se comportam como uma FILA.
Acerca de FILAS, assinale a alternativa CORRETA:
Nota: 20.0
	
	A
	Uma fila onde o primeiro elemento é o 66, o segundo é o 33 e o terceiro é o 99. Inserir na fila significaria inserir um elemento que aponte para o valor 66.
Inseriria depois do valor 99 (inserção no final da fila).
	
	B
	Em uma fila, podemos ter a inserção dos dados início desta fila.
Inserção somente no final.
	
	C
	Em uma fila, podemos ter a remoção dos dados final ou no meio desta fila.
Remoção somente no início.
	
	D
	Em uma fila trabalhamos com o conceito de: “o primeiro que entra é o primeiro que sai”.
Você acertou!
Correto. FIFO.
	
	E
	Uma fila onde o primeiro elemento é o 66, o segundo é o 33 e o terceiro é o 99. Remover da fila significaria remover o elemento 99.
Removeria o 66 (remoção no início da fila).