rvore binria de busca

Prévia do material em texto

Árvore binária de busca 
Qual das seguintes opcoes e uma caracteristica de uma Arvore Binaria de Busca (ABB)?
a) Cada no pode ter no maximo dois filhos, e os nos a esquerda de um no sao menores que o no,
enquanto os nos a direita sao maiores.
b) Cada no pode ter no maximo tres filhos, e a arvore deve ser balanceada.
c) Todos os nos possuem o mesmo valor.
d) Os filhos de um no devem ser maiores que o no.
Resposta correta: a)
Explicacao: A Arvore Binaria de Busca tem a caracteristica de que, para qualquer no, todos os
valores no seu subarvore esquerda sao menores que o valor do no, e todos os valores na sua
subarvore direita sao maiores.
Qual e a principal vantagem de se utilizar uma Arvore Binaria de Busca?
a) Facilidade na realizacao de buscas rapidas.
b) Estrutura simples de implementacao.
c) Nao ha necessidade de balanceamento.
d) A arvore sempre se mantem balanceada automaticamente.
Resposta correta: a)
Explicacao: A principal vantagem da ABB e permitir buscas rapidas, com complexidade O(log n) na
melhor situacao, o que torna a operacao de busca muito eficiente.
Qual e a complexidade do tempo para inserir um novo elemento em uma Arvore Binaria de Busca
balanceada?
a) O(n)
b) O(log n)
c) O(n log n)
d) O(1)
Resposta correta: b)
Explicacao: Em uma Arvore Binaria de Busca balanceada, a insercao de um novo elemento ocorre
em tempo O(log n), ja que a arvore esta balanceada e a profundidade e logaritmica.
O que acontece quando voce tenta inserir um valor que ja existe em uma Arvore Binaria de Busca?
a) O no com valor duplicado e removido.
b) O no com valor duplicado e ignorado.
c) A arvore e reorganizada automaticamente.
d) A insercao falha.
Resposta correta: b)
Explicacao: Em uma Arvore Binaria de Busca, valores duplicados geralmente sao ignorados, a nao
ser que haja uma estrategia especifica para trata-los.
Como voce pode garantir que uma Arvore Binaria de Busca se mantenha balanceada?
a) Adicionando um no aleatorio de cada vez.
b) Garantindo que as subarvores esquerda e direita de cada no tenham o mesmo numero de nos.
c) Utilizando uma arvore AVL ou Red-Black.
d) Modificando a estrutura da arvore apos cada insercao.
Resposta correta: c)
Explicacao: Arvores como AVL ou Red-Black sao tipos especificos de Arvore Binaria de Busca que
garantem que a arvore se mantenha balanceada apos cada insercao ou remocao.
Qual e a principal diferenca entre uma Arvore Binaria de Busca e uma Arvore Binaria comum?
a) Em uma Arvore Binaria de Busca, os valores a esquerda de um no sao menores, e a direita sao
maiores.
b) Na Arvore Binaria de Busca, cada no pode ter mais de dois filhos.
c) A Arvore Binaria de Busca sempre mantem sua altura minima.
d) Na Arvore Binaria de Busca, os valores nao podem se repetir.
Resposta correta: a)
Explicacao: A diferenca fundamental e a regra de ordenacao dos valores: na Arvore Binaria de
Busca, os nos a esquerda sao menores que o no e a direita sao maiores, o que nao e uma regra
em uma Arvore Binaria comum.
Qual e a complexidade de tempo da operacao de busca em uma Arvore Binaria de Busca
balanceada?
a) O(n)
b) O(log n)
c) O(n log n)
d) O(1)
Resposta correta: b)
Explicacao: A busca em uma Arvore Binaria de Busca balanceada e O(log n), ja que, em media, a
arvore tem altura logaritmica, o que resulta em uma busca eficiente.
O que ocorre quando a Arvore Binaria de Busca se torna desbalanceada?
a) As operacoes de busca, insercao e remocao se tornam mais rapidas.
b) O tempo de busca pode aumentar para O(n).
c) A arvore automaticamente se reorganiza para se balancear.
d) A arvore deixa de ser uma Arvore Binaria de Busca.
Resposta correta: b)
Explicacao: Quando a arvore fica desbalanceada, a profundidade pode aumentar, levando as
operacoes de busca a ter tempo O(n), o que torna a performance significativamente pior.
Qual e o pior caso para a complexidade de busca em uma Arvore Binaria de Busca?
a) Quando a arvore esta balanceada.
b) Quando a arvore e muito pequena.
c) Quando a arvore e desbalanceada, se parecendo com uma lista ligada.
d) Quando a arvore possui muitos nos.
Resposta correta: c)
Explicacao: No pior caso, quando a Arvore Binaria de Busca e desbalanceada e tem a forma de
uma lista ligada, a busca tem complexidade O(n), porque a arvore nao oferece nenhuma vantagem
em termos de divisao dos dados.
O que e um no folha em uma Arvore Binaria de Busca?
a) Um no que nao tem filhos a esquerda.
b) Um no que nao tem filhos a direita.
c) Um no que nao tem filhos.
d) Um no que possui filhos em ambas as direcoes.
Resposta correta: c)
Explicacao: Um no folha e um no que nao tem filhos, ou seja, nao tem filhos a esquerda nem a
direita.
O que caracteriza uma Arvore Binaria de Busca AVL?
a) A arvore e sempre balanceada apos cada operacao.
b) A diferenca entre a altura das subarvores esquerda e direita de qualquer no e sempre no maximo
1.
c) Todos os nos tem no maximo dois filhos.
d) A arvore possui, no maximo, tres niveis de profundidade.
Resposta correta: b)
Explicacao: Em uma arvore AVL, a diferenca entre a altura das subarvores esquerda e direita de
qualquer no nunca pode ser maior que 1. Isso garante que a arvore esteja balanceada.
Como e realizada a rotacao em uma arvore AVL para balanceamento?
a) Com troca de posicoes entre o no pai e o no filho.
b) A rotacao envolve deslocar o no raiz para a posicao de um de seus filhos.
c) A rotacao troca o no com a maior subarvore para a direita.
d) A rotacao pode ser simples ou dupla, dependendo da posicao do desequilibrio.
Resposta correta: d)
Explicacao: A rotacao pode ser simples ou dupla, dependendo da posicao do desequilibrio da
arvore. A rotacao e necessaria para manter a altura balanceada apos insercoes ou remocoes de
nos.
Qual e o objetivo principal de uma arvore Red-Black?
a) Garantir que a arvore tenha no maximo dois niveis de profundidade.
b) Manter a arvore balanceada, mas com algumas permissoes de desbalanceamento.
c) Aumentar a quantidade de filhos por no.
d) Evitar a duplicacao de valores na arvore.
Resposta correta: b)
Explicacao: A arvore Red-Black e uma arvore binaria de busca balanceada, mas com menos
restricoes em comparacao com a AVL. Ela mantem algumas permissoes de desbalanceamento,
mas ainda garante eficiencia nas operacoes.
O que ocorre quando voce remove um no em uma Arvore Binaria de Busca?
a) O no e simplesmente excluido.
b) O no e substituido por seu no esquerdo.
c) O no e substituido por seu no sucessor ou antecessor.
d) A arvore e reorganizada e balanceada automaticamente.
Resposta correta: c)
Explicacao: Quando um no e removido de uma Arvore Binaria de Busca, ele e substituido por seu
no sucessor ou antecessor para manter a propriedade de ordenacao da arvore.
Em uma Arvore Binaria de Busca, como um no e localizado?
a) Comparando o valor do no com o valor do no atual e escolhendo o lado esquerdo ou direito com
base nessa comparacao.
b) Buscando todos os nos recursivamente.
c) Iterando de baixo para cima pela arvore.
d) Realizando uma busca binaria diretamente na arvore.
Resposta correta: a)
Explicacao: A localizacao de um no em uma Arvore Binaria de Busca e feita comparando-se o valor
do no com o valor do no atual, e entao decidindo se a busca continuara a esquerda ou a direita,
conforme as regras da arvore.
Qual e a diferenca entre a altura e a profundidade de um no em uma Arvore Binaria de Busca?
a) A altura e a distancia ate a folha mais distante, e a profundidade e a distancia ate a raiz.
b) A altura e o numero de nos ate a raiz, e a profundidade e o numero de nos ate as folhas.
c) A altura e a distancia ate a folha mais distante, e a profundidade e o numero de nos do caminho
ate a raiz.
d) A altura e a profundidade sao a mesma coisa em uma arvore.
Resposta correta: a)
Explicacao: A altura de um no e a distancia ate a folha mais distante abaixo dele, enquanto a
profundidade e a distancia do no ate a raiz.
Qual operacao e mais eficiente em uma Arvore Binaria de Busca em termosde tempo?
a) Busca.
b) Insercao.
c) Remocao.
d) Todas as operacoes possuem a mesma eficiencia.
Resposta correta: a)
Explic