Questão de TI - Desenvolvimento de Sistemas — Árvores — IBFC 2024

A árvore __ é construída a partir da árvore binária de prefixo. Seja um conjunto de chaves {s1, …, sn} de valores binários tais que nenhuma chave seja prefixo de outra.   Considere a árvore binária de prefixo correspondente a essas chaves apresentada na figura a seguir. Sabendo que as chaves válidas se encontram nas folhas da árvore, e admitindose de início, que a chave procurada z seja uma chave sempre válida. Agora o processo em questão é buscar a chave z = s4 na árvore. A partir do valor binário de z, o algoritmo percorrerá o caminho 11100 na árvore, iniciando pela raiz. Se z é uma chave válida, após se assegurar de que os dois primeiros dígitos de z são 11 não há alternativa para os dois seguintes, pois correspondem a nós com um único filho. Então, neste caso, a busca poderia eliminar o terceiro e o quarto teste de dígitos, pois, certamente será produzido 10.   Em outras palavras, do segundo dígito da chave poderia se prosseguir diretamente para o quinto.   Assinale a alternativa que preencha corretamente a lacuna do texto acima .

1. APatricia
2. BMoore
3. CKiefer
4. DBoyer
5. EBoyer-Moore