Estrutura De Dados TEMA 6

Prévia do material em texto

Você acertou 2 de 10 questões
Verifique o seu desempenho e continue treinando! Você pode refazer o exercício quantas
vezes quiser.
Verificar Desempenho
A
B
1 Marcar para revisão
Ano: 2015 Banca: NUCEPE Órgão: SEFAZ � PI Prova: Analista � Sistemas Pleno2015
Árvore AVL é uma árvore de busca autobalanceada. Isso significa que:
As alturas das duas subárvores a partir de cada nó diferem no máximo em uma
unidade.
Cada nó da árvore possui até três descendentes.
C
D
E
As alturas das duas subárvores a partir de cada nó diferem no máximo em duas
unidades.
Pode possuir até duas raízes.
As alturas das duas subárvores a partir de cada nó são exatamente iguais.
Resposta incorreta
Opa! A alternativa correta é a letra A. Confira o gabarito comentado!
Gabarito Comentado
A alternativa correta é a letra A. A árvore AVL, nomeada em homenagem aos seus
inventores Adelson-Velskii e Landis, é uma árvore de busca binária onde a diferença de
alturas de subárvores de qualquer nó é garantida para ser no máximo uma unidade. Se
em qualquer momento elas diferirem em mais de uma unidade, rebalanceamento é
feito para restaurar essa propriedade. As outras alternativas são incorretas pois não
descrevem corretamente as características de uma árvore AVL.
2 Marcar para revisão
A
B
C
D
E
As rotações são operações fundamentais para ajuste da propriedade AVL. Analise as
afirmativas abaixo.
I � A inserção de uma nova chave em uma árvore AVL pode desregular diversos nós no
caminho da raiz até a folha onde a nova chave foi inserida. Só é necessário aplicar uma
rotação no nó mais profundo desregulado.
Porque
II � A aplicação da rotação resulta em uma subárvore com a mesma altura da subárvore
original, isto é, antes da inserção da nova chave.
Marque a alternativa correta.
As duas afirmativas estão corretas e a segunda não justifica a primeira.
As duas afirmativas estão corretas e a segunda justifica a primeira.
As duas afirmativas são falsas.
A primeira afirmativa é verdadeira e a segunda afirmativa é falsa.
A primeira afirmativa é falsa e a segunda afirmativa é verdadeira.
Resposta incorreta
Opa! A alternativa correta é a letra B. Confira o gabarito comentado!
Gabarito Comentado
As operações de rotação em uma árvore AVL são fundamentais para manter o
equilíbrio da árvore. Quando uma nova chave é inserida, pode ocorrer um desequilíbrio
em vários nós no caminho da raiz até a folha onde a nova chave foi inserida. No
entanto, é suficiente aplicar uma rotação no nó mais profundo que está desequilibrado
para corrigir a situação (afirmativa I�. A rotação resulta em uma subárvore com a
mesma altura da subárvore original antes da inserção da nova chave (afirmativa II�.
Portanto, a segunda afirmativa justifica a primeira, pois explica o motivo pelo qual
apenas uma rotação é necessária para corrigir o desequilíbrio causado pela inserção
de uma nova chave.
3 Marcar para revisão
Ano: 2015 Banca: MP�RS Órgão: MP�RS Prova: Técnico em informática � Sistemas2015
Imagine que temos números de 1 a 100 em uma árvore de pesquisa binária �ABP�. Agora
queremos procurar o número 50. Assinale a alternativa que apresenta a possível sequência
de elementos da árvore consultada.
A
B
C
D
E
42 � 60 � 20 � 48 � 50.
40 � 10 � 45 � 30 � 50.
40 � 60 � 45 � 48 � 50.
40 � 15 � 45 � 30 � 50.
42 � 60 � 20 � 30 � 50.
Resposta incorreta
Opa! A alternativa correta é a letra C. Confira o gabarito comentado!
Gabarito Comentado
A sequência correta para encontrar o número 50 em uma árvore de pesquisa binária
�ABP� é 40 � 60 � 45 � 48 � 50. Em uma ABP, cada nó tem um valor. Se o valor que
estamos procurando é menor que o valor do nó, seguimos para a esquerda. Se o valor
que estamos procurando é maior, seguimos para a direita. Neste caso, começamos
com 40 (menor que 50�, depois vamos para 60 (maior que 50�, depois para 45 (menor
que 50�, depois para 48 (menor que 50� e finalmente chegamos a 50.
A
B
C
D
E
4 Marcar para revisão
Escola de Formação Complementar do Exército � EsFCEx Prova: CFO � Informática � 2019
Árvores binárias podem ser usadas para representar expressões aritméticas. Como um
exemplo de expressão, podemos ter: a * b + f sen - h * j com os elementos enumerados
"Em-ordem". Nesse caso, a árvore binária terá como raiz:
O átomo a
O átomo j
O átomo +
O átomo sen
O átomo *
Resposta incorreta
Opa! A alternativa correta é a letra C. Confira o gabarito comentado!
Gabarito Comentado
A
B
Na representação de expressões aritméticas por meio de árvores binárias, a raiz da
árvore é o operador principal da expressão. No caso da expressão dada, o operador
principal é o sinal de adição (+), que é o responsável por unir as duas partes da
expressão. Portanto, o átomo + é a raiz da árvore binária que representa a expressão
aritmética apresentada.
5 Marcar para revisão
Seja a seguinte árvore, marque a opção correta que indica o porquê a árvore abaixo não é
uma árvore binária de busca:
Não é uma árvore binária de busca pois está desbalanceada.
Não é uma árvore binária de busca pois o nó 35 deveria estar inserido à direita do
nó 20.
Questão 10 de 10
1 2 3 4 5
Exercicio Árvores Sair
C
D
E
Não é uma árvore binária de busca pois essa árvore deve estar perfeitamente
balanceada.
Não é uma árvore binária de busca pois esta árvore deve estar com os níveis de
suas folhas todas igualmente perfeitas.
Não é uma árvore binária de busca pois o nó 22 deveria estar inserido à direita do
nó 20.
Resposta correta
Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado!
Gabarito Comentado
Uma árvore binária de busca são árvores que obedecem às seguintes propriedades:
Dado um nó qualquer da árvore binária, todos os nós à esquerda dele são menores
ou iguais a ele.
Dado um nó qualquer da árvore binária, todos os nós à direita dele são maiores ou
iguais a ele.
Observe que a sub-árvore 20�22 não respeita a regra básica, portanto, o nó 22 deveria
estar a direita do nó 20.
Corretas �2�
Incorretas �8�
Em branco �0�
6 7 8 9 10
A
B
C
D
E
6 Marcar para revisão
As árvores binárias de busca são especializações das árvores binárias que permitem uma
melhor organização dos algoritmos de busca. Sobre a inserção de uma nova chave em uma
árvore binária de busca é correto afirmar que:
Toda nova chave é inserida obrigatoriamente na raiz.
Para determinar a posição da nova chave é necessário calcular o percurso em
ordem simétrica da árvore obtida. Com este percurso, verifica-se se a sequência
está ordenada em ordem crescente. Caso esteja, a posição da nova chave está
correta.
A complexidade da inserção é sempre O(n), independentemente da altura da
árvore.
Todas as chaves são inseridas em folhas, a posição da folha é determinada pela
busca.
O algoritmo de inserção em árvores binárias de busca é estático, isto é, é
necessário recalcular toda árvore para inserir uma nova chave.
Resposta incorreta
Opa! A alternativa correta é a letra D. Confira o gabarito comentado!
Gabarito Comentado
A alternativa correta é a D. Em uma árvore binária de busca, todas as chaves são
inseridas em folhas. A posição da folha é determinada pela busca. Isso ocorre porque a
árvore binária de busca é projetada para otimizar a busca de dados. Portanto, quando
uma nova chave é inserida, ela é colocada em uma posição que facilita a busca futura.
A chave não é inserida na raiz (como afirmado na alternativa A� nem requer o recálculo
de toda a árvore (como afirmado na alternativa E�. Além disso, a complexidade da
inserção não é sempre O(n), como afirmado na alternativa C. A complexidade pode
variar dependendo da altura da árvore. Por fim, a posição da nova chave não é
determinada pelo percurso em ordem simétrica da árvore, como afirmado na
alternativa B.
7 Marcar para revisão
Ano: 2012 Banca: IDECAN Órgão: BANESTES Prova: Analista de Tecnologia da Informação �
Desenvolvimento de Sistemas
Árvore de pesquisa é uma estrutura de dados eficiente para armazenar informação,sendo
particularmente adequada quando existe a necessidade de considerar todos ou alguma
combinação de registros. Assinale uma combinação correta desses registros.
A
B
C
D
E
Acesso direto e sequencial eficientes, facilidade de inserção e retirada de registro,
boa taxa de utilização de memória, utilização de memória primária e secundária.
Utilização de algoritmos de ordenação eficientes.
Utilização de estruturas de dados como lista, pilha e fila.
Não é necessário indexar os registros.
As operações de inserir, retirar e pesquisar são definidas.
Resposta incorreta
Opa! A alternativa correta é a letra A. Confira o gabarito comentado!
Gabarito Comentado
A alternativa correta é a letra A. A árvore de pesquisa é uma estrutura de dados que
permite um acesso direto e sequencial eficientes, além de facilitar a inserção e retirada
de registros. Ela também apresenta uma boa taxa de utilização de memória, podendo
utilizar tanto a memória primária quanto a secundária. As demais alternativas não
A
B
C
descrevem corretamente as características e funcionalidades de uma árvore de
pesquisa.
8 Marcar para revisão
Seja a seguinte árvore binária de busca abaixo, marque a sequência correta do percurso em
pós-ordem:
23,24,25,26,27,29,28
25,24,27,23,26,29,30
25,24,23,27,26,28,29
D
E
23,24,26,29,28,27,25
23,24,29,26,28,25,27
Resposta incorreta
Opa! A alternativa correta é a letra D. Confira o gabarito comentado!
Gabarito Comentado
O percurso em pós-ordem de uma árvore binária é definido pela seguinte sequência de
ações: primeiro, percorre-se recursivamente o lado esquerdo da raiz considerada; em
seguida, percorre-se recursivamente o lado direito; e, finalmente, visita-se a raiz.
Nesse caso, a sequência correta é a alternativa D� 23,24,26,29,28,27,25. Isso porque,
seguindo a regra de pós-ordem, primeiro percorremos a subárvore esquerda �23,24�,
depois a subárvore direita �26,29,28,27� e, por fim, visitamos a raiz �25�.
9 Marcar para revisão
Seja o seguinte código em Python cujo principal objetivo é implementar uma árvore binária.
Marque a alternativa correta quanto a execução do código:
A
B
C
D
E
A árvore criada no código acima é uma árvore binária de busca com todas as
folhas no último nível.
A árvore criada no código acima não é binária de busca.
A árvore criada no código é binária de busca com altura 6, isto é, com 6 níveis
distintos.
Não é possível inferir a topologia da árvore com base no código.
A classe NotArvore implementa regras que garantem que os nós inseridos
respeitam a ordem de inserção dos nós (maiores a direita e menores a esquerda).
Resposta incorreta
Opa! A alternativa correta é a letra A. Confira o gabarito comentado!
Gabarito Comentado
Apesar de que a função NoArvore não tem regras quanto à inserção dos nós, a forma
(e a ordem) de como os nós foram inseridos �55�35�75�65�85�25�45� formam uma
árvore binária de busca.
Resultado:
10 Marcar para revisão
Ano: 2020 Banca: Instituto AOCP Órgão: Prefeitura de Nova Hamburgo � RS Prova: Analista
de Desenvolvimento � Analista de Sistemas
Analise a seguinte árvore binária e assinale a alternativa correta.
A
B
C
D
E
"A" é filho de todos.
"B" e "C" são caules da árvore.
"B" tem grau de saída 3 e ¿C¿ grau 2.
TA é a subárvore enraizada em "A", portanto toda a árvore.
Com exceção do nó "A", que é raiz, os demais nós são conhecido como folhas
Resposta correta
Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado!
Gabarito Comentado
Resposta correta: TA é a subárvore enraizada em "A", portanto toda a árvore.