Atividade 2 (A2) - ESTRUTURA DE DADOS -(ANHEMBI MORUMBI UAM) CURTA SE LHE AJUDOU! D

Prévia do material em texto

Atividade 2 - ESTRUTURA DE DADOS
1. 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( n2) para o melhor caso, médio caso e pior caso.
. Bubble Sort.
. Merge Sort.
. Insertion Sort.
. Quick Sort.
. Selection Sort.
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.
2. Um algoritmo é uma sequência de passos que resolve algum problema ou alcança algum objetivo. E uma estrutura de dados definem como as informações serão organizadas na memória. Existem métodos ordenação que reduz o uso de memória e outros que aumentam o volume de memória utilizado. Sendo assim, analise a alternativa do método que possui como desvantagem um gasto extra de espaço de memória
. Bubble Sort.
. Merge Sort.
. Insertion Sort.
. Selection Sort.
. Quick Sort.
Resposta correta. O Algoritmo é estável, no qual não altera a ordem de dados iguais, e é indicado para aplicações que possuem restrição de tempo. Porém, uma grande desvantagem é possuir um gasto extra de espaço de memória
3. Para descobrir se um algoritmo de ordenação é eficiente, existe uma função que pode ser calculada, essa função é chamada de complexidade de algoritmo. Assim, cada algoritmo possui uma função para representar a sua complexidade, que pode ser analisada em vários cenários, como o melhor caso, médio caso e pior caso. Considere um array com 1000 elementos. Levando em conta que todos os elementos estão organizados de forma decrescente. Para ordenar esse array em ordem crescente utilizando o método Bubble Sort, assinale a alternativa que contem a complexidade para essa ordenação.
. O(n²).
.O(n log n).
. O(n).
. O(1).
. O(log n);
Resposta correta. Bubble-Sort é um dos métodos mais difundidos. A sua interação se limita em percorrer n vezes o array do início ao fim, sem interrupção, trocando a posição dos elementos sempre que estiverem desordenados.
4. 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:
. Selection Sort.
. Bubble Sort.
. Merge Sort.
. Insertion Sort.
. Quick Sort.
Resposta correta. O algoritmo é estável, mas possui um alto custo de movimentação dos elementos do array.
5. 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.
.14 comparações e 9 trocas.
.10 comparações e 8 trocas.
.10 comparações e 10 trocas.
.10 comparações e 9 trocas.
.14 comparações e 8 trocas.
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
6. 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.
.O (n), O (n log n), O (n 2).
. O (n log n), O (n log n), O (n log n).
. O (n), O (n log n), O (n log n)..
.O (n log n), O (n log n), O (n 2).
.O (n log n), O (n), O (n 2).
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ô.
7. 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 (n2) 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).
 ..V, F, F, F.
 .V, F, V, V.
.F, F, V, V.
.F, V, V, F.
. F, V, V, F.
Resposta correta. Existem algoritmos que são estáveis e outros não, esse conceito se refere ao fato do algoritmo não alterar os dados quando os mesmos são iguais
8. 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.
 
. O(n).
. O(n log n).
. O(n²).
. O(log n);
. O(1).
esposta correta. O Bubble Sort é um algoritmo simples, que se limita em percorrer diversas vezes o array do início ao fim, ou seja, percorre todos os n elementos do array.
9. Os algoritmos de ordenação foram desenvolvidos para auxiliar na ordenação e com isso melhor a eficiente de busca dos sistemas. O algoritmo na imagem abaixo está percorrendo o array
comparando todos os elementos até encontrar o menor elemento. Encontrando o menor elemento, o algoritmo irá posicioná-lo na posição inicial do array. A imagem abaixo está descrevendo o pseudocódigo de um algoritmo específico.
Analise os conceitos descritos acima e a imagem. Assinale a alternativa que corresponde aos conceitos e ao código acima:
. Insertion Sort.
. Bubble Sort.
. Quick Sort.
. Merge Sort.
. Selection Sort.
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.
10. 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?
. selection sort, merge sort, array, insertion sort.
. chell sort, selection sort, bubble sort.
. boolean sort, selection sort, insertion sort.
. bubble sort, selection sort, merge sort, quick sort.
. margie sort, boolean sort, quick sort.
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.