Algoritmos e Estrutura de Dados · FGV · 2025 | Questão sqc-fg118909

Algoritmos e Estrutura de DadosEstrutura de Dados

Código: fg118909
Banca: FGV
Órgão: Prefeitura de Rio de Janeiro - RJ
Ano: 2025
Nível: Superior

Cargo: Gestor de Segurança Municipal

Técnicas de indexação baseadas em hashing permitem a localização direta e eficiente de informações em tempo quase real, otimizando o acesso a grandes volumes de registros produzidos por câmeras, sensores e outros equipamentos de segurança pública.Sobre técnicas de indexação utilizando hashing, assinale a opção correta.

AA técnica de desdobramento em hashing refere-se à aplicação de um fator de carga de arquivo, que trata colisões em hashings com coalescência pela formação da cadeia de sinônimos, como no caso da técnica de quociente linear.
BA técnica de hashing extensível caracteriza-se, em seu funcionamento, na criação de um diretório de 2d endereços de bucket, sendo d a profundidade global do diretório, com a utilização dos d bits de mais alta ordem como índice para determinar uma entrada de diretório.
CEm hashing dinâmico, o diretório estruturado em árvores apresenta dois tipos de nós: os folha, mantendo localmente armazenados o bucket real com registros; e internos, com ponteiros esquerdo correspondente ao bit 1 no endereço hashed e o direito correspondendo ao bit 0.
DHashing externo corresponde à técnica de hasing aplicada em arquivos de disco, sendo o espaço de endereços de destino constituído por buckets - blocos de discos não contíguos, cada qual mantendo exatamente um registro.
EO princípio de funcionamento do hashing linear prevê que um arquivo de hash expanda e encolha seu número de buckets estaticamente, com o auxílio de um diretório, e com a criação de buckets adicionais divididos na ordem linear.

Revelar gabarito e comentário

GabaritoB — A técnica de hashing extensível caracteriza-se, em seu funcionamento, na criação de um diretório de 2d endereços de bucket, sendo d a profundidade global do diretório, com a utilização dos d bits de mais alta ordem como índice para determinar uma entrada de diretório.

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”.

Técnicas de indexação baseadas em hashing

Gabarito: letra B. O hashing extensível utiliza um diretório com 2^d entradas, onde d é a profundidade global, e emprega os d bits mais significativos (de mais alta ordem) para indexar o diretório. Essa descrição está correta e corresponde ao funcionamento clássico da técnica.

A questão exige conhecimento das principais variantes de hashing: extensível, linear, dinâmico e externo. Cada alternativa aborda um conceito específico, muitas vezes com imprecisões propositais (troca de características entre métodos).

Alternativa A — ❌ Incorreta

O termo "desdobramento" não é uma técnica consagrada em hashing. A descrição mistura elementos: "fator de carga" é uma métrica, "coalescência" e "cadeia de sinônimos" referem-se ao encadeamento separado (separate chaining), e "quociente linear" não é um método reconhecido. Portanto, a alternativa é falsa.

Alternativa B — ✅ Correta ⟵ GABARITO

No hashing extensível (extendible hashing), cria-se um diretório de tamanho 2^d, onde d é a profundidade global. Para determinar a entrada do diretório, utilizam-se os d bits de mais alta ordem (bits mais significativos) do valor hash. O diretório aponta para buckets que podem conter múltiplos registros. Essa descrição é precisa e corresponde à literatura (ex.: Cormen et al., "Algoritmos").

Alternativa C — ❌ Incorreta

Hashing dinâmico pode ser implementado com uma estrutura de árvore (trie), mas a descrição inverte a associação: normalmente, o ponteiro esquerdo corresponde ao bit 0 e o direito ao bit 1 (ou vice-versa, dependendo da convenção). Além disso, a alternativa afirma que nós internos têm ponteiro esquerdo para bit 1 e direito para bit 0, o que é o oposto do usual. A imprecisão torna a alternativa errada.

Alternativa D — ❌ Incorreta

Hashing externo é projetado para arquivos em disco, e os buckets são blocos de disco que geralmente armazenam vários registros, não exatamente um. A afirmação "cada qual mantendo exatamente um registro" é falsa; buckets tipicamente têm capacidade para múltiplos registros para otimizar acesso a disco.

Alternativa E — ❌ Incorreta

Hashing linear é um método dinâmico que expande e contrai o número de buckets sem utilizar um diretório — ao contrário do hashing extensível, que usa diretório. A alternativa afirma "com o auxílio de um diretório", o que é incorreto. Além disso, "estaticamente" contradiz o comportamento dinâmico do hashing linear.

NÃO CAIA NESSA!

A banca troca características entre hashing extensível e linear. No hashing linear, não há diretório; a expansão ocorre incrementalmente, tratando colisões com buckets overflow. Já no extensível, o diretório de 2^d entradas é essencial. Memorize essa distinção.

Gabarito: letra B.

Link permanente: /questoes/fg118909