Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2018
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fg031205
Banca
FGV
Órgão
Banestes
Ano
2018
Nível
Superior
Cargo
Analista em Tecnologia da Informação - Suporte e Infraestrutura
Sobre as características de índices estruturados na forma de Btrees e Hash tables, analise as afirmativas a seguir.I. Hash tables aplicam-se somente em buscas que referenciam a chave por inteiro (operador =).II. B-trees favorecem consultas que buscam chaves num determinado intervalo (operadores >= e <=).III. B-trees são usualmente mais lentas para buscas pela chave (operador =).IV. Hash tables favorecem buscas, com o operador ‘LIKE’ do SQL, que não contenham caracteres curingas na primeira posição.V. B-trees não se aplicam em buscas que se referem a uma substring à esquerda da chave.Está correto o que se afirma em:
Anenhuma;
Bsomente I, II e III;
Csomente I, IV e V;
Dsomente II, III, IV;
EI, II, III, IV e V.
Revelar gabarito e comentário▾
GabaritoB — somente I, II e III;
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”.
B-trees e Hash Tables: características
Gabarito: letra B. Apenas as afirmativas I, II e III estão corretas. Hash tables são eficientes apenas para buscas exatas (operador =), enquanto B-trees são adequadas para consultas por intervalo (>= e <=) e são mais lentas que hash tables para busca exata. As afirmativas IV e V são falsas: hash tables não suportam LIKE, e B-trees suportam buscas por prefixo (substring à esquerda).
Busca exata (=)
Busca por intervalo (>=, <=)
B-tree
Rápida (O(1))
Não suporta
Hash Table
Mais lenta (O(log n))
Eficiente
LEVEL · soulevel.com.br
Item I — ✅ Correta
Hash tables aplicam-se somente em buscas que referenciam a chave por inteiro (operador =). De fato, as hash tables são projetadas para acesso direto por meio de uma função hash que mapeia a chave para um bucket, sendo eficientes apenas para consultas de igualdade. Não suportam consultas por intervalo ou padrão.
Item II — ✅ Correta
B-trees favorecem consultas que buscam chaves num determinado intervalo (operadores >= e <=). As B-trees mantêm os dados ordenados e balanceados, permitindo percorrer as folhas em ordem para recuperar rapidamente todos os elementos dentro de um intervalo.
Item III — ✅ Correta
B-trees são usualmente mais lentas para buscas pela chave (operador =). Enquanto uma hash table tem complexidade O(1) média para busca exata, a B-tree tem complexidade O(log n) – com a altura da árvore. Portanto, a B-tree é mais lenta para esse tipo de consulta.
Item IV — ❌ Incorreta
Hash tables favorecem buscas com o operador ‘LIKE’ do SQL que não contenham caracteres curingas na primeira posição. Isso é falso. Hash tables não oferecem suporte a casamento de padrões ou substrings; elas exigem a chave completa para calcular o hash. Mesmo um LIKE sem curinga inicial (ex.: 'abc%') não pode ser eficientemente resolvido por uma hash table, pois a função hash depende da chave inteira.
Item V — ❌ Incorreta
B-trees não se aplicam em buscas que se referem a uma substring à esquerda da chave. Falso. As B-trees, por serem árvores ordenadas, permitem buscas por prefixo (substring à esquerda) de forma eficiente, já que podem percorrer a faixa de valores com aquele prefixo. Por exemplo, uma consulta com LIKE 'abc%' pode ser otimizada usando uma B-tree como índice.
Critério
Hash Table
B-tree
Busca exata (=)
Rápida (O(1) médio)
Mais lenta (O(log n))
Busca por intervalo
Não suporta
Suporta eficientemente
Busca por prefixo
Não suporta
Suporta (via escaneamento ordenado)
LIKE com curinga
Não suporta
Suporta (com otimização para prefixo)
Gabarito: letra B (corretos apenas os itens I, II e III).