SóProvas

ID
1822588
Banca
FGV
Órgão
TJ-PI
Ano
2015
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Considere um sistema que enfileira tarefas a serem executadas com variadas prioridades. Ao comparar duas formas comuns de implementação de listas de prioridade, uma usando lista ordenada e outra usando heap binária, conclui-se que:

Alternativas
Comentários

  • Falou em lista de prioridade, falou em heap

    Ótimo material, bem suscinto, sobre o assunto.


    http://webserver2.tecgraf.puc-rio.br/eda/slides/EDA_05_Heap.pdf

  • ===Letra A===

    lista ordenada é mais indicada, pois apresenta complexidade O(1) para inserção, remoção e consulta; (ERRADO)

    Lista ordenada apresenta complexidade O(1) para inserção, remoção e consulta O(n).

    ===Letra B===

    lista ordenada é mais indicada, pois, apesar de sua complexidade de inserção ser O(n), suas complexidades de remoção e consulta são O(1);(ERRADO)

    ===Letra C===

    heap binária é mais indicada, pois apresenta complexidade O(log n) para inserção e remoção e O(1) para consulta; (CERTO)

    ===Letra D===

    heap binária é mais indicada, pois apresenta complexidade O(1) para inserção e remoção e O(log n) para consulta; (ERRADO)

    heap binária apresenta complexidade O(log n) para inserção e remoção e O(1) para consulta;

    ===Letra E===

    ambas as escolhas são boas, pois apresentam as mesmas complexidades para inserção, remoção e consulta. (ERRADO)

    Número de passos de cada operações em uma lista ordenada:

    - Seleção: O(1)

    - Inserção: O(n)

    - Remoção: O(1)

    - Alteração: O(n)

    - Construção: O(n log n)

    Número de passos de cada operações Heap:

    - Seleção: O(1)

    - Inserção: O(log n)

    - Remoção: O(log n)

    - Alteração: O(log n)

    - Construção: O(n)

  • Força Guerreiro!!!!!!