Computação1º anoBNCC EF15CO01Difícil⏱ longo

Descreva com precisão o algoritmo e as estruturas de dados (registros, hash ou listas) para construir um…

Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva

Habilidade BNCC EF15CO01

Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).

Fonte: Base Nacional Comum Curricular (MEC).

Questão

Descreva com precisão o algoritmo e as estruturas de dados (registros, hash ou listas) para construir um índice invertido: dado uma coleção de documentos, produzir uma estrutura que permita, para qualquer termo, retornar a lista de documentos que o contêm. Explique como representar cada entrada, como atualizar ao processar cada documento e como realizar a busca por termo.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Estruturas: tabela hash (mapa) de termo ? lista de postagens; cada postagem é um registro com campos {docID, frequência, (opcional) posições}. Algoritmo de construção: para cada documento D com id docID, tokenizar o texto; para cada token t, procurar t na tabela hash; se ausente, inserir chave t com lista vazia; na lista de postagens, se o último registro não tem docID igual a docID, anexar novo registro {docID,1, [pos]}; caso contrário, incrementar frequência e acrescentar posição. Para evitar duplicados ao processar um mesmo documento, atualizar o registro existente em vez de adicionar outro. Representação das postagens: listas ligadas ou arrays dinâmicos; manter postagens ordenadas por docID facilita operações de interseção em consultas múltiplas. Busca por termo: buscar t na tabela hash (O(1) médio) e retornar a lista de postagens associada; para consulta multi-termo, intersectar listas ordenadas (merge). Complexidade: construção O(total_tokens) tempo médio; busca por termo O(1) para localizar a lista, mais custo de varredura das postagens. Observações: para escala, usar compressão de postagens, blocos ou estruturas em disco e manter vocabulário em hash ou trie para memória eficiente.

Explicação

A explicação apresenta de forma clara as estruturas de dados necessárias para implementar um índice invertido, detalhando como cada entrada é representada e atualizada durante o processamento dos documentos. O algoritmo descrito assegura eficiência tanto na construção do índice quanto na busca por termos, otimizando operações com o uso de tabelas hash e listas de postagens. Além disso, menciona considerações práticas para escalabilidade e eficiência em consultas, o que é fundamental em sistemas de busca.

Raio-X da questão

Dificuldade Difícil

Bloom Criar

Leitura alto

Discriminação alto

Peso pedagógico alto

Autonomia do enunciado completo

Cobertura da habilidade multipla

🧪 Simulado🩺 Diagnóstico🧮 Exige cálculo🏠 Cotidiano🔗 Interdisciplinar⭐ Representativa✍️ interpretativa🧩 desafio

🎯 Conceito central

índice invertido

📌 Objetivo

avaliacao

🧱 Pré-requisitos

estruturas de dados · algoritmos de busca

📚 Reveja

Revisar conceitos de algoritmos e estruturas de dados.

⚠️ Erro mais comum

O aluno pode descrever um algoritmo de busca simples, mas não incluir a estrutura de dados necessária para um índice invertido.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

pensamento_critico

🏫 Contexto

cientifico

Questões parecidas com resolução

Todas as questões de Organização e representação da informação

🔎 Procurar outra questão

Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.

Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog