Questão 2891164

• Banca: IF-MS
• Órgão: IF-MS
• Ano: 2019
• Provas: IF-MS - 2019 - IF-MS - Técnico em Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos; Estrutura de Dados; Filas

Considere as seguintes afirmações sobre algoritmos e estruturas de dados:

I. Filas são estruturas do tipo FIFO (First In First Out).

II. A inserção no fim de uma lista duplamente encadeada e não ordenada é realizada em O(n).

O tempo de execução do algoritmo quicksort no pior caso é O(n² ).

Assinale a opção CORRETA:

• A. Apenas a afirmação I é verdadeira.
• B. Apenas a afirmação II é verdadeira.
• C. Apenas a afirmação III é verdadeira.
• D. Apenas as afirmações I e III são verdadeiras.
• E. As afirmações I, II e III são verdadeiras.

Gabarito: D

Comentários

• Estão apenas corretas as alternativas

  I. Filas são estruturas do tipo FIFO (First In First Out).

  PRIMEIRO QUE ENTRA PRIMEIRO QUE SAI. Similar à fila de um banco.

   

  III - O tempo de execução do algoritmo quicksort no pior caso é O(n2 ).

  Complexidade no pior caso: O(n2 ). https://uploaddeimagens.com.br/imagens/quicksort_-_cesgranrio-png

• II. A inserção no fim de uma lista duplamente encadeada e não ordenada é realizada em O(n).

  "Inserção no fim da lista

  Basta realizar operações de atribuições atualizando o ponteiro do fim (e início, quando necessário). Tempo gasto é constante, O(1). Realizada em:

  -> Lista simplesmente encadeada e não ordenada.

  -> Lista duplamente encadeada e não ordenada.

  -> Lista circular simplesmente encadeada e não ordenada.

   -> Lista circular duplamente encadeada e não ordenada"

  Fonte: Estruturas de Dados - Ana Fernanda Gomes Ascencio; Graziela Santos de Araújo;

• O fato da lista não estar ordenada, cria a necessidade de buscar o elemento final, ou seja, uma estrutura de repetição a mais é necessária para varrer a lista comparando o elemento atual, criando uma complexidade O(n²).

• d-

  ________________________________________________________________________________________

  Algoritmo            Melhor caso   Pior caso

  ----------------------------------------------------------------------

  Select Sort           n2                n2

  ----------------------------------------------------------------------

  Bubble Sort           n2                n2

  ----------------------------------------------------------------------

  Inserção Direta     n2                 n2

  ----------------------------------------------------------------------

  Heap Sort            nlogn            nlogn

  ----------------------------------------------------------------------

  Merge Sort          nlogn             nlogn

  ----------------------------------------------------------------------

  Quick Sort           nlogn              n2

  ----------------------------------------------------------------------

  ________________________________________________________________________________________

  complexidade de inserção no fim de uma lista duplamente encadeada e não ordenada é

  O(1)

• Complementando as demais respostas, a complexidade para inserção no fim de uma lista duplamente encadeada é O(1) pois podemos inserir diretamente na posição final. Isto se deve ao fato de ao desenvolver o algoritmo da lista duplamente encadeada, diferente da linear, devemos guardar as posições de início e fim da lista.

  Gabarito D

• Força Guerreiro!!!!!!

• Entendi que a questão Raphael Coutinho menciona como "definição" a mim se apresenta mais como uma descrição da atividade do que propriamente uma definição do termo criação