Estrutura de Dados II - Árvores Binárias de Busca e AVL

Prévia do material em texto

27/06/2019 Unicesumar - Ensino a Distância
1/8
ATIVIDADE 2 - ADS - ESTRUTURA DE DADOS II - 2019B
Período:17/06/2019 08:00 a 05/07/2019 23:59 (Horário de Brasília)
Status:ABERTO
Nota máxima:0,50
Gabarito:Gabarito será liberado no dia 06/07/2019 00:00 (Horário de Brasília)
Nota obtida:
1ª QUESTÃO
Para resolver o problema do desbalanceamento de árvores binárias de busca, os pesquisadores Adelson-
Velskii e Landis, em 1962, criaram um algoritmo que leva as iniciais de seus nomes. Tendo em mente os
conhecimentos básicos a respeito das Árvores Binárias de Busca e Árvores AVL, avalie as afirmações que se
seguem.
I - Em uma árvore AVL, nós folha devem admitir que a altura de seus filhos é igual a -1.
II - O fator de balanceamento é calculado através da diferença entre os fatores de balanceamento de seus
filhos.
III - Um nó desbalanciado através da inserção de um elemento na subárvore esquerda do filho à direita
desse nó pode ser balanceado novamente através de rotação dupla.
Com base no exposto é possível concluir que estão corretas as afirmações:
ALTERNATIVAS
I, apenas.
III, apenas.
I e II, apenas.
I e III, apenas.
I, II e III.
2ª QUESTÃO
27/06/2019 Unicesumar - Ensino a Distância
2/8
A principal característica de uma árvore binária é que cada um dos elementos pode ter, no máximo, dois
filhos. Se a figura abaixo representar uma árvore binária de busca, qual seria o caminho percorrido entre a
raiz 1 até a folha de valor 10 ?
Assinale a alternativa correta.
ALTERNATIVAS
1, 2, 35, 6.
1, 2, 5, 10.
1, 2, 5, 9, 5, 10.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
A figura não representa uma árvore binária de busca.
Atenção! Questão anulada.
ALTERNATIVAS
I e II, apenas.
I, III e V, apenas.
I, II e IV, apenas.
I, II, III e V, apenas.
I, II, III, IV e V.
4ª QUESTÃO
27/06/2019 Unicesumar - Ensino a Distância
3/8
Para resolver o problema do desbalanceamento de árvores binárias de busca, os pesquisadores Adelson-
Velskii e Landis, em 1962, criaram um algoritmo que leva as iniciais de seus nomes. Com base na árvore
ilustrada a seguir, avalie as afirmações que se seguem.
  
I - Os nós 18, 29 e 43 estão desbalanceados, com fator de balanceamento igual a 2, em valor absoluto.
II - Ao rotacionar o nó 15 à direita, teremos o nó 18 sendo filho do nó 15.
III - Ao rotacionar o nó 15 à direita, o próprio nó 15 é "adotado" pelo nó 31.
Com base no exposto é possível concluir que estão corretas as afirmações:
ALTERNATIVAS
I, apenas.
III, apenas.
I e II, apenas.
I e III, apenas.
I, II e III.
5ª QUESTÃO
27/06/2019 Unicesumar - Ensino a Distância
4/8
Para resolver o problema do desbalanceamento de árvores binárias de busca, os pesquisadores Adelson-
Velskii e Landis, em 1962, criaram um algoritmo que leva as iniciais de seus nomes. Considere a seguinte
ilustração de rotação em uma árvore AVL.
Assim sendo, avalie as afirmações a seguir.
I - Ao realizar a rotação a especificada anteriormente, o nó u passa a ser raiz da árvore como um todo.
II - Nesse caso, após a rotação, a subárvore B é descartada.
III - É possível afirmar que o desbalanceamento foi causado por uma inserção na subárvore C.
É correto o que se afirma em:
ALTERNATIVAS
I, apenas.
III, apenas.
I e II, apenas.
I e III, apenas.
I, II e III.
Atenção! Questão anulada.
ALTERNATIVAS
I, apenas.
III, apenas.
I e II, apenas.
I e III, apenas.
I, II e III.
27/06/2019 Unicesumar - Ensino a Distância
5/8
7ª QUESTÃO
Para resolver o problema do desbalanceamento de árvores binárias de busca, os pesquisadores Adelson-
Velskii e Landis, em 1962, criaram um algoritmo que leva as iniciais de seus nomes. Com base na árvore
ilustrada a seguir, avalie as afirmações que se seguem.    
    
