ATIVIDADE 2 - ESTRUTURA DE DADOS

Prévia do material em texto

ESTRUTURA DE DADOS – ATIVIDADE 2
QUESTÃO 1
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.
· Insertion Sort.
· Merge Sort.
· Selection Sort.
· Bubble Sort.
· Quick Sort.
Resposta correta. O algoritmo é estável, mas possui um alto custo de movimentação dos elementos do array.
QUESTÃO 2
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).
· V, V, V, F.
· V, F, V, F.
· F, V, V, V.
· V, F, V, V.
· F, F, V, V.
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.
QUESTÃO 3
Cada algoritmo possui uma complexidade para resolver problemas, no qual é analisado as funções implementadas no algoritmo. Assinale a complexidade do caso médio do algoritmo de ordenação Insertion-Sort.
· O(n log n).
· O(log n);
· O(n²).
· O(n 3)
· O(n).
· 
Resposta correta. O Algoritmo tem como vantagem ser estável, no qual não altera a ordem dos dados iguais e pode organizar os elementos assim que os recebe, como quando uma pessoa está organizando as cartas em um jogo de baralho
QUESTÃO 4
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 log n), O (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), O (n log n), O (n 2).
· O (n log n), O (n log 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ô.
QUESTÃO 5
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?
· boolean sort, selection sort, insertion sort.
· chell sort, selection sort, bubble sort.
· margie sort, boolean sort, quick sort.
· selection sort, merge sort, array, insertion sort.
· bubble sort, selection sort, merge 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.
QUESTÃO 6
A complexidade de um algoritmo é calculada por meio da complexidade temporal e espacial, sendo na primeira o cálculo do tempo que as instruções levam para serem executadas em uma aplicação (utilizando as funções), e na sequência, o espaço na memória que o algoritmo utiliza enquanto é executado. Existem algoritmos que necessitam de muito mais espaço, como o Algoritmo _____________. Assinale a alternativa que complete o nome de algoritmo que exige mais espaço na memória.
· Bubble Sort.
· Insertion Sort.
· Quick Sort.
· Merge Sort.
· Selection Sort.
Resposta correta. Um algoritmo estável, muito indicado para organizar uma grande quantidade de dados, com um desempenho de (n log n) para todos os casos. Sendo muito eficiente quando levamos em conta o tempo de execução do algoritmo.
QUESTÃO 7
O algoritmo Merge-Sort, faz o uso da estratégia dividir para conquistar. Assim, sua ideia é dividir o conjunto de dados em subconjuntos, reorganiza cada subconjunto e depois intercala os resultados. De acordo com o método descrito, assinale a alternativa que descreva a complexidade do algoritmo no melhor caso e no pior caso
· Melhor caso: O (n log n) Pior caso: O (n) .
· Melhor caso: O (n) Pior caso: O (n 2).
· Melhor caso: O (n log n) Pior caso:  O (n 2).
· Melhor caso: O (n log n) Pior caso: O (n log n).
· Melhor caso: O (n log n) Pior caso: O (log n).
Resposta correta. Apesar de possuir um gasto extra de espaço de memória, o algoritmo é indicado para aplicações que possuem restrição de tempo. Podemos observar isso pela sua complexidade.
QUESTÃO 8
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.
· Quick Sort.
· Selection Sort.
· Bubble Sort.
· Insertion Sort.
· Merge 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
QUESTÃO 9
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.
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.
QUESTÃO 10
O método de ordenação Quick Sort, é classificado como um método complexo e não estável. Nesse algoritmo se faz necessária a escolha de um elemento como pivô. Utilize esse algoritmo para ordenar um array unidimensional, contendo os números [5,2,9,6,3] em ordem crescente. Considere o número 9 e, na sequência, o número 3 como pivô.
Assinale a alternativa a seguir que apresente a quantidade de trocas que serão realizados para ordenar o array utilizando o algoritmo Quick Sort.
· 4 trocas.
· 6 trocas.
· 5 trocas.
· 2 trocas.
· 3 trocas.
Resposta correta. O algoritmo utiliza a estratégia dividir para conquistar e quando ele vai reorganizando os dados ocorre a troca dos elementoscom o pivô.