Marque a alternativa FALSA. (ITA 2025)

Questões de Tecnologia da Informação · ITA

Tecnologia da InformaçãoÁrvores e grafosITA 2025

ITA

Marque a alternativa FALSA.

AÉ preciso percorrer toda a árvore para encontrar o caminho máximo entre a raiz e uma folha, portanto, um limite inferior para qualquer algoritmo é Ω(n) em tempo de execução.BComo se requer a impressão dos valores ao longo do caminho máximo da raiz a uma folha, o tamanho da resposta é Θ(h). Portanto, um limite inferior para qualquer algoritmo é Ω(h) em tempo de execução.CConsiderando os itens a) e b) acima, e que é preciso encontrar o caminho antes de imprimi-lo, um limite inferior para qualquer algoritmo é Ω(n + h) em tempo de execução.DA existência de um algoritmo Θ(n) em tempo de execução é compatível com a existência de um limite inferior para qualquer algoritmo Ω(n + h) em tempo de execução.EO raciocínio expresso nas alternativas a), b), c) e d) não é válido para árvores balanceadas, é válido apenas se h = ω(log n) 12 .

Mais questões de Árvores e grafos

Questão de prova oficial, com o gabarito definitivo publicado pela banca. Reproduzida para fins de estudo.