Questão 906289

• Banca: FCC
• Órgão: TRT - 9ª REGIÃO (PR)
• Ano: 2013
• Provas: FCC - 2013 - TRT - 9ª REGIÃO (PR) - Analista Judiciário - Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação; Complexidade de Algoritmos

Analise as afirmativas:

I. Considere o método de ordenação que implementa o seguinte processo: uma coleção desordenada de n elementos é dividida em duas metades e cada metade é utilizada como argumento para a reaplicação recursiva da subrotina. Os resultados das duas reaplicações são, então, combinados pela intercalação dos elementos de ambas, resultando em uma coleção ordenada. A complexidade do caso médio desse algoritmo é expressa por O(n log₂ n).

II. Existem aplicações para listas lineares nas quais inserções, retiradas e acessos a itens ocorrem sempre em um dos extremos da lista. Nestes casos a estrutura adequada para resolvê-los é a pilha ou stack.

III. No método Quicksort, o pivô é responsável pelo número de partições em que o vetor é dividido. Como o pivô não pode ser um elemento que esteja repetido no vetor, o Quicksort não funciona quando há elementos repetidos.

Está correto o que se afirma em

• A. I e III, apenas.
• B. I, II e III.
• C. I e II, apenas.
• D. II, apenas.
• E. II e III, apenas.

Gabarito: C

Comentários

• I. Trata-se do método MergeSort, corretamente descrito, cuja complexidade de tempo é Θ(n log2 n). Alternativa VERDADEIRA.

   http://pt.wikipedia.org/wiki/Merge_sort

  
  

  
  

  II - As duas estruturas de dados lineares que permitem inserções, retiradas e acessos somente aos extremos da lista são pilhas (stacks) e filas (queues). Alternativa VERDADEIRA.

  http://pt.wikipedia.org/wiki/Pilha_(inform%C3%A1tica)

  
  

  
  

  III - No método QuickSort, qualquer elemento pode ser o pivô. Este obviamente funciona mesmo quando há elementos repetidos. Alternativa FALSA.

  http://pt.wikipedia.org/wiki/Quick_sort

• Força Guerreiro!!!!!!