Estrutura de Dados APOL Objetiva 1 - 90 pontos

Prévia do material em texto

Questão 1/10 - 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: 10.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.
Você acertou!
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/10 - Estrutura de Dados
Uma implementação do algoritmo de ordenação do tipo bubble sort pode ser visto abaixo. As partes que envolvem impressão de dados na tela e leitura de dados foram omitidas para um melhor entendimento do que é necessário na questão. 
X[TAMANHOVETOR], i, j, aux: inteiro
para i de 1 até TAMANHOVETOR faça 
     para j de 0 até (TAMANHOVETOR - 2) faça 
          se (X[j] > X[j + 1]) então 
               aux <- X[j]
               X[j] <- X[j + 1]
               X[j + 1] <- aux
          fimse
     fimpara
fimpara
Acerca deste algoritmo, assinale a alternativa CORRETA:
Nota: 10.0
	
	A
	O algoritmo apresentado no exercício realizado a ordenação de dados numéricos, 
inteiros, em ordem decrescente.
Ordenação é crescente.
	
	B
	As linhas de código que correspondem a troca dos valores usando uma variável 
auxiliar poderiam ser também escritas da seguinte maneira:
aux <- X[j+1]
X[j+1] <- X[j]
X[j] <- aux
Você acertou!
AULA 2 – TEMA 2. CORRETO.
	
	C
	Se precisarmos ordenar dados não numéricos, como caracteres, precisaremos repensar 
em toda a lógica do bubble sort, não sendo possível adaptar o código facilmente.
Basta adaptarmos a linha da condicional para funcionar com outro tipo de dado.
	
	D
	Não é possível implementar o bubble sort com laços de repetição do tipo enquanto.
É possível implementar com qualquer tipo de laço, para, enquanto ou repita.
	
	E
	A complexidade deste algoritmo, para o pior caso, é O(logn).
Complexidade O(n²).
Questão 3/10 - Estrutura de Dados
Uma função que implementa o algoritmo bubble sort pode ser vista abaixo. Todo o resto do algoritmo foi omitido para que analisemos somente o método de ordenação. No código, TAMANHOVETOR refere a um valor inteiro que corresponde a dimensão do vetor de dados.
1 - void BubbleSort(int vet[]) {
2 - int aux;
3 - for (int n = 1; n <= TAMANHOVETOR; n++) {
4 -      for (int i = 0; i < (TAMANHOVETOR - 1); i++) {
5 -           if (vet[i] < vet[i + 1]) {
6 -                aux = vet[i];
7 -                vet[i] = vet[i + 1];
8 -                vet[i + 1] = aux;
9 - } } } }
Acerca deste algoritmo, assinale a alternativa CORRETA:
Nota: 0.0
	
	A
	Na linha 5, o sinal de MENOR está incorreto. O algoritmo do bubble sort  deve 
apresentar um sinal de MAIOR nesta linha.
Tanto faz o sinal. Invertendo sinal inverte a forma como irá ordenar, o que não caracteriza um erro.
	
	B
	Não é possível substituir os laços de repetição do tipo PARA (FOR) por um laço do tipo 
REPITA (DO-WHILE).
É possível implementar com qualquer laço de repetição.
	
	C
	Não é possível substituir os laços de repetição do tipo PARA (FOR) por um laço do tipo 
ENQUANTO (WHILE).
É possível implementar com qualquer laço de repetição.
	
	D
	Na linha 3, seria possível fazer a variável n iniciar em zero e terminar em 
(TAMANHOVETOR-1)
CORRETO. AULA 2 – TEMA 2 e conceitos básicos de programação e algoritmos.
	
	E
	A variável chamada de aux neste código tem como objetivo armazenar temporariamente 
