APOL 02 ESTRUTURA DE DADOS

Prévia do material em texto

APOL OBJETIVA 02 – ESTRUTURA DE DADOS
Questão 1/5 - Estrutura de Dados
Uma função que implementa parte do algoritmo merge 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, inicio e fim são variáveis inteiras que correspondem a posições no vetor de dados, parteinteira significa truncar em zero casas decimais o respectivo cálculo da linha 6 e intercala refere-se a uma função que realiza a ordenação neste método.
1. Função mergesort(X, inicio, fim) 
2. Var
3.      Meio: inteiro
4. Inicio
5.      Se (inicio < fim) então
6.           Meio <- parteinteira((inicio + fim) / 2)
7.          mergesort(X, inicio, meio)
8.          mergesort(X, meio + 1, fim)
9.           Intercala(X, inicio, fim, meio)
10.    Fimse
11. funfunção
A assumindo que a dimensão do vetor de dados X é 10, e que a primeira chamada da função mergesort foi realizada com os seguintes parâmetros: Função mergesort(X, 0, 9).
Acerca deste algoritmo, assinale a alternativa INCORRETA:
Nota: 0.0
	
	A
	Na segunda instância aberta da função mergesort na memória do programa, a variável
 inicio vale zero e a variável meio vale 2.
	
	B
	Na primeira instância aberta da função mergesort na memória do programa, a
 variável meio corresponde ao valor 4.
	
	C
	Na segunda instância aberta da função mergesort na memória do programa, a variável
 inicio vale zero e a variável fim vale 2.
Fim vale 4.
	
	D
	Na terceira instância aberta da função mergesort na memória do programa, a variável
 inicio vale zero e a variável fim vale 2.
	
	E
	Na primeira instância aberta da função mergesort na memória do programa, a variável
 inicio vale zero e a variável fim vale 9.
Questão 2/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: 0.0
	
	A
	Uma busca binária pode ser implementada utilizando o princípio de dividir para conquistar, 
e portanto, complexidade O(n²).
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 3/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: 0.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.
Primeiro localizamos a posição (linha 4) e depois o valor daquela posição (linha 5).
Questão 4/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 DUPLA, ou LISTA DUPLAMENTE ENCADEADA.
Acerca de listas encadeadas simples, assinale a alternativa CORRETA:
Nota: 0.0
	
	A
	Uma lista encadeada dupla só permite a inserção no início desta lista.
Permite em qualquer posição.
	
	B
	Uma lista encadeada dupla conterá, em cada elemento, dois ponteiros de endereços.
 Um endereço corresponderá ao primeiro elemento da lista e o outro endereço ao último
 elemento da lista.
Um endereço é do elemento imediatamente subsequente e do anterior, e não do primeiro e último.
	
	C
	Uma lista encadeada dupla circular conterá em seu último elemento, o endereço do primeiro 
elemento da lista. E conterá no seu primeiro elemento, o endereço do último elemento 
da lista. Fechando dois círculos.
CORRETO.
	
	D
	Os dados de uma lisa dupla podem ser acessados mais rapidamente que uma simples, 
devido ao emprego de um ponteiro a mais.
Os ponteiros nada impactam no tempo de acesso da lista.
	
	E
	Uma lista encadeada dupla ocupa o dobro de memória do programa em relação a 
uma lista simples, pois precisa armazenar duas vezes os dados de cada elemento.
O fato de existir um ponteiro a mais não impacta significativamente a ponto de dobra o uso 
de memória.
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).