Estrutura de dados A2

Prévia do material em texto

Estrutura de dados A2 - FMU
Em aplicações encontramos problemas que muitas vezes precisam ser ordenados, essa ordenação facilita o tempo de resposta das aplicações. Ordenar pode ser, organizar os números em ordem crescente ou decrescente, organizar nomes em ordem alfabética, entre outros. Para organizar os elementos de uma forma eficiente se faz necessária a utilização de métodos como os algoritmos de ordenação. Assim, analise as afirmativas a seguir.
 
                                I.            Faz uma analogia do método com o modo que algumas pessoas ordem cartas de baralho em jogo.
                             II.            Método de ordenação mais complexo, possui a estratégia dividir para conquistar e seleciona um pivô para auxiliar na ordenação dos elementos.
                          III.            O algoritmo irá percorrer o array comparando todos os elementos até encontrar o menor elemento e alocar na posição inicial do array
                          IV.            A interação do método se limita em percorrer diversas vezes o array do início ao fim, sem interrupção, trocando a posição de dois elementos sempre que estiverem desordenados
As afirmativas apresentam diferentes possibilidades de sequências, sendo apenas uma alternativa correta:
a.
.Insertion-Sort, Selection-Sort, Quick_Sort, Bubble-Sort.
Resposta correta. Existem vários métodos que são utilizados para ordenar, alguns mais simples e outros mais complexos. Esses métodos são estrutura de dados e a utilização de métodos corretos nos algoritmos faz com que aumente a eficiência das aplicações.
b.
. Bubble-Sort., Selection-Sort, Quick_Sort, Insertion-Sort.
c.
. Insertion-Sort, Selection-Sort, Merge_Sort, Bubble-Sort.
d.
. Insertion-Sort, Bubble-Sort, Merge_Sort, Bubble-Sort.
e.
. Bubble-Sort., Merge-Sort, Quick_Sort, Insertion-Sort.
Feedback A resposta correta é: .Insertion-Sort, Selection-Sort, Quick_Sort, Bubble-Sort.
Texto da questão
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.
a.
. O(1).
b.
. O(log n);
c.
. O.
d.
. O(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.
e.
. O(n log n).
Feedback A resposta correta é: . O(n²).
Texto da questão
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 n2 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).
a.
.V, F, V, V.
b.
. F, V, V, V.
c.
. F, F, V, V.
d.
. V, F, V, F.
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.
e.
. V, V, V, F.
Feedback A resposta correta é: . V, F, V, F.
Texto da questão
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 (n2) 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).
a.
.V, V, V, F.
b.
.V, F, V, F.
c.
.V, F, F, F.
Sua resposta está incorreta. A complexidade do algoritmo se da devido as funções que possui, cada passo e cada função pode aumentar ou diminuir a sua eficiência. Revise a complexidade dos algoritmos na apostila.
d.
.F, F, V, V.
e.
.F, V, V, F.
Feedback A resposta correta é: .V, F, V, F.
Texto da questão
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:
a.
. 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.
b.
. Insertion Sort.
c.
. Merge Sort.
d.
. Quick Sort.
e.
.Bubble Sort.
Feedback A resposta correta é: . Selection Sort.
Texto da questão
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
a.
. Melhor caso: O 
Pior caso: O (n2).
b.
. Melhor caso: O (n log n)
Pior caso: O  .
c.
.Melhor caso: O (n log n)
Pior caso:  O (n2).
d.
.Melhor caso: O (n log n)
Pior caso: O (log n).
e.
Melhor caso: O (n log n)
Pior caso: O (n 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.
Feedback A resposta correta é: Melhor caso: O (n log n)
Pior caso: O (n log n).
Texto da questão
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.
a.
. O.
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.
b.
. O(n²).c.
. O(log n);
d.
. O(1).
e.
. O(n log n).
Feedback A resposta correta é: . O.
Texto da questão
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).
a.
.F, V, V, F.
b.
..V, F, F, F.
c.
.F, F, V, V.
d.
. 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.
e.
.V, F, V, V.
Feedback A resposta correta é: .F, V, V, F.
Texto da questão
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.
a.
. 4 trocas.
b.
. 3 trocas.
Resposta correta. O algoritmo utiliza a estratégia dividir para conquistar e quando ele vai reorganizando os dados ocorre a troca dos elementos com o pivô.
c.
. 5 trocas.
d.
.6 trocas.
e.
. 2 trocas.
Feedback A resposta correta é: . 3 trocas.
Texto da questão
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.
a.
.O , O (n log n), O (n2).
b.
. O , O (n log n), O (n log n)..
c.
. O (n log n), O (n log n), O (n log n).
d.
.O (n log n), O (n log n), O (n2).
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ô.
e.
.O (n log n), O , O (n2).
Feedback A resposta correta é: .O (n log n), O (n log n), O (n2).