Questão EPO - Merge sort

As estratégias de divisão e de conquista são utilizadas pelos algoritmos de ordenação

a) Selection sort e Insertion sort.
b) Selection sort e Bubble sort.
c) Quick sort e Merge sort.
d) Bubble sort e Bucket sort.
e) N.D.A

Fonte:
Questão 52 - Caderno de Prova D04, Tipo 001 MPE-RN - Analista de Tecnologia da Informação
http://www.questoesdeconcursos.com.br/provas/fcc-2010-mpe-rn-analista-de-tecnologia-da-informacao-banco-de-dados

Questão EPO - Merge sort

Uma fabrica de Software foi contratada para desenvolver um produto de análise de riscos. Em determinada funcionalidade desse software, é necessário realizar a ordenação de um conjunto formado por muitos números inteiros. Que algoritmo de ordenação oferece melhor complexidade de tempo (Big O notation) no pior caso?

a) Merge Sort
b) Insertion Sort
c) Bubble Sort
d) Quick Sort
e) NDA.

Referencia:
http://www.questoesdeconcursos.com.br/provas/cesgranrio-2010-bacen-analista-do-banco-central-area-1

Questão EPO - Merge sort

Sobre o  Merge Sort, assinale a alternativa INCORRETA:

a) É um algoritmo de abordagem dividir para conquistar;
b) É um algoritmo recursivo;
c) Divide o vetor a ser ordenado aleatoriamente;
d) Divide o vetor a ser ordenado ao meio
e) NDA.

Fonte: http://www.inf.ufsc.br/~ronaldo/ine5384/18-OrdenacaoDados4.pdf

Questão EPO - Merge sort

No desenho abaixo retirado do vídeo do Merg Sort você terá o inicio do vetor e o final, assinale a alternativa que complemente o processo de comparação do Merg Sort dado pelo desenho.

a) Separa em dois  grupos iguais e mostra o subgrupo dividido em pares: exemplo=>1º Grupo (2 | 9) e (5 | 6) conquista –verifica o 1ª elemento com o 1ª elemento e verifica o 2ª elemento com o 2ª elemento; conclusão do 1º Grupo (2 | 5 | 6 | 9 ). 2º Grupo (3 | 10 ) e   ( 1 | 7 ) conquista –verifica o 1ª elemento com o 1ª elemento e verifica o 2ª elemento com o 2ª elemento; conclusão do 2º Grupo(1 | 3 | 7| 10)

b) ) Separa em dois  grupos iguais e mostra o subgrupo dividido em pares: exemplo=>1º Grupo (22 | 9) e (5 | 6) conquista –verifica o 1ª elemento com o 1ª elemento; conclusão do 1º Grupo (2 | 5 | 6 | 9 ). 2º Grupo (3 | 10 ) e   ( 10 | 7 ) conquista –verifica o 1ª elemento com o 1ª elemento; conclusão do 2º Grupo(1 | 3 | 7| 10)

c) ) Separa em dois  grupos iguais e mostra o subgrupo dividido em pares: exemplo=>1º Grupo (20 | 99) e (5 | 6) conquista –verifica o 2ª elemento com o 2ª elemento; conclusão do 1º Grupo (2 | 5 | 6 | 9 ). 2º Grupo (3 | 10 ) e   ( 1 | 7 ) conquista –verifica o 1ª elemento com o 1ª elemento e verifica; conclusão do 2º Grupo(1 | 3 | 7| 10)

d) ) Separa em dois  grupos iguais e mostra o subgrupo dividido em pares: exemplo=>1º Grupo (2 | 9 | 50) e (5 | 6) conquista –verifica o 1ª elemento com o 1ª elemento e verifica o 2ª elemento com o 2ª elemento; conclusão do 1º Grupo (2 | 5 | 6 | 9| 50 ). 2º Grupo (3 | 10 ) e   ( 1 | 7 ) conquista –verifica o 1ª elemento com o 1ª elemento e verifica o 2ª elemento com o 2ª elemento; conclusão do 2º Grupo(1 | 3 | 7| 10)

e)N.D.A

Fonte: Video do Grupo Meger Sort

Questão EPO - Merge sort

Analisando o seguinte vetor de cinco posições, como o merge sort dividiria o vetor na próxima iteração.

a)

b)

c)

d)

e) N.D.A

Retirado do conteúdo visto na apresentação de merge sort.

Questão EPO - Merge sort

O merge sort utilizada à abordagem dividir para conquistar, como é realizada está divisão e conquista?

a) Divide de maneira aleatória e  após  a junção das partes é realizada a ordenação do vetor.
b) Divide o vetor ao meio, realiza a ordenação das partes e depois realizada a versão.
c) O merge sort não realiza divisões no método de ordenação.
d) Realizada divisões em pares não ordenando os pares para realizar junção.
e) Nda.

Questão EPO - Merge sort

Quanto ao merge sort é correto afirmar que:

a) cria uma sequência ordenada a partir de duas outras também ordenadas

b) a cada passagem no vetor, flutua para o topo o maior elemento da sequência

c) o algoritmo executa n2 operações relevantes

d) consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores"

e) nda

Questão EPO - Merge sort

Quais as “Etapas” do Merge Sort?

a) Dividir em duas sequências iguais e Conquistar em uma única sequência as subsequências divididas anteriormente;

b) Dividir em duas sequências iguais ou não, Classificar e Conquistar ordenando na lista original.

c) Classificar em duas sequências as subsequências divididas anteriormente, Dividir em duas sequências e Conquistar;

d) Conquistar em uma única sequência as subsequências divididas anteriormente, Classificar e Dividir em duas sequências;

e) NDA;

Fonte:
http://cavmelo.files.wordpress.com/2010/11/merge-sort.pdf

Questão EPO - Merge sort

Sobre o Merge sort é correto afirmar que:

I. Usa como abordagem o “Dividir e consquistar”;
II. Divide o vetor em 2(sub-vetores), somente uma vez;
III. Eficiente tanto em vetores grandes quanto em pequenos;
IV. Faz uso de um array auxiliar, gerando um gasto extra de memória;
V. Caso o vetor tenha  tamanho ímpar, um  elemento será dispensado;

a) I,II e IV
b) I e IV
c) I,IV e V
d) I, III e IV
e) NDA

Fonte:
Usado como base o que foi estudado para se fazer o trabalho.

Questão EPO - Merge sort

Analise a seguinte aplicação do Merge Sort e identifique qual das aternativas esta correta.

Sequencia 3  2  4  9  12  7

Passo 1: 3 2 4 9 12 7

Passo 2: 3 2 4 9 12 7

Passo 3: 3 2 4 9 12 7

Passo 4: 2 3 4 9 12 7

Passo 5: 2 3 4 9 12 7

Passo 6: 2 3 4 7 9 12

a) A sequencia esta ordenada.
b) O Passo 5 possui uma irregularidade.
c) A tecnica usada não é Merge Sort.
d) a e b estão corretas.
e)N.D.A

Fonte:
Bolada com o conhecimento adquirido em sala.

Questão EPO - Merge sort

Quais alternativas FALSAS sobre Merge Sort

I- Não usa o método "Dividir para conquistar".
II- Não utiliza memória adicional para execução.
III- OS subvetores gerados podem ter número de elementos diferentes.
IV- Tem um alto desempenho com grande quantidade de dados.

a) I e IV
b) I e III
c) I e II
d) Somente a I
e) N.D.A.

Questão EPO - Merge sort

As estratégias de divisão e de conquista são utilizadas pelos algoritmos de ordenação

a) Selection Sort e Insertion Sort
b) Selection Sort e Buble Sort.
c) Quick sort e Merge Sort.
d) Bubble sort e Bucket Sort.
e) Nda.

Referencia:
http://www.questoesdeconcursos.com.br/questoes/eccbd7ac-72

Questão EPO - Merge sort

Considere a ilustração abaixo e assinale a alternativa correta:

a) A figura demonstra fielmente o procedimento de mergesort para ordenar os elementos 8, 4, 1,5.
b) A figura contém um erro na parte de divisão, pois a segunda linha não deveria ser dividida em duas partes
c) A figura contém um erro na parte de junção, pois a quarta linha não deveria ser agrupada em duas partes
d) O procedimento na figura é ineficiente, pois esta utilizando mais passos que o algoritmo mergesort realmente precisa para ordenar um vetor de 4 posições.
e) N.D.A

Fonte:
Questão mergesort baseada no artigo “Algoritmos de ordenação” de Carlos Torrão, João Martins e Maria Couceiro

Questão EPO - Merge sort

Indique a incorreta:

a) É um algoritmo de ordenação
b) Subdivide uma ordenação para facilitar a ordenação
c) Escolhe um número aleatoriamente para a partir dele ordenar o resto
d) Usa a teoria de “Dividir para Conquistar”
e) NDA

Fonte:
Slides usados em apresentação

Questão EPO - Merge sort

Dada as seguintes afirmativas:

I. “Merge sort é um algoritmo recursivo. Utiliza a técnica ‘Dividir para conquistar’ que em síntese vai subdividindo o vetor em metades para ordenação, para depois reuni-lo ordenado.”
II.  “Merge sort é muito parecido com o Bubble sort já que faz trocas da esquerda para a direita.    “
III. “É muito vantajoso pela rapidez e estabilidade, porém, utiliza muita memória já que tem que criar um vetor auxiliar para ordenação.”
IV. “Precisa de muitos nós para conseguir ficar nivelado.”

Assinale:
a) I, II e III
b) III somente
c) I e III somente
d) Todas as afirmativas estão corretas
e) N.D.A

Questão EPO - Merge sort

MergeSort(i,f)

    Dado um vetor A[i..f] de inteiros
    Devolve A com os elementos em ordem crescente.

{
 1    se (i-f > 0) então {
 2        m <- (i+f) div 2;
 3        MergeSort(i,m);
 4        MergeSort(m,f);
 5        para k de 1 até m-i+1 faça
 6            b[k] <- A[i+k-1];
 7        para l de m+1 até f faça
 8            c[l-m] <- A[l];
 9        k <- 1;
10        l <- 1;
11        b[m+1] <-  ∞;
12        c[f-m+1] <- ∞;
13        para r de i até f faça
14            se ( b[k] < c[l] ) { A[r] <- b[k]; k <- k+1;}
15            senão {A[r] <- c[l]; l <- l+1;}
    }
}

O número de comparações entre elementos do vetor A feitas por uma chamada de MergeSort(1,n),n>1 , é o número de comparações feitas recursivamente nas chamadas das linhas 3 e 4 mais o número de compações feitas na linha 14 ( pois o resultado de cada comparação determina um elemento de A), logo
Complete o tracejado:

a) 1 , 2
b) 3 , 4
c) 3 , 5
d) 5 , 7
e) NDA

Fonte:
http://anotacoesdeaula.wordpress.com/2011/02/10/bc1435-mergesort-solucao-exata-da-recorrencia/

Questão EPO - Merge sort

Quais das alternativas abaixo estão CORRETAS:

I.  O Merge Sort, ou ordenação por mistura, é um algoritmo de ordenação que usa a abordagem de “Dividir e conquistar”.
II. Sua idéia básica é criar uma sequência ordenada a partir de duas outras também ordenadas.
III.  A ordenação merge sort requer  apenas operações sem dar importância à ordem de entrada.
IV.  O merge sort utiliza uma estrutura de dados chamada merge para ordenar os elementos à medida que os insere na estrutura.

a) I e II.
b) I, II, III.
c) Todas.
d) Somente a III.
e) NDA.

Referência:
Slide de apresentação do grupo Merge Sort.

Questão EPO - Merge sort

É correto afirmar:

a) Merge sort fio um erro e nunca foi utilizado para estudos.
b) Tem um exelente desempenho com muitos dados.
c) Não muito utilizado por seu desempenho ser baixo.
d) Divide o vetor de dados e cria-se subvetores, sendo assim um metodo adaptivo.
d) N.D.A

Questão EPO - Merge sort

Baseado no método dividir e conquistar, o Mergesort é uma estrutura amplamente usada no contexto da estrutura de dados. Baseado nesta afirmação, julgue os itens à seguir:

(  ) 1. O Mergesort trabalha recursivamente.
(  ) 2. Só é possível aplicar o Mergesort em vetores com quantidades de  posições.
(  ) 3. Uma das vantagens do Mergesort é o fato de trabalhar com 2 arrays para organizar a  troca dos elementos.


a) Todas são verdadeiras.
b) Apenas uma é verdadeira.
c) Duas são verdadeiras.
d) Duas são falsas.
e) NDA.

Questão EPO - Merge sort

O Merge Sort é um algoritmo de ordenação que se utiliza de recursão para ordenar os elementos de um vetor, assim como o Bubble Sort e o Quick Sort, entre outros. Sobre o Merge Sort é correto afirmar que:

a) O merge Sort é um algoritmo que possui uma única forma de ordenação que consiste em dividir a lista inicial em duas listas similares cada uma com um tamanho igual à metade da lista original , porém não realiza a reunião novamente das sub-listas que separou. Por isso é considerado como um algoritmo de complexidade alta, ou seja, O(n log n)

b) Uma das vantagens do uso do Merge sort é a facilidade, que esse método de ordenação tem, de implementação.  A desvantagem é que requer o dobro de memória, ou seja, precisa de uma lista com as mesmas dimensões da lista que está a ser classificada.

c) O Merge Sort é um algoritmo de ordenação de complexidade de caso médio, ou seja, O(n log n), efetuando a ordenação do vetor escolhendo um pivô aleatoriamente depois dividindo a lista inicial e ordenando seus membros comparando-os com esse pivô.

d) O Merge Sort é um algoritmo que realiza a ordenação da lista da seguinte forma: é feito uma lista com os elementos de posição ímpar (a1, a3, a5, ...) e outra com os elementos pares (a2, a4, ...), porém sem o uso adicional de memória, já que esse algoritmo não cria uma lista adicional para conter os dados subdivididos do vetor que está colocando em ordem.

e) N.D.A.

Fonte:
http://w3.ualg.pt/~hshah/ped/Aula%2014/merge_final.html