APOL 01 ESTRUTURA DE DADOS

Prévia do material em texto

APOL OBJETIVA 01 – ESTRUTUTA DE DADOS 
Questão 1/5 - 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: 0.0
	
	A
	A complexidade do merge sort é O(logn), pois o algoritmo trabalha com 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.
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 2/5 - Estrutura de Dados
O segundo assunto de nossa disciplina diz respeito a algoritmos de ordenação de dados.
Acerca deste assunto, assinale a alternativa INCORRETA:
Nota: 20.0
	
	A
	Algoritmos de ordenação são empregados com o objetivo de ordenar conjuntos de
 dados a partir de uma determinada métrica, como por exemplo, ordenar nomes de pessoas
 em ordem alfabética crescente.
	
	B
	Existem os mais diversos algoritmos de ordenação, sendo que cada um deles apresentará 
uma complexidade distinta em tempo de execução e de uso de memória e, 
portanto, devem ser minuciosamente escolhidos de acordo com a aplicação.
	
	C
	A permuta de grandes quantidades de dados para ordenação tende a ser custoso 
computacionalmente. O uso de variáveis ponteiros servem para auxiliar e otimizar 
este processo ordenando somente os endereços ao invés de todo o conjunto de dados.
	
	D
	Um algoritmo de ordenação é um método que descreve como é possível colocar, 
em uma ordem específica, um conjunto de dados qualquer.
	
	E
	A lógica algorítmica de cada método de ordenação difere para cada tipo de estrutura de
 dados que se deseja manipular.
Você acertou!
AULA 2 – TEMA 1. A estrutura de dados não muda a lógica de funcionamento do algoritmo de
 ordenação, só muda a estrutura a ser manipulada.
Questão 3/5 - 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: 0.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).
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 4/5 - 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: 0.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.
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/5 - 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: 0.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
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²).