Organizações Primárias de Arquivos
Gabarito: letra D. Apenas a alternativa D está correta: arquivos hashing (tabelas de dispersão) oferecem acesso direto e rápido a um registro quando se conhece o valor da chave, pois utilizam uma função hash para mapear a chave a uma posição no arquivo, resultando em tempo de acesso praticamente constante (O(1) em média). As demais alternativas contêm erros conceituais sobre arquivos desordenados, ordenados e hashing.
Conteúdo de apoio (fonte genérica): "Outro tipo de organização de arquivo principal é baseado no hashing, que oferece acesso muito rápido aos registros sob certas condições de pesquisa." (C2)
A banca testa o conhecimento sobre as características básicas de cada organização: heap (desordenado), arquivo ordenado e hashing. É essencial dominar as operações de busca, inserção e tratamento de overflow.
Organização Primária | Característica de Acesso | Método de Pesquisa | Inserção | Tratamento de Colisão/Overflow |
|---|
Desordenado (Heap) | Leitura na ordem de classificação é ineficiente (varredura sequencial) | Pesquisa linear (b/2 blocos em média) | Simples (insere no final) | Não se aplica (não há colisão por chave) |
Ordenado | Leitura na ordem de classificação é eficiente (blocos consecutivos) | Pesquisa binária (log₂ b acessos) | Complexa (requer deslocamento ou arquivo de overflow) | Overflow tratado por encadeamento ou área de overflow |
Hashing | Acesso direto e rápido a um registro arbitrário (O(1) médio) | Função hash mapeia chave à posição | Rápida (posição calculada pela hash) | Colisões tratadas por encadeamento, sondagem linear, etc. |
Alternativa A — ❌ Incorreta
Afirma que arquivos desordenados diminuem o tempo para leitura na ordem do campo de classificação. Na verdade, em um arquivo heap (desordenado), a leitura na ordem de classificação exige uma varredura sequencial completa (ou ordenação prévia), o que é ineficiente (b/2 blocos em média). Arquivos ordenados é que tornam essa leitura eficiente, pois os blocos podem ser lidos consecutivamente. O erro está em inverter a vantagem.
Alternativa B — ❌ Incorreta
Afirma que arquivos ordenados exigem pesquisa linear. Na verdade, por estarem ordenados, permitem pesquisa binária, que localiza um registro em média em log₂ b acessos a blocos (b = número de blocos). A pesquisa linear (b/2) é característica de arquivos desordenados. A banca troca o método de pesquisa.
Alternativa C — ❌ Incorreta
Afirma que a inclusão em arquivos ordenados é muito simples porque os registros são inseridos no final. Isso é falso: inserir no final quebra a ordenação. A inserção correta exige deslocar registros ou usar um arquivo de overflow (insere no final de um arquivo auxiliar e depois mescla). Portanto, a inserção é complexa e custosa, não simples.
Alternativa D — ✅ Correta ⟵ GABARITO
A descrição está correta. Arquivos baseados em hashing (tabela de dispersão) utilizam uma função hash para, a partir do valor da chave, calcular diretamente a posição do registro. Isso proporciona acesso muito rápido (tempo constante médio) a um registro arbitrário, desde que se conheça a chave. As colisões são tratadas com técnicas como encadeamento, rehashing ou endereçamento aberto.
Alternativa E — ❌ Incorreta
Afirma que colisões que causam overflow em um arquivo ordenado são tratadas por encadeamento. Colisões são um conceito de hashing (quando duas chaves diferentes mapeiam para o mesmo endereço). Em arquivos ordenados, não há colisão de hash; o problema de overflow ocorre quando um bloco não tem espaço para novos registros, e a solução típica é o uso de arquivo de overflow (também chamado de arquivo de transação) ou a realocação dentro do próprio bloco. O encadeamento é uma técnica de tratamento de colisões em hashing, não em arquivos ordenados.
Gabarito: letra D