Prévia do material em texto

Árvore balanceada 
O que caracteriza uma arvore balanceada?
a) Cada no possui apenas um filho.
b) A diferenca entre a altura das subarvores de qualquer no e limitada.
c) Cada no deve ter um numero fixo de filhos.
d) As folhas estao sempre no mesmo nivel.
Resposta correta: b) A diferenca entre a altura das subarvores de qualquer no e limitada.
Explicacao: Uma arvore e considerada balanceada quando a diferenca entre a altura das suas
subarvores esquerda e direita, em qualquer no, e mantida dentro de um limite especifico. Isso
garante um tempo de busca eficiente.
Qual e o principal objetivo de manter uma arvore balanceada?
a) Garantir que todas as operacoes sejam realizadas em tempo constante.
b) Melhorar o desempenho das operacoes de busca, insercao e remocao.
c) Minimizar o uso de memoria.
d) Reduzir o numero de nos na arvore.
Resposta correta: b) Melhorar o desempenho das operacoes de busca, insercao e remocao.
Explicacao: O principal objetivo de manter uma arvore balanceada e garantir que as operacoes de
busca, insercao e remocao possam ser realizadas de forma eficiente, com um tempo de execucao
proximo ao minimo, geralmente O(log n).
Em uma arvore binaria de busca balanceada, qual e a altura maxima de qualquer no em relacao a
sua subarvore?
a) A altura de qualquer no pode ser arbitrariamente alta.
b) A altura de qualquer subarvore pode diferir no maximo em 2 niveis.
c) A altura das subarvores de qualquer no deve ser a mesma.
d) A altura das subarvores de qualquer no nao deve diferir mais que 1 nivel.
Resposta correta: d) A altura das subarvores de qualquer no nao deve diferir mais que 1 nivel.
Explicacao: Em uma arvore binaria de busca balanceada (como uma AVL ou Red-Black), a altura
das subarvores de qualquer no nao deve diferir em mais de 1 nivel, garantindo a eficiencia nas
operacoes.
Qual das seguintes arvores e um exemplo de arvore balanceada?
a) Arvore binaria de busca (BST).
b) Arvore AVL.
c) Arvore binaria nao balanceada.
d) Arvore binaria de heap.
Resposta correta: b) Arvore AVL.
Explicacao: A Arvore AVL e um exemplo classico de arvore balanceada. Ela mantem a diferenca de
altura entre as subarvores de qualquer no em no maximo 1, garantindo operacoes eficientes de
busca e modificacao.
Como uma arvore AVL garante que as operacoes de insercao e remocao sejam eficientes?
a) Atraves da reorganizacao automatica dos nos.
b) Garantindo que a altura das subarvores de qualquer no seja equilibrada.
c) Mantendo os nos sempre ordenados.
d) Utilizando apenas nos com um numero fixo de filhos.
Resposta correta: b) Garantindo que a altura das subarvores de qualquer no seja equilibrada.
Explicacao: A arvore AVL faz isso por meio de rotacoes, que sao operacoes de reorganizacao dos
nos da arvore, garantindo que a diferenca de altura entre as subarvores de qualquer no nunca seja
maior que 1.
Qual operacao e realizada para restaurar o balanceamento de uma arvore AVL quando ela fica
desbalanceada?
a) Compressao.
b) Divisao de nos.
c) Rotacoes.
d) Excluindo o no desbalanceado.
Resposta correta: c) Rotacoes.
Explicacao: Quando uma arvore AVL fica desbalanceada, uma rotacao e realizada para restaurar o
balanceamento. Existem diferentes tipos de rotacoes, como rotacao a esquerda e a direita, que
reorganizam a arvore para manter o equilibrio.
Em uma arvore binaria de busca balanceada, como uma arvore AVL, o que acontece quando a
diferenca de altura das subarvores de um no e maior que 1?
a) A arvore e reestruturada por uma rotacao.
b) A arvore cresce indefinidamente.
c) A arvore e convertida para uma arvore nao balanceada.
d) A arvore retorna erro de operacao.
Resposta correta: a) A arvore e reestruturada por uma rotacao.
Explicacao: Quando a diferenca de altura das subarvores de um no excede 1, a arvore e
reestruturada por meio de uma rotacao, que pode ser simples ou dupla, dependendo da situacao.
Qual e o tempo de busca em uma arvore binaria balanceada (como AVL ou Red-Black)?
a) O tempo de busca e constante, O(1).
b) O tempo de busca e linear, O(n).
c) O tempo de busca e logaritmico, O(log n).
d) O tempo de busca depende do numero de nos internos.
Resposta correta: c) O tempo de busca e logaritmico, O(log n).
Explicacao: Em uma arvore binaria balanceada, a altura da arvore e mantida baixa, garantindo que
a busca ocorra em tempo logaritmico, O(log n), o que e muito mais eficiente do que uma busca
linear.
Quais sao as principais vantagens de uma arvore binaria balanceada sobre uma arvore binaria de
busca nao balanceada?
a) Menor consumo de memoria.
b) Maior facilidade de implementacao.
c) Maior eficiencia nas operacoes de busca, insercao e remocao.
d) Menor numero de rotacoes durante as insercoes.
Resposta correta: c) Maior eficiencia nas operacoes de busca, insercao e remocao.
Explicacao: A principal vantagem de uma arvore binaria balanceada e que ela mantem o tempo das
operacoes de busca, insercao e remocao no tempo logaritmico, mesmo em cenarios com muitos
dados, enquanto uma arvore nao balanceada pode ter desempenho muito pior.
Em uma arvore Red-Black, qual e a principal propriedade que garante seu balanceamento?
a) Todos os nos sao sempre vermelhos.
b) A altura das subarvores de qualquer no nunca difere em mais de 2.
c) Os nos vermelhos nao podem ter filhos vermelhos.
d) A arvore sempre tem um numero fixo de nos.
Resposta correta: c) Os nos vermelhos nao podem ter filhos vermelhos.
Explicacao: A principal regra da arvore Red-Black que garante o balanceamento e que um no
vermelho nao pode ter filhos vermelhos. Isso, juntamente com outras propriedades, ajuda a manter
o balanceamento e a eficiencia das operacoes.
O que acontece quando uma arvore Red-Black e desbalanceada apos uma insercao?
a) Ela e reorganizada automaticamente em um no unico.
b) Ela se torna uma arvore AVL.
c) O balanceamento e restaurado por meio de rotacoes e mudancas de cor.
d) A arvore e completamente reconstruida.
Resposta correta: c) O balanceamento e restaurado por meio de rotacoes e mudancas de cor.
Explicacao: Quando uma arvore Red-Black se desbalanceia apos uma insercao, ela e reorganizada
por meio de rotacoes e mudancas de cor para manter as propriedades da arvore, garantindo que as
operacoes continuem eficientes.
Qual e a principal vantagem de uma arvore Red-Black em comparacao com uma arvore AVL?
a) As arvores Red-Black sao mais faceis de implementar.
b) As arvores Red-Black sao mais balanceadas, o que resulta em tempo constante para operacoes.
c) As arvores Red-Black exigem menos rotacoes para manter o balanceamento.
d) As arvores Red-Black sao mais eficientes para consultas em intervalos.
Resposta correta: a) As arvores Red-Black sao mais faceis de implementar.
Explicacao: A arvore Red-Black e mais facil de implementar do que a arvore AVL, pois suas regras
de balanceamento sao menos rigorosas e exigem menos rotacoes, tornando as operacoes de
insercao e remocao mais simples.
Qual e a principal caracteristica de uma arvore binaria balanceada por fator de equilibrio?
a) Ela deve manter uma diferenca de altura de no maximo 2 entre os nos.
b) O numero de filhos de cada no deve ser o mesmo.
c) A altura de todas as subarvores deve ser igual.
d) A diferenca de altura entre as subarvores de cada no deve ser no maximo 1.
Resposta correta: d) A diferenca de altura entre as subarvores de cada no deve ser no maximo 1.
Explicacao: Nas arvores balanceadas por fator de equilibrio, como a AVL, a diferenca de altura
entre as subarvores de qualquer no e mantida em no maximo 1, o que garante um tempo de busca
eficiente.
Em uma arvore AVL, qual operacao e realizada quando a arvore fica desbalanceada apos a
insercao de um novo no?
a) Divisao do no desbalanceado.
b) Troca de posicao dos nos.
c) Rotacoes para restaurar o balanceamento.
d) Descarte do no desbalanceado.
Resposta correta: c) Rotacoes para restaurar o balanceamento.
Explicacao: Em uma arvore AVL, quando ocorre um desbalanceamento apos uma insercao, a
arvorerealiza rotacoes (