Logo Passei Direto
Buscar

Estrutura de Dados

Outros

Qual e a complexidade de insercao de um novo no em uma BST balanceada? a) O(n2) b) O(log n) c) O(n) d) O(1)

User badge image
Questões para Estudantes

semana passada

User badge image
Questões para Estudantes

semana passada

Árvore binária de busca
6 pág.

Árvore binária de busca

Respostas

User badge image

Ed Verified user icon

semana passada

Para determinar a complexidade de inserção de um novo nó em uma Árvore de Busca Binária (BST) balanceada, precisamos considerar como a árvore é estruturada. Em uma BST balanceada, a altura da árvore é mantida em O(log n), onde n é o número de nós na árvore. Isso significa que, ao inserir um novo nó, você precisa percorrer a altura da árvore para encontrar a posição correta para a inserção. Portanto, a complexidade de inserção em uma BST balanceada é O(log n). A alternativa correta é: b) O(log n).

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

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

Essa pergunta também está no material:

Árvore binária de busca
6 pág.

Árvore binária de busca

Mais perguntas desse material

O que caracteriza uma arvore binaria de busca (BST)?
a) Cada no pode ter no maximo tres filhos e os valores sao armazenados em sequencia aleatoria.
b) Cada no possui no maximo dois filhos, sendo que todos os valores do filho esquerdo sao menores que o no pai e todos os valores do filho direito sao maiores.
c) Todos os nos possuem exatamente dois filhos, independentemente dos valores.
d) Os elementos da arvore sao armazenados em forma de lista encadeada.

Qual e a complexidade media de busca em uma BST balanceada?
a) O(n2)
b) O(n)
c) O(log n)
d) O(1)

Em uma BST, onde esta localizado o menor valor?
a) Na raiz
b) No no mais a esquerda
c) No no mais a direita
d) Em qualquer folha

Em uma BST, qual e o local do maior valor?
a) Na raiz
b) No no mais a esquerda
c) No no mais a direita
d) No primeiro filho que tiver apenas um descendente

Quando um no e removido de uma BST e ele possui dois filhos, qual procedimento e geralmente adotado?
a) Remover o no e deixar os filhos desconectados.
b) Substituir o no pelo menor valor da subarvore direita ou pelo maior valor da subarvore esquerda.
c) Substituir o no pelo filho esquerdo apenas.
d) Substituir o no pelo filho direito apenas.

Qual tipo de percurso em uma BST imprime os elementos em ordem crescente?
a) Pre-ordem
b) Pos-ordem
c) Em ordem (in-order)
d) Nivel por nivel (level-order)

Qual tipo de percurso pode ser usado para copiar uma BST mantendo a mesma estrutura?
a) Pre-ordem
b) Pos-ordem
c) Em ordem
d) Nivel por nivel

Se uma BST nao estiver balanceada, qual sera a complexidade de busca no pior caso?
a) O(1)
b) O(log n)
c) O(n)
d) O(n2)

O que e considerado a raiz de uma BST?
a) O no com maior valor
b) O no com menor valor
c) O primeiro no inserido ou no superior que nao possui pai
d) Qualquer no interno

Mais conteúdos dessa disciplina