Questão 2056891

• Banca: COMVEST UFAM
• Órgão: UFAM
• Ano: 2016
• Provas: COMVEST UFAM - 2016 - UFAM - Técnico em Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca

O mergesort é um algoritmo de ordenação do tipo dividir-para-conquistar. Sua ideia básica consiste em dividir o problema em vários subproblemas, e resolver esses subproblemas por meio da recursividade e, em seguida,após todos os subproblemas terem sido resolvidos,ocorre a conquista, que é a união das resoluções dos subproblemas. O algoritmo mergesort, apresentado em seguida, está codificado em C/C++.Esse algoritmo ordena o vetor de inteiros a[p],..., a[r](onde, p<r) usando um vetor auxiliar b[p],..., b[r].O vetor a[ ] é dividido recursivamente ao meio em duas instâncias menores, que são ordenadas e então colocadas

juntas, ordenando todo o vetor. No código estão faltando as linhas que fazem a divisão por recursão (linhas 7 e 8) e as linhas que concretizam a fase de conquista, unindo todas as intercalações no vetor principal (linhas 11 e 12).

1.   voidmergesort(int a[], int p, int r)

2.   {

3.   inti,j,k,m;

4.   if (r > p)

5.   {

6.   m = (r + p)/2;

7.   …

8.   …

9.   for (i = m+1; i> p; i--) b[i-1] = a[i-1];

10. for (j = m; j < r; j++) b[r+m-j] = a[j+1];

11.  ...

12.  ...

13.  }  

14.  }

As linhas 7,8, 11 e 12, que complementam o código do mergesort de maneira CORRETA, são:

• A. 7.mergesort(a, p, m);8.mergesort(a, m+1, r);…11.for (k = p; k <= r; k++)12. a[k] = (b[i]<b[j]) ? b[i++] : b[j--];
• B. 7.mergesort(a, p, m+1);8.sort(a, m+1, r);...11.for (k = m; k <= r; k--)12. a[k] = (b[i]<b[j]) ? b[i++] : b[j--];
• C. 7.mergesort(a, p, m);8.mergesort(a, m+1, r);…11.for (k = m; k <= m; k++)12. a[m] = (b[m]<b[j]) ? b[m++] : b[m--];
• D. 7.sort(a, p, m);8.sort(a, m+1, r);...11.for (k = p; k <= r; k++)12. a[k] = (b[i]<b[j]) ? b[i++] : b[j--];
• E. 7.sort(a, p, m);8.merge(a, m+1, r);...11.for(k = p; k <= r; k++)12. a[k] = (b[i]<b[j]) ? b[i++] : b[j--];

Gabarito: A

Comentários

• MergeSort trabalha com recursividade, logo, podemos eliminar as alternativas B), D) e E) que utilizam uma função sort não apresentada. Desta maneiras os itens B), D) e E) falham no requisito de recursividade.

  A letra C) não faz sentido nenhum no passo 11 pois se k = m e o loop incrementa até k <=m é o mesmo que dizer que esse laço for iria funcionar apenas quando k = m. Portanto, resposta letra A)

• Força Guerreiro!!!!!!