Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IF-MT 2023
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qq952259
Banca
IF-MT
Órgão
IF-MT
Ano
2023
Nível
Superior
Cargo
Professor do Ensino Básico, Técnico e Tecnológico: Informática
Considere as afirmações abaixo sobre estruturas de dados em árvore.I – Uma árvore AVL (Adelson-Velskii e Landis) é uma árvore na qual as alturas das subárvores esquerda e direita de cada nó diferem no máximo em um elemento.II – A árvore B é uma estrutura de dados que foi projetada para minimizar o número de acessos à memória secundária, sendo que cada nó associado pode ter mais de uma chave.III – Uma Black-Red Tree é uma árvore B+ que possui um bit extra para armazenar a cor de cada nó.Está CORRETO o que consta em:
AI e II, apenas.
BI e III, apenas.
CII, apenas.
DIII, apenas.
EI, II e III.
Revelar gabarito e comentário▾
GabaritoA — I e II, apenas.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Estruturas de dados em árvore: AVL, Árvore B e Rubro-Negra
Gabarito: letra A (I e II, apenas). A afirmativa I está correta: árvores AVL são balanceadas com diferença de altura máxima de 1 entre subárvores. A afirmativa II está correta: árvores B são projetadas para minimizar acessos a disco e cada nó pode ter múltiplas chaves. A afirmativa III está incorreta: árvores Rubro-Negras são árvores binárias de busca balanceadas, não são variantes de árvores B+.
A banca cobra o conhecimento das definições clássicas das principais estruturas de árvores balanceadas. O erro típico é confundir árvore Rubro-Negra (Red-Black Tree) com árvore B+, já que ambas usam balanceamento, mas são conceitos distintos.
Afirmação I — ✅ Correta
Uma árvore AVL é uma árvore binária de busca balanceada em que, para cada nó, a diferença entre as alturas das subárvores esquerda e direita é no máximo 1. Esse fator de balanceamento garante que a árvore permaneça aproximadamente equilibrada, assegurando operações de busca, inserção e remoção em O(log n). A redação "diferem no máximo em um elemento" pode ser interpretada como diferença de altura máxima de 1, o que está correto.
Afirmação II — ✅ Correta
A árvore B é uma estrutura de dados auto-balanceada que mantém dados ordenados e permite buscas, inserções e remoções em tempo logarítmico. Ela foi projetada para funcionar eficientemente com memória secundária (discos), pois cada nó pode conter várias chaves (fan-out alto), reduzindo o número de acessos a disco. É amplamente usada em bancos de dados e sistemas de arquivos.
Afirmação III — ❌ Incorreta
Uma árvore Rubro-Negra (Red-Black Tree) é uma árvore binária de busca balanceada, não uma árvore B+. Cada nó possui um bit extra para armazenar a cor (vermelho ou preto), que é usado para garantir o balanceamento aproximado. A afirmação erra ao classificá-la como uma árvore B+; são estruturas diferentes: árvores B+ são generalizações de árvores B com folhas encadeadas, usadas em indexação de bancos de dados, enquanto árvores Rubro-Negras são binárias.
Afirmação
Descrição
Correção
Motivo
I
Árvore AVL: alturas das subárvores esquerda e direita de cada nó diferem no máximo em 1
✅ Correta
Definição clássica de árvore AVL balanceada
II
Árvore B: projetada para minimizar acessos à memória secundária; cada nó pode ter múltiplas chaves
✅ Correta
Característica fundamental de árvores B
III
Black-Red Tree é uma árvore B+ com bit extra para cor
❌ Incorreta
Árvore Rubro-Negra é binária, não é variante de árvore B+
Árvores balanceadas
1Binárias
AVL
Diferença de altura ≤ 1
Fator de balanceamento
Rubro-Negra
Bit extra de cor
Balanceamento aproximado
2Multicaminho
Árvore B
Múltiplas chaves por nó
Minimiza acessos a disco
Árvore B+
Folhas encadeadas
Indexação de bancos de dados
LEVEL · soulevel.com.br
NÃO CAIA NESSA!
Para não confundir, lembre-se: árvores AVL e Rubro-Negras são binárias; árvores B e B+ são multicaminho (cada nó pode ter mais de duas subárvores). Árvore Rubro-Negra tem cor, mas é binária, não é B+.
Gabarito: letra A — corretas apenas as afirmações I e II.