o vetor de dados completo, para posteriormente ser ordenado.
Ela serve para ajudar na troca individual de cada elemento.
Questão 4/10 - Estrutura de Dados
O algoritmo de ordenação rápida, também conhecido como quick sort, é um dos algoritmos estudados na AULA 2.
Acerca deste algoritmo, assinale a alternativa CORRETA.
Nota: 10.0
	
	A
	A complexidade do quick sort é O(n²). Isso significa que ele sempre terá a mesma 
eficiência de um bubble sort. Somente o pior caso do bubble e do quick são iguais. 
Se considerarmos cenários melhores o quick sort se sai bem melhor que o bubble sort. 
Veja o experimento feito na AULA PRÁTICA 1 para mais detalhes.
	
	B
	O quick sort trabalha com o conceito de pivô, que é o elemento usado nas comparações, 
comparando sempre o seu valor com todos os valores do lado direito do pivô, enquanto 
que o lado esquerdo permanece já ordenado.
Ambos os lados são comparados, esquerdo e direito.
	
	C
	O quick sort trabalha com o conceito de pivô, que é o elemento usado nas comparações, comparando sempre o seu valor com todos os valores do lado esquerdo do pivô, enquanto que o lado direito permanece já ordenado.
Ambos os lados são comparados, esquerdo e direito.
	
	D
	O quick sort trabalha com uma troca de valores utilizando uma variável auxiliar, da mesma maneira feita no bubble sort.
Você acertou!
AULA 2 – TEMA 4 – CORRETO.
	
	E
	O quick sort só pode ser executado para um tamanho de conjunto de dados máximo igual 
a 1000, pois mais do que isso o uso de memória pelo algoritmo é muito grande.
O limite máximo dependerá da memória disponível, não sendo limitado ao valor de 1000.
Questão 5/10 - Estrutura de Dados
A complexidade de um algoritmo pode ser mensurada matematicamente em termos de uma função de custo do algoritmo.
Acerca da função custo de um algoritmo, assinale a alternativa CORRETA:
Nota: 10.0
	
	A
	A ordem de como os dados de entradas estão organizados não tem impacto no 
desempenho do algoritmo em tempo de execução.
Tem impacto. Conforme mostrado na AULA 1 – TEMA 2.
	
	B
	O custo matemático de um algoritmo é dado, exclusivamente, pelo custo de tempo 
de execução de um algoritmo.
É dado pelo tempo de execução e pelo uso de memória, embora este segundo não esteja 
sendo investigado em nossa disciplina.
	
	C
	O custo matemático de tempo de execução de um algoritmo pode ser mensurado através 
da contagem de instruções em uma linguagem de alto nível.
Você acertou!
AULA 1 – TEMA 2. CORRETO.
	
	D
	A função custo é dada em função do tamanho do conjunto de dados de entrada n, ou seja, 
em função da quantidade de instruções a serem executadas.
n representa a quantidade de dados a serem manipulados, como por exemplo, um vetor de entrada 
de tamanho n. E não significa as instruções contadas.
	
	E
	O custo de tempo de execução de um algoritmo corresponde a quantos núcleos paralelos 
o algoritmo está sendo executado.
Tempo de execução significa o quão rápido um algoritmo executa para resolver um problema. 
Não tendo relação com o paralelismo.
Questão 6/10 - Estrutura de Dados
O algoritmo de ordenação por intercalação, também conhecido como merge sort, é um dos algoritmos estudados na AULA 2.
Acerca deste algoritmo, assinale a alternativa CORRETA.
Nota: 10.0
	
	A
	A complexidade do merge sort é O(logn), pois o algoritmo trabalhacom o princípio 
de dividir para conquistar.
O(n.logn), pois temos duas funções.
	
	B
	O processo do merge sort consiste em dividir uma estrutura de dados de tamanho n 
(um vetor por exemplo) em 4 partes e ordenar estar partes, agregando-as posteriormente.
O processo do merge sort consiste em dividir uma estrutura de dados de tamanho 
n (um vetor por exemplo) em n partes de tamanho unitário.
	
	C
	Ao dividir o conjunto de dado em duas partes menores, o merge sort sempre 
calcula a posição central da ruptura, que é dada pela média entre os valores posição 
inicial com a posição final, arredondando para cima.
É feito um truncamento somente da parte inteira.
	
	D
	A intercalação é realizada utilizando um vetor auxiliar para ir armazenando os dados 
que vão sendo ordenados naquele momento.
Você acertou!
AULA 2 – TEMA 3. Figura 10.
	
	E
	A função merge sort pode ser implementada de forma recursiva, ou seja, realizando 
chamadas de si mesma até que o conjunto de dados seja indivisível. A ordenação só 
ocorre quando as partes menores forem agregadas novamente.
A ordenação ocorre nas partes menores e indivisíveis.
Questão 7/10 - Estrutura de Dados
Assuma um vetor de dimensão 10 com dados numéricos e inteiros colocados na seguinte ordem: 
| 05 | 07 | 08 | 14 | 24 | 29 | 56 | 77 | 78 | 88 |
Suponha que você deseja implementar um algoritmo de busca para localizar algum dado neste vetor já ordenado de maneira crescente. Você resolve testar a busca sequencial e a busca binária.
Acerca destes algoritmos e analisando o vetor acima, assinale a alternativa CORRETA:
Nota: 10.0
	
	A
	No algoritmo de busca sequencial, o valor 24 seria localizado na 6ª tentativa, se 
fizermos uma varredura da esquerda para a direita.
Na 5ª tentativa.
	
	B
	No algoritmo de busca binária, o valor 24 seria localizado na 3ª tentativa.
Na 1ª tentativa.
	
	C
	No algoritmo de busca sequencial, o valor 77 seria localizado mais rapidamente que 
se comparado com a busca binária.
Binária se sairia mais rápida.
	
	D
	No algoritmo de busca sequencial, o valor 07 seria localizado mais rapidamente que se 
comparado com a busca binária.
Você acertou!
CORRETO. Levará menos iterações.
	
	E
	Em nenhum cenário de busca o algoritmo sequencial irá localizar o valor antes da busca 
binária.
É possível que sim, a sequencial ache antes. Dependerá o valor buscado e onde ele se localizado 
no vetor.
Questão 8/10 - Estrutura de Dados
Chamamos de análise assintótica de algoritmos quando encontramos a complexidade de um algoritmo de maneira aproximada através de uma curva de tendência. Este tipo de análise e é a mais adotada para compararmos desempenho de algoritmos.
Acerca da análise assintótica de um algoritmo, assinale a alternativa INCORRETA:
Nota: 10.0
	
	A
	Um algoritmo com três laços de repetição não encadeados contém uma complexidade 
assintótica, para o pior caso, O(n).
	
	B
	Na análise assintótica, fazemos o conjunto de dados de entrada da função custo tender 
ao infinito, mantendo na equação somente o termo de maior grau, ou seja, aquele que 
mais cresce na equação.
	
	C
	Um algoritmo com três laços de repetição aninhados contém uma complexidade 
assintótica, para o pior caso, O(n³).
	
	D
	A complexidade assintótica para o pior caso, também conhecida como BigO, representa 
o pior cenário para um algoritmo, ou seja, quando mais instruções precisam ser executadas, 
levando mais tempo para finalizar a execução.
	
	E
	A complexidade assintótica para o pior caso de um algoritmo contendo dois laços de 
repetição aninhados, sendo que o segundo laço só será executado caso uma condicional 
simples seja verdadeira, será O(n).
Você acertou!
AULA 1 – TEMA 3. O pior caso (BigO) nos diz que todas as linhas devem ser executadas, 
ou seja, a condicional será sempre verdadeira, e ambos laços de repetição serão sempre executados, 
sendo assim, complexidade O(n²).
Questão 9/10 - 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: 10.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 10/10 - 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: 10.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.