Estrutura de dados para filtragem por prefixo
Gabarito: letra C. A estrutura de dados mais adequada para filtrar registros por prefixo do nome é uma árvore, especialmente uma árvore de prefixos (trie), que permite buscas eficientes por prefixo com complexidade O(n) no tamanho do prefixo. Fila, lista ligada e tabela hash não oferecem essa eficiência.
Alternativa A — ❌ Incorreta
Fila é uma estrutura FIFO (first-in, first-out), não otimizada para busca ou filtragem. Percorrer a fila para encontrar prefixos exigiria varredura linear, ineficiente para grandes volumes.
Alternativa B — ❌ Incorreta
Lista ligada também requer busca linear O(n) para cada consulta, o que é inaceitável para grandes conjuntos de dados e operações frequentes de prefixo.
Alternativa C — ✅ Correta ⟵ GABARITO
Árvores, especialmente árvores de prefixos (trie), são projetadas para buscas por prefixo. Uma trie armazena as chaves em caminhos da raiz até as folhas, permitindo localizar todos os registros com determinado prefixo em tempo proporcional ao tamanho do prefixo, independentemente do número total de registros.
Alternativa D — ❌ Incorreta
Tabela hash oferece busca exata O(1), mas não suporta consultas por prefixo. Para filtrar por prefixo, seria necessário percorrer todas as chaves, resultando em O(n), sem vantagem sobre estruturas lineares.
Gabarito: letra C.