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

Questões para Estudantes

semana passada

Questões para Estudantes

semana passada

6 pág.

Respostas

semana passada

Em uma árvore binária de busca (BST) balanceada, a complexidade média de busca é O(log n). Isso ocorre porque, em uma árvore balanceada, a altura da árvore é mantida em logaritmo da quantidade de nós, permitindo que a busca seja realizada de forma eficiente, dividindo o espaço de busca pela metade a cada comparação. Portanto, a alternativa correta é: c) O(log n).

Essa resposta te ajudou?

Ainda com dúvidas?

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

Essa pergunta também está no material:

6 pág.

Árvore binária de busca

Mais perguntas desse material

O que define uma arvore binaria de busca (BST)?
a) Cada no pode ter qualquer numero de filhos, sem restricoes
b) Cada no possui no maximo dois filhos e valores menores a esquerda e maiores a direita
c) E uma arvore que armazena apenas numeros primos
d) E uma lista encadeada com referencias para nos filhos

Quando a busca em uma BST pode ter complexidade O(n)?
a) Quando a arvore e balanceada
b) Quando todos os nos estao alinhados como uma lista encadeada
c) Quando ha apenas a raiz
d) Isso nunca ocorre

Ao inserir um valor em uma BST, qual e a regra que deve ser seguida?
a) Sempre adicionar o novo no a direita da raiz
b) Comparar o valor com a raiz e, dependendo, seguir para a subarvore esquerda ou direita recursivamente
c) Adicionar na primeira posicao disponivel
d) Inserir apenas em folhas

Qual e o percurso que produz os valores em ordem crescente em uma BST?
a) Pre-ordem
b) Pos-ordem
c) Em-ordem (inorder)
d) Nenhum percurso especifico

Em uma BST, como identificar rapidamente o menor valor?
a) Seguindo sempre o filho direito ate a folha
b) Seguindo sempre o filho esquerdo ate a folha
c) Pegando o valor da raiz
d) Calculando a media dos valores

Qual e o maior valor em uma BST e como encontra-lo?
a) E a raiz da arvore
b) Seguindo sempre o filho direito ate um no sem filho direito
c) Seguindo sempre o filho esquerdo ate um no sem filho esquerdo
d) Calculando a media dos valores de todas as folhas

Ao remover um no com dois filhos em uma BST, qual e a abordagem padrao?
a) Remover o no e substituir por um valor aleatorio
b) Substituir o no pelo maior valor da subarvore esquerda ou pelo menor da subarvore direita
c) Remover a arvore inteira
d) Nao e possivel remover nos com dois filhos

Qual e a vantagem de usar uma BST balanceada em comparacao com uma BST desbalanceada?
a) Menor consumo de memoria
b) Operacoes de busca, insercao e remocao tem complexidade garantida O(log n)
c) Permite armazenar apenas numeros pares
d) Nao ha vantagem real

Em uma BST, se todos os elementos forem inseridos em ordem crescente, como sera a estrutura da arvore?
a) Totalmente balanceada
b) Uma lista ligada para a direita
c) Uma lista ligada para a esquerda
d) Uma arvore cheia

Estrutura de Dados

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

Árvore binária de busca

Respostas

Ainda com dúvidas?

Essa pergunta também está no material:

Árvore binária de busca

Quando a busca em uma BST pode ter complexidade O(n)?
a) Quando a arvore e balanceada
b) Quando todos os nos estao alinhados como uma lista encadeada
c) Quando ha apenas a raiz
d) Isso nunca ocorre

Ao inserir um valor em uma BST, qual e a regra que deve ser seguida?
a) Sempre adicionar o novo no a direita da raiz
b) Comparar o valor com a raiz e, dependendo, seguir para a subarvore esquerda ou direita recursivamente
c) Adicionar na primeira posicao disponivel
d) Inserir apenas em folhas

Qual e o percurso que produz os valores em ordem crescente em uma BST?
a) Pre-ordem
b) Pos-ordem
c) Em-ordem (inorder)
d) Nenhum percurso especifico

Em uma BST, como identificar rapidamente o menor valor?
a) Seguindo sempre o filho direito ate a folha
b) Seguindo sempre o filho esquerdo ate a folha
c) Pegando o valor da raiz
d) Calculando a media dos valores

Qual e o maior valor em uma BST e como encontra-lo?
a) E a raiz da arvore
b) Seguindo sempre o filho direito ate um no sem filho direito
c) Seguindo sempre o filho esquerdo ate um no sem filho esquerdo
d) Calculando a media dos valores de todas as folhas

Ao remover um no com dois filhos em uma BST, qual e a abordagem padrao?
a) Remover o no e substituir por um valor aleatorio
b) Substituir o no pelo maior valor da subarvore esquerda ou pelo menor da subarvore direita
c) Remover a arvore inteira
d) Nao e possivel remover nos com dois filhos

Qual e a vantagem de usar uma BST balanceada em comparacao com uma BST desbalanceada?
a) Menor consumo de memoria
b) Operacoes de busca, insercao e remocao tem complexidade garantida O(log n)
c) Permite armazenar apenas numeros pares
d) Nao ha vantagem real

Em uma BST, se todos os elementos forem inseridos em ordem crescente, como sera a estrutura da arvore?
a) Totalmente balanceada
b) Uma lista ligada para a direita
c) Uma lista ligada para a esquerda
d) Uma arvore cheia

Mais conteúdos dessa disciplina

Estrutura de Dados

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

Árvore binária de busca

Respostas

Ainda com dúvidas?

Essa pergunta também está no material:

Árvore binária de busca

Quando a busca em uma BST pode ter complexidade O(n)?a) Quando a arvore e balanceadab) Quando todos os nos estao alinhados como uma lista encadeadac) Quando ha apenas a raizd) Isso nunca ocorre

Ao inserir um valor em uma BST, qual e a regra que deve ser seguida?a) Sempre adicionar o novo no a direita da raizb) Comparar o valor com a raiz e, dependendo, seguir para a subarvore esquerda ou direita recursivamentec) Adicionar na primeira posicao disponiveld) Inserir apenas em folhas

Qual e o percurso que produz os valores em ordem crescente em uma BST?a) Pre-ordemb) Pos-ordemc) Em-ordem (inorder)d) Nenhum percurso especifico

Em uma BST, como identificar rapidamente o menor valor?a) Seguindo sempre o filho direito ate a folhab) Seguindo sempre o filho esquerdo ate a folhac) Pegando o valor da raizd) Calculando a media dos valores

Qual e o maior valor em uma BST e como encontra-lo?a) E a raiz da arvoreb) Seguindo sempre o filho direito ate um no sem filho direitoc) Seguindo sempre o filho esquerdo ate um no sem filho esquerdod) Calculando a media dos valores de todas as folhas

Ao remover um no com dois filhos em uma BST, qual e a abordagem padrao?a) Remover o no e substituir por um valor aleatoriob) Substituir o no pelo maior valor da subarvore esquerda ou pelo menor da subarvore direitac) Remover a arvore inteirad) Nao e possivel remover nos com dois filhos

Qual e a vantagem de usar uma BST balanceada em comparacao com uma BST desbalanceada?a) Menor consumo de memoriab) Operacoes de busca, insercao e remocao tem complexidade garantida O(log n)c) Permite armazenar apenas numeros paresd) Nao ha vantagem real

Em uma BST, se todos os elementos forem inseridos em ordem crescente, como sera a estrutura da arvore?a) Totalmente balanceadab) Uma lista ligada para a direitac) Uma lista ligada para a esquerdad) Uma arvore cheia

Mais conteúdos dessa disciplina

Quando a busca em uma BST pode ter complexidade O(n)?
a) Quando a arvore e balanceada
b) Quando todos os nos estao alinhados como uma lista encadeada
c) Quando ha apenas a raiz
d) Isso nunca ocorre

Ao inserir um valor em uma BST, qual e a regra que deve ser seguida?
a) Sempre adicionar o novo no a direita da raiz
b) Comparar o valor com a raiz e, dependendo, seguir para a subarvore esquerda ou direita recursivamente
c) Adicionar na primeira posicao disponivel
d) Inserir apenas em folhas

Qual e o percurso que produz os valores em ordem crescente em uma BST?
a) Pre-ordem
b) Pos-ordem
c) Em-ordem (inorder)
d) Nenhum percurso especifico

Em uma BST, como identificar rapidamente o menor valor?
a) Seguindo sempre o filho direito ate a folha
b) Seguindo sempre o filho esquerdo ate a folha
c) Pegando o valor da raiz
d) Calculando a media dos valores

Qual e o maior valor em uma BST e como encontra-lo?
a) E a raiz da arvore
b) Seguindo sempre o filho direito ate um no sem filho direito
c) Seguindo sempre o filho esquerdo ate um no sem filho esquerdo
d) Calculando a media dos valores de todas as folhas

Ao remover um no com dois filhos em uma BST, qual e a abordagem padrao?
a) Remover o no e substituir por um valor aleatorio
b) Substituir o no pelo maior valor da subarvore esquerda ou pelo menor da subarvore direita
c) Remover a arvore inteira
d) Nao e possivel remover nos com dois filhos

Qual e a vantagem de usar uma BST balanceada em comparacao com uma BST desbalanceada?
a) Menor consumo de memoria
b) Operacoes de busca, insercao e remocao tem complexidade garantida O(log n)
c) Permite armazenar apenas numeros pares
d) Nao ha vantagem real

Em uma BST, se todos os elementos forem inseridos em ordem crescente, como sera a estrutura da arvore?
a) Totalmente balanceada
b) Uma lista ligada para a direita
c) Uma lista ligada para a esquerda
d) Uma arvore cheia