Atividade Unidade 2

Prévia do material em texto

· Pergunta 1
0 em 1 pontos
	
	
	
	A tarefa de obter uma expressão matemática para avaliar o tempo de execução de um algoritmo não é simples, mesmo considerando-se uma expressão aproximada (SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de Dados e seus Algoritmos . 3. ed. Rio de Janeiro: Ltc, 2010). As expressões são representadas por meio de funções, no qual podemos descobrir a complexidade do algoritmo. Desta forma, analise as afirmativas abaixo.
 
                                I.            O algoritmo Bubble Sort não é um algoritmo estável.  
                             II.            O algoritmo Bublle Sort , possui complexidade O ( n ) para o melhor caso e O ( n 2 ) para o pior caso.
                          III.            O algoritmo Quick Sort possui complexidade O ( n log ( n )) para o melhor caso.
                          IV.            O algoritmo Quick Sort é um algoritmo estável.
Julgue e assinale se as afirmativas acima são verdadeiras (V) ou falsas (F).
	
	
	
	
		Resposta Selecionada:
	 
. F, V, V, F.
	Resposta Correta:
	 
.F, V, V, F.
	Comentário da resposta:
	Sua resposta está incorreta. A estabilidade se dá quando um algoritmo em sua execução não altera os dados quando são iguais. Um exemplo de algoritmo estável é o Insertion-Sort, porém esse algoritmo não é o único algoritmo estável que aprendemos na apostila.
	
	
	
· Pergunta 2
1 em 1 pontos
	
	
	
	A complexidade de um algoritmo se dá por meio das funções que são implementadas no código. Cada laço de repetição aumenta o tempo de execução da aplicação. Assinale a complexidade do melhor caso do algoritmo de ordenação Bubble Sort.
	
	
	
	
		Resposta Selecionada:
	 
. O(n).
	Resposta Correta:
	 
. O(n).
	Comentário da resposta:
	Resposta correta. O Algoritmo é um método mais simples, de fácil implementação e apesar da sua eficiência diminuir `a medida que os dados aumentam, ainda é um dos algoritmos mais utilizados para ordenação.
	
	
	
· Pergunta 3
1 em 1 pontos
	
	
	
	Algoritmos de ordenação são exemplos de algoritmos desenvolvido para solucionar de forma mais rápida e eficiente alguns problemas com o auxílio de um computador. Existem diversos métodos que podem ser utilizados, cada método tem procedimentos distintos para resolver uma determinada tarefa. Assinale a alternativa a seguir que pode ser considerados métodos de ordenação?
	
	
	
	
		Resposta Selecionada:
	 
. bubble sort, selection sort, merge sort, quick sort.
	Resposta Correta:
	 
.bubble sort, selection sort, merge sort, quick sort.
	Comentário da resposta:
	Resposta correta. Existem vários algoritmos de ordenação, alguns mais simples e outros mais sofisticados. Os métodos mais simples são mais adequados para organizar poucos dados, diferente dos mais sofisticados que são mais complexos e organizam uma quantidade de dados maior de forma mais eficiente.
	
	
	
· Pergunta 4
1 em 1 pontos
	
	
	
	Ordenar “corresponde ao processo de rearranjar um conjunto de objetos em ordem ascendente ou descendente. O objetivo principal da ordenação é facilitar a recuperação posterior de itens do conjunto ordenado”. (ZIVIANI, Nivio. Projeto de Algoritmos: com implementações em JAVA e C++. Cengage Learning Editores, 2012).  Analise as afirmativas abaixo sobre os conceitos de algoritmos de ordenação.
 
                                I.            Uma vantagem de entender os métodos de ordenação por meio do pseudocódigo faz a transformação do algoritmo para linguagens de programação torna atividade mais simples.
                             II.            O algoritmo Bublle Sort, possui complexidade O ( n -1) para o melhor caso e O ( n 2) para o pior caso.
                          III.            O algoritmo Quick Sort é baseado no fato de que as interações devem ser preferencialmente empregadas para pares de elementos que guardem entre si distâncias grandes, com a finalidade de se conseguir uma eficiência maior.
                          IV.            O algoritmo Selection Sort, possui complexidade O ( n) em todos os casos de complexidade, ou seja, melhor caso, médio caso e pior caso.  (F)
 
Julgue e assinale se as afirmativas acima são verdadeiras (V) ou falsas (F).
	
	
	
	
		Resposta Selecionada:
	 
.V, F, V, F.
	Resposta Correta:
	 
.V, F, V, F.
	Comentário da resposta:
	Resposta correta. Podemos utilizar código mais simples para representar conceitos, ou utilizar formas genéricas de escrever um algoritmo, utilizando uma linguagem simples.
	
	
	
· Pergunta 5
1 em 1 pontos
	
	
	
	A complexidade de um algoritmo pode ser calculada por meio da complexidade temporal e espacial, sendo na primeira o cálculo do tempo que as instruções levam para serem executadas (utilizando as funções), e na sequência, o espaço na memória que o algoritmo utiliza.
Assinale a alternativa correta que descreva o algoritmo de ordenação que contêm como complexidade O( n 2) para o melhor caso, médio caso e pior caso.
	
	
	
	
		Resposta Selecionada:
	 
. Selection Sort.
	Resposta Correta:
	 
.Selection Sort.
	Comentário da resposta:
	Resposta correta. O Algoritmo é estável, no qual não altera a ordem dos dados iguais e pode organizar os elementos assim que os recebe, sem necessitar organizar depois de receber todos os dados.
	
	
	
· Pergunta 6
1 em 1 pontos
	
	
	
	O método de ordenação Insertion Sort, também conhecido como método de inserção, é classificado como um método simples. O funcionamento do método é percorrer os elementos e à medida que avança vai ordenando. Utilize esse algoritmo para organizar em ordem crescente um array
unidimensional, contendo os números [5,3,8,2,6].
Assinale a alternativa a seguir que apresente a quantidade de trocas que serão realizados para ordenar o array utilizando o algoritmo Insertion Sort.
	
	
	
	
		Resposta Selecionada:
	 
.5 trocas.
	Resposta Correta:
	 
.5 trocas.
	Comentário da resposta:
	Resposta correta. O algoritmo Insertion Sort se limita em a cada passo a partir do segundo elemento selecionar o próximo item da sequência e colocá-lo no local apropriado.
	
	
	
· Pergunta 7
1 em 1 pontos
	
	
	
	O método de ordenação Bubble Sort , também conhecido como método bolha, é classificado como um método simples e também um dos métodos mais utilizados. Utilize esse algoritmo para ordenar um array unidimensional, contendo os números [6,5,0,3,2] em ordem crescente.
Assinale a alternativa a seguir que apresente a quantidade de comparações e trocas que serão realizados para ordenar o array utilizando o algoritmo Bubble Sort .
	
	
	
	
		Resposta Selecionada:
	 
.10 comparações e 8 trocas.
	Resposta Correta:
	 
.10 comparações e 8 trocas.
	Comentário da resposta:
	Resposta correta. O algoritmo Bubble Sort se limita em percorrer n vezes os elementos do array do início ao fim, sem interrupção, trocando a posição dos elementos sempre que estiverem desordenados.
	
	
	
· Pergunta 8
1 em 1 pontos
	
	
	
	Existem algoritmos de ordenação mais complexos e algoritmos mais simples de implementar.  Os algoritmos Merge e Quick são considerados algoritmos complexos, sendo mais eficientes e executam as aplicações em tempo menor que os algoritmos mais simples. Analise as afirmativas abaixo sobre os algoritmos de ordenação:
                                I.            Os métodos Quick Sort e Merge Sort utilizam a estratégia dividir para conquistar.
                             II.            O método de ordenação Quick Sort aloca o maior elemento para o final do array para garantir que os dados fiquem em ordem decrescente.
                          III.            No pior caso, o algoritmo bolha executa n 2 operações para ordenar um array de n elementos.
                          IV.            O algoritmo de ordenação por inserção possui o menor número de trocas quando o array está ordenado de forma inversa à ordem do procedimento.
Julgue e assinale se as afirmativas acima são verdadeiras (V) ou falsas (F).
	
	
	
	
		Resposta Selecionada:
	 
. V, F, V, F.
	Resposta Correta:
	 
. V, F, V, F.
	Comentário da resposta:Resposta correta. Tanto o Merge quanto o Quick possuem no melhor caso e no médio caso a complexidade O (n log n). Porém o Quick no pior caso não é tão eficiente quanto o Merge.
	
	
	
· Pergunta 9
1 em 1 pontos
	
	
	
	As estruturas de dados são aplicadas aos algoritmos para melhorar o tempo de execução nas aplicações. Cada método de ordenação possui um conceito e uma forma de manipular os dados. O método utilizado no algoritmo abaixo é eficiente para resolver problemas com poucos dados e a sua complexidade é O (n) no melhor caso e O (n 2) no pior caso. Analise o código abaixo sobre o método de ordenação citado acima.
Qual a alternativa que corresponde aos conceitos de ordenação descritos acima e ao código na imagem representam o algoritmo de ordenação:
	
	
	
	
		Resposta Selecionada:
	 
. Insertion Sort.
	Resposta Correta:
	 
. Insertion Sort.
	Comentário da resposta:
	Resposta correta. O algoritmo é estável, mas possui um alto custo de movimentação dos elementos do array.
	
	
	
· Pergunta 10
1 em 1 pontos
	
	
	
	Algoritmos são desenvolvidos para facilitar a nossa vida e fornecer respostas de maneira rápida e eficiente. Podemos descrever a complexidade que um algoritmo possui analisando as funções existentes no código. O algoritmo Quick Sort possui complexidade ______________ no melhor caso, ___________ no caso médio e _____________ no pior caso.
Assinale a alternativa que imprima a complexidade dos algoritmos na ordem correta.
	
	
	
	
		Resposta Selecionada:
	 
.O (n log n), O (n log n), O (n 2).
	Resposta Correta:
	 
.O (n log n), O (n log n), O (n2).
	Comentário da resposta:
	Resposta correta. O Algoritmo Quick-Sort trabalha com eficiência e com uma base de dados grande, dividindo o array em pequenos arrays
com base em um elemento chamado pivô.