Projete um algoritmo em pseudocódigo que receba uma lista de strings binárias (dados) e construa uma trie…

Questão

Projete um algoritmo em pseudocódigo que receba uma lista de strings binárias (dados) e construa uma trie (árvore de prefixos) que permita consultar quantas strings compartilham um determinado prefixo. Explique a estrutura, as variáveis e os procedimentos de inserção e consulta.

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

Resposta esperada

Estrutura: nó tem filhos[0,1] e contador. Variáveis: raiz (node). Inserção(s): node <- raiz; para cada bit b em s: se node.filhos[b] = null então criar nó; node <- node.filhos[b]; node.contador <- node.contador + 1. Pseudocódigo: criarTrie(): raiz.contador=0 inserir(raiz, s): node=raiz; for b in s: if node.filhos[b]==null then node.filhos[b]=novoNo(); node=node.filhos[b]; node.contador+=1 consultaPrefixo(raiz,p): node=raiz; for b in p: if node.filhos[b]==null return 0; node=node.filhos[b]; return node.contador Complexidade: inserção O(L) por string (L = comprimento); consulta O(P) (P = comprimento do prefixo). A trie armazena contadores por nó para responder rapidamente quantos dados compartilham um prefixo.

Explicação

A explicação apresenta uma estrutura clara para a trie, onde cada nó possui filhos que representam os bits 0 e 1, além de um contador que rastreia quantas strings compartilham o prefixo até aquele ponto. O algoritmo de inserção é eficiente, pois cria nós conforme necessário e atualiza o contador, enquanto a consulta é direta, permitindo verificar rapidamente quantas strings compartilham um prefixo específico. A análise de complexidade destaca a eficiência do algoritmo em termos de tempo, tornando-o adequado para o problema proposto.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo em pseudocódigo que receba uma lista de nomes (strings) como dado de entrada e devolva uma lista de…
• Descreva um algoritmo em pseudocódigo que, dada uma árvore enraizada onde cada nó mantém uma lista arbitrária de filhos…
• Projete um algoritmo em pseudocódigo que, dada uma árvore de decisão codificada como nós com condição e referências a…
• Descreva em etapas um algoritmo que recebe um conjunto de símbolos com suas frequências e gera uma codificação por…
• Explique como utilizar árvores para organizar dados de forma hierárquica em um programa.
• Projete um algoritmo em pseudocódigo para detectar ciclos em um grafo dirigido representado por listas de adjacência…

Todas as questões de Programação - Programação com listas e recursão