Questão de Algoritmos e Estrutura de Dados — Árvores — FUNDATEC 2023
Algoritmos e Estrutura de Dados›Árvores
Código
qq893853
Banca
FUNDATEC
Órgão
IF-RS
Ano
2023
Nível
Superior
Cargo
Professor - Informática: Programação, Estrutura de Dados e Análise de Algoritimos
Sobre árvores de pesquisa binária, analise as assertivas abaixo e assinale a alternativa correta.I. Admitem todas as operações sobre conjuntos dinâmicos, no pior caso, cada operação demora um tempo 1(n) em uma árvore com n elementos.II. As árvores vermelho-preto são uma variante de árvores de pesquisa binária.III. Em uma árvore de pesquisa binária construída aleatoriamente, não há como medir o tempo esperado para cada operação.IV. Uma árvore vermelho-preto é uma árvore de pesquisa balanceada, chamada árvore B.
ATodas as assertivas estão corretas.
BTodas as assertivas estão incorretas.
CApenas a assertiva I está correta.
DApenas as assertivas I e II estão corretas.
EApenas as assertivas III e IV estão corretas.
Revelar gabarito e comentário▾
GabaritoD — Apenas as assertivas I e II estão corretas.
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”.
Árvores de pesquisa binária
Gabarito: letra D. Apenas as assertivas I e II estão corretas. Em árvores binárias de busca (BST), no pior caso (árvore degenerada) as operações têm complexidade O(n), e as árvores vermelho-preto são uma variante balanceada de BST. As assertivas III e IV são falsas.
Item
Afirmação
Correção
Justificativa
I
Admitem todas as operações sobre conjuntos dinâmicos, no pior caso, cada operação demora um tempo O(n) em uma árvore com n elementos.
✅ Correta
Em BST degenerada (lista ligada), operações têm complexidade O(n).
II
As árvores vermelho-preto são uma variante de árvores de pesquisa binária.
✅ Correta
São BSTs com balanceamento aproximado, garantindo O(log n) no pior caso.
III
Em uma árvore de pesquisa binária construída aleatoriamente, não há como medir o tempo esperado para cada operação.
❌ Incorreta
O tempo esperado é O(log n), resultado conhecido da análise de algoritmos.
IV
Uma árvore vermelho-preto é uma árvore de pesquisa balanceada, chamada árvore B.
❌ Incorreta
Árvore vermelho-preto é diferente de árvore B (B-tree), que possui múltiplas chaves por nó.
Árvores de pesquisa binária
1BST (binária de busca)
Operações O(n) no pior caso
Tempo esperado O(log n)
2Variantes balanceadas
Rubro-negra (RB)
O(log n) no pior caso
Árvore B
Não é RB
Múltiplas chaves por nó
LEVEL · soulevel.com.br
Item I — ✅ Correto
Árvores de pesquisa binária suportam operações de conjuntos dinâmicos (busca, inserção, remoção). No pior caso, quando a árvore é degenerada (semelhante a uma lista ligada), cada operação tem complexidade O(n), onde n é o número de elementos. A assertiva menciona "tempo 1(n)", que interpretamos como O(n) ou tempo linear. Portanto, correta.
Item II — ✅ Correto
Árvores vermelho-preto são, de fato, uma variante de árvores de pesquisa binária. Elas são balanceadas de forma aproximada, garantindo que as operações tenham complexidade O(log n) no pior caso, mas mantêm a estrutura básica de uma BST (cada nó tem dois filhos, segue a propriedade de ordenação).
Item III — ❌ Incorreto
Para uma árvore de pesquisa binária construída aleatoriamente, o tempo esperado para cada operação (busca, inserção, remoção) é O(log n). Esse resultado é bem conhecido na análise de algoritmos, baseado na altura esperada de uma BST aleatória. A assertiva afirma que "não há como medir", o que é falso.
Item IV — ❌ Incorreto
Uma árvore vermelho-preto é uma árvore de pesquisa balanceada, mas não é chamada de "árvore B". Árvores B (B-trees) são uma estrutura diferente, usada principalmente em sistemas de arquivos e bancos de dados, com múltiplas chaves por nó. A assertiva confunde os dois conceitos.