I - É possível afirmar, com certeza que o desbalanceamento foi causado pela inserção do 63.
II - O nó 63 está desbalanceado.
III - É preciso realizar uma rotação dupla esquerda-direita para balancear essa árvore.
Com base no exposto é possível concluir que estão corretas as afirmações:
ALTERNATIVAS
I, apenas.
III, apenas.
I e II, apenas.
I e III, apenas.
I e III, apenas. E) I, II e III.
8ª QUESTÃO
27/06/2019 Unicesumar - Ensino a Distância
6/8
Existem basicamente duas formas de organizar uma estrutura de dados que representa árvores. Pode-se
criar uma árvore alocando posições de memória dinamicamente ou simplesmente utilizar um vetor estático.
Com base no esquema recém apresentado, analise as alternativas e assinale a correta.
ALTERNATIVAS
Esta árvore é binária completa.
Esta árvore não pode ser considerada estritamente binária.
Pode-se dizer que esquema da figura ilustra uma árvore binária armazenada em um vetor dinâmico.
Imagine que há a necessidade de adicionar mais um nó H, o qual seria filho direito de D. Nesse caso, o vértice seria
armazenado na posição 9 do vetor.
Na figura, para se encontrar a posição do filho esquerdo, pode-se aplicar a seguinte fórmula: E = 2 * P, onde E é a
posição do filho esquerdo, e P é a posição do pai.
9ª QUESTÃO
27/06/2019 Unicesumar - Ensino a Distância
7/8
Para resolver o problema do desbalanceamento de árvores binárias de busca, os pesquisadores Adelson-
Velskii e Landis, em 1962, criaram um algoritmo que leva as iniciais de seus nomes. Tendo em mente os
conhecimentos básicos a respeito das Árvores Binárias de Busca e Árvores AVL, associe os números cada
uma das rotações listadas a seguir com a descrição correta da causa que levaria à necessidade de aplicação
da respectiva rotação.
(1) Rotação simples à direita.
(2) Rotação simples à esquerda.
(3) Rotação dupla esquerda-direita.
(4) Rotação dupla direita-esquerda.
(  ) Inserção na subárvore esquerda do filho à direita do nó desbalanceado.
(  ) Inserção à direita do filho à direita do nó desbalanceado. 
(  ) Inserção na subárvore esquerda do filho à esquerda do nó desbalanceado.
(  ) Inserção à direita do filho à esquerda em relação ao nó desbalanceado.
   
De cima para baixo, a ordem de preenchimento dos parênteses é:
ALTERNATIVAS
3, 1, 2, 4
4, 2, 1, 3
3, 2, 1, 4
4, 1, 2, 3
2, 1, 3, 4
10ª QUESTÃO
27/06/2019 Unicesumar - Ensino a Distância
8/8
Para resolver o problema do desbalanceamento de árvores binárias de busca, os pesquisadores Adelson-
Velskii e Landis, em 1962, criaram um algoritmo que leva as iniciais de seus nomes. Com base na árvore
ilustrada a seguir, avalie as afirmações que se seguem.     
 
I - A altura do nó 77 é igual a 3.
II - O nó 31 encontra-se desbalanceado com fator de balanceamento igual a 2, em valor absoluto.
III - Para balancear essa árvore é preciso executar uma rotação dupla esquerda-direita envolvendo a
subárvore com raiz em 31.
Com base no exposto é possível concluir que estão corretas as afirmações:
ALTERNATIVAS
I, apenas.
III, apenas.
I e II, apenas.
I e III, apenas.
I, II e III.