Ao aplicar o algoritmo DFS a Gnxn para… (ITA 2025)

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

Tecnologia da InformaçãoÁrvores e grafosITA 2025

ITA

5

Ao aplicar o algoritmo DFS a Gnxn para obter uma árvore de busca, contendo apenas as arestas entre sucessor e antecessor na busca DFS, podemos afirmar sobre esta árvore:

AA profundidade será n², sempre.Ba profundidade será O(n2), sempre, mas alcançará exatamente o limite superior ou não dependendo da ordem em que os vizinhos de cada vértice são listados.CA profundidade será O(log n), sempre.DO número de arestas da árvore pode ser diferente de n2-1, dependendo de como os vizinhos são ordenados.EO número de folhas da árvore é ω(log n), sempre.

Mais questões de Árvores e grafos

Fênix Instituto 2026Em uma árvore binária de busca, considerando valores distintos, a propriedade que orienta a organização dos nós estabelece que:
FGV 2026A árvore rubro-negra é uma estrutura de dados de árvore autobalanceada que mantém propriedades específicas para garantir desempenho consistente na manipulação de dados. Essa estru…
Vunesp 2026A teoria dos grafos é uma base importante para a com preensão das redes sociais. Os grafos são utilizados para analisar as redes e para entender os padrões de conexões, influência…
Fundatec 2026Uma Árvore Binária de Pesquisa (ABP) organiza chaves de forma que, para cada nó, todos os valores na subárvore esquerda são menores e todos na subárvore direita são maiores. A Árv…
Fundatec 2026No desenvolvimento de algoritmos, a escolha adequada das estruturas de dados é fundamental para a eficiência do sistema. Com base nas características estruturais e operacionais da…

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