Question

7) O algoritmo counting sort constitui uma alternativa eficiente para a ordenação de dados em memória, já que ele demanda um tempo computacional da ordem de Θ(n). No entanto, ele faz maior uso do espaço em memória, por precisar que vetores auxiliares sejam criados durante sua execução.



Considerando a execução do algoritmo sobre um vetor A = {4, 1, 5, 0, 1, 6, 5, 1, 5, 3}, em que todos os valores são menores que k = 7, analise as afirmativas a seguir.



I. Após o primeiro laço que inicializa cada posição do vetor auxiliar C com zero, o segundo laço finaliza com o vetor C = { 1, 3, 0, 1, 1, 3, 1 }.

II. Ao término do terceiro laço, o vetor auxiliar C definido no corpo do algoritmo terá os seguintes valores armazenados {0, 3, 3, 4, 5, 8, 9}.

III. A primeira iteração do último laço do algoritmo faz com que o valor 3 seja atribuído à posição 4 do vetor A.

IV. A posição 4 corresponde à última posição do vetor A a ser preenchida pelo laço final do algoritmo.



Está correto apenas o que se afirma em:




a) III e IV.


b) I, II e III.


c) I e IV.


d) II e III.


e) I e II.

Answer 1

Resposta:

é

B Resposta

Explicação:

Deus abençoe você sempre ilumine sempre

Answer 2

Resposta:

I,II E III

Explicação:

Resposta certa. O segundo laço do algoritmo é responsável por contabilizar a frequência de cada valor do vetor A. Então, como existem: 1 ocorrência de 0; 3 ocorrências de 1; 0 ocorrências de 2; 1 ocorrência de 3; 1 ocorrência de 4; 3 ocorrências de 5 e 1 ocorrência de 6, o vetor C terá os seguintes valores, ao término do segundo laço {1, 3, 0, 1, 1, 3, 1}. O terceiro laço realiza uma soma acumulada de cada posição. Porém, como o primeiro índice do vetor é 0, as somas devem ser decrementadas de 1. Neste caso, ao término desse laço, o valor de C será {0, 3, 3, 4, 5, 8, 9}. A primeira iteração do último laço posiciona o elemento 3 na quarta posição de A, já que C[ 3 ] = 4. O último valor a ser posicionado no vetor A é o elemento 4. Mas como C[ 4 ] = 5, ele é alocado na posição 5 do vetor.