Questão 1477552

• Banca: CONSULPLAN
• Órgão: TRE-MG
• Ano: 2015
• Provas: CONSULPLAN - 2015 - TRE-MG - Técnico Judiciário - Programação de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

A pesquisa de dados envolve a determinação da chave pesquisada estar ou não entre os dados pesquisados e, caso  esteja, que seja encontrada sua localização. Em computação, a pesquisa tem um papel importante, pois de posse do  campo chave a ser pesquisado fica mais fácil encontrar determinado arquivo, ou mesmo qualquer item que se queira  buscar.  Já  a  classificação  envolve  a  organização  dos  dados  em  uma  determinada  ordem,  por  exemplo:  crescente,  decrescente, ordem alfabética, numérica, entre outros. Acerca dos algoritmos de pesquisa e classificação, analise as  afirmativas a seguir.

I. Diz-se que o algoritmo 0(log n) tem um tempo de execução linear.
II. A pesquisa binária executa em 0(log n) vezes, pois cada passo remove metade dos elementos restantes. 
III. O algoritmo de classificação por inserção executa no tempo 0(n²), no pior caso e no caso médio. 
IV.No pior caso, a primeira chamada à classificação por intercalação tem de fazer 0(n) comparações para preencher os n slots no array final. 

Estão corretas apenas as afirmativas 

• A. I e II.
• B. II e III.
• C. II e IV.
• D. III e IV.

Gabarito: C

Comentários

• Pra mim, o gabarito deveria ser B.
  
  IV- classificação por intercalação é o mesmo que MergeSort. Logo deveria ser O(nlogn) para preencher os slots do array final.
  
  Alguém comenta?

• Letra Correta B)

  Algoritmos por inserção é somente o "Insertion Sort" que possui complexidade 

  Melhor Caso O(n) 

  Caso Médio O(n²) 

  Pior Caso O(n²)

• Também acredito, quanto ao III não tenho dúvidas.

   

  Quanto ao IV acredito que ele se refira a primeira chamada à classificação por intercalação, ou seja o passo de combinar.

   

  O algoritmo tem duas fases. Primeiro se quebra o array recursivamente em n arrays de um elemento,

   

  Depois começa-se a intercalação em um laço recursivo. Cada um desses laços vai fazer n comparações e como a cada passo teremos arrays com o dobro de tamanho, ordenada, esse laço precisará ser executado executado log2(n) vezes. Daí a complexidade n*log2(n).

   

  Foi isso que tinha entendido, embora falta clareza ao item.

   

  https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif

   

   

• Tempo logarítmico O(log n) Busca binária

  Tempo linear O(n)  Procurando o menor item em um array não ordenado

  Tempo quadrático O(n2)  Bubble sort; Insertion sort

  Insertion sort algoritmo de classificação por inserção:

                                                                          complexidade pior caso O(n2)

                                                                          complexidade caso médio O(n2)

                                                                          complexidade melhor caso O(n)

   

   

   

   

• Resposta da banca ao recurso:

  Recurso Improcedente. Ratifica-se a opção divulgada no gabarito preliminar. A banca mantém o gabarito divulgado anteriormente. (Gab. C)

  I) Diz-se que o algoritmo 0(n) tem um tempo de execução linear.

  III) O algoritmo de classificação por seleção executa no tempo 0(n²).

  Fonte: DEITEL, P.; DEITEL, H. – Java: como programar – 8ª ed. São Paulo: Person Prentice Hall, 2010 – pág.: 633.

  Gab. Final: C

  Banca doida... =P

• Força Guerreiro!!!!!!