Logo Passei Direto
Buscar
Segue o texto extraído da imagem: “As operações básicas em uma árvore binária (de busca) têm tempo proporcional à sua altura. Como a altura da árvore dependerá da quantidade N de chaves e de sua ordem de inserção na árvore, o tempo de resposta das operações básicas dependerá da quantidade e da distribuição das chaves pelas subárvores (subárvores com diferentes alturas’). Fonte: BIANCHI, F.; FREITAS, R.; JUNIOR, D. Estrutura de dados e técnicas de programação. Rio de Janeiro: Elsevier, 2014, p.273. Considerando essas informações e o conteúdo estudado sobre a eficiência na busca em árvore binária, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) falsa(s). I. Uma árvore balanceada tem para cada nó da árvore as alturas das subárvores esquerda e direita, diferindo, no máximo, em uma unidade. II. Se uma árvore possuir essa propriedade, será alta e com mínimo. III. No pior caso, teremos as inserções das chaves de modo que a altura da árvore fosse N-1, ou seja, um tempo de execução das operações básicas O(N). IV. As árvores binárias, por definição, são balanceadas, pois implementam, naturalmente, o fator de equilíbrio. Agora, assinale a alternativa que apresenta a sequência correta.”
User badge image
Nilmar Fernandes

há 2 semanas

Respostas

User badge image

Ed Verified user icon

há 2 semanas

Vamos analisar cada afirmativa com base no conteúdo sobre árvores binárias de busca e eficiência: I. Uma árvore balanceada tem para cada nó da árvore as alturas das subárvores esquerda e direita, diferindo, no máximo, em uma unidade. Verdadeiro (V) — Essa é a definição clássica de árvore balanceada, como a árvore AVL, onde o fator de equilíbrio é no máximo 1. II. Se uma árvore possuir essa propriedade, será alta e com mínimo. Falso (F) — Se a árvore é balanceada, ela tende a ser baixa (altura mínima possível para o número de nós), não alta. III. No pior caso, teremos as inserções das chaves de modo que a altura da árvore fosse N-1, ou seja, um tempo de execução das operações básicas O(N). Verdadeiro (V) — No pior caso, a árvore pode degenerar em uma lista ligada, com altura N-1, e as operações básicas terão complexidade linear O(N). IV. As árvores binárias, por definição, são balanceadas, pois implementam, naturalmente, o fator de equilíbrio. Falso (F) — Árvores binárias não são necessariamente balanceadas; o balanceamento é uma característica de tipos específicos, como AVL ou Red-Black. Sequência correta: I (V), II (F), III (V), IV (F) Portanto, a sequência correta é: V - F - V - F.

Essa resposta te ajudou?

0
Dislike0
details

Libere essa resposta sem enrolação!

Craque NetoCraque Neto

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Mais conteúdos dessa disciplina