Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IDCAP 2025

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qg517171
Banca
IDCAP
Órgão
HEMOBA
Ano
2025
Nível
Superior
Cargo
Analista Técnico - Área de Atuação: Análise de Sistemas
A escolha da estrutura de dados adequada é fundamental para o desenvolvimento de algoritmos eficientes, impactando diretamente a complexidade e o desempenho do software. Sobre as características de desempenho de diferentes estruturas de dados, analise as afirmativas a seguir:I.A busca por um elemento em uma árvore binária de busca (BST) perfeitamente balanceada possui complexidade de tempo no pior caso de O(logn), enquanto a busca em uma tabela de hash (hash table) com uma função de hash ideal e sem colisões possui complexidade de tempo de O(1).II.Uma lista duplamente encadeada oferece vantagem sobre uma lista simplesmente encadeada por permitir a inserção e remoção de elementos em tempo constante, O(1), em qualquer posição da lista, desde que o ponteiro para o nó seja conhecido.III.A estrutura de dados mais eficiente para implementar um sistema que necessita processar tarefas com base em diferentes níveis de urgência, garantindo que a tarefa de maior urgência seja sempre processada primeiro, é uma fila de prioridade (priority queue), frequentemente implementada com um heap.Está correto o que se afirma em:
  1. AI apenas.
  2. BIII apenas.
  3. CII e III apenas.
  4. DI, II e III.
  5. EI e III apenas.
Revelar gabarito e comentário

GabaritoB — III apenas.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Análise das afirmativas sobre estruturas de dados

Gabarito: letra B — apenas a afirmativa III está correta. A afirmativa I apresenta imprecisão sobre a complexidade de busca em tabelas hash, e a afirmativa II generaliza indevidamente a vantagem da lista duplamente encadeada.

Estruturas de dados
  • 1Árvore binária de busca (BST)
    • Balanceada
      • Busca: O(log n) no pior caso
    • Desbalanceada
      • Busca: O(n) no pior caso
  • 2Tabela hash
    • Caso médio
      • Busca: O(1)
    • Pior caso (colisões)
      • Busca: O(n)
  • 3Lista encadeada
    • Simples
      • Inserção após nó: O(1)
      • Remoção: O(n)
    • Dupla
      • Inserção após nó: O(1)
      • Remoção: O(1)
  • 4Fila de prioridade (heap)
    • Inserção: O(log n)
    • Extração do maior: O(log n)
LEVEL · soulevel.com.br

Item I — ❌ Incorreto

A busca em uma árvore binária de busca (BST) perfeitamente balanceada tem complexidade O(log n) no pior caso, o que está correto. No entanto, a afirmação sobre a tabela hash é problemática: mesmo com função de hash ideal e sem colisões, a complexidade de busca é O(1) apenas no caso médio; no pior caso, considerando a possibilidade de colisões (mesmo que a função seja ideal, colisões podem ocorrer se a tabela não for dimensionada adequadamente), a complexidade pode ser O(n). A condição "sem colisões" é idealizada e não reflete a realidade prática, tornando a comparação enganosa.

Item II — ❌ Incorreto

A lista duplamente encadeada permite remoção de um nó em O(1) quando se tem o ponteiro para ele, o que é uma vantagem sobre a lista simplesmente encadeada (que exige O(n) para remoção). Contudo, a afirmação diz que a inserção e remoção são O(1) "em qualquer posição". Na lista duplamente encadeada, a inserção após um nó dado é O(1), mas a inserção antes de um nó também exige o ponteiro para o nó anterior (que pode ser obtido via prev, o que é O(1)). Apesar disso, a afirmação peca ao generalizar para "qualquer posição" sem esclarecer que, na prática, para inserir no início ou final, o ponteiro deve ser conhecido. O erro principal é que a lista simplesmente encadeada também permite inserção após um nó em O(1), e a diferença real está na remoção e na inserção antes de um nó. A redação dá a entender que a duplamente é superior em todas as operações de inserção/remoção, o que não é verdade (inserção após um nó é igualmente O(1) em ambas).

Item III — ✅ Correto

Para processar tarefas com diferentes níveis de urgência, garantindo que a de maior urgência seja sempre atendida primeiro, a estrutura mais adequada é a fila de prioridade (priority queue), que é comumente implementada com um heap. O heap permite inserção e extração do elemento de maior prioridade em O(log n), sendo eficiente para esse fim.

NÃO CAIA NESSA!

A banca explora a confusão entre complexidade de caso médio e pior caso em tabelas hash. Embora a ideia de hash ideal sem colisões sugira O(1) garantido, na computação teórica o pior caso de uma hash table (com colisões) é O(n). A condição "sem colisões" é irrealista e, portanto, a afirmação I é considerada incorreta. Fique atento a essa sutileza.

Conclusão: apenas o item III está correto. Assim, a alternativa correta é a B (III apenas).

Link permanente: /questoes/qg517171