[Exercícios] Árvores

1) Considere a árvore binária da figura a seguir:



Os resultados das consultas dos nós dessa árvore binária em pré-ordem e pós-ordem são, respectivamente: 
A) (2 4 6 8 12 16) e (2 6 8 4 16 12). 
B) (12 4 2 8 6 16) e (2 4 6 8 12 16). 
C) (2 6 8 4 16 12) e (12 4 2 8 6 16). 
D) (2 4 6 8 12 16) e (12 4 2 8 6 16). 
E) (12 4 2 8 6 16) e (2 6 8 4 16 12). 

2) A operação de destruição de uma árvore requer um tipo de percurso em que a liberação de um nó é realizada apenas após todos os seus descendentes terem sido também liberados. Segundo essa descrição, a operação de destruição de uma árvore deve ser implementada utilizando o percurso

A) em ordem. 
B) pré-ordem. 
C) central. 
D) simétrico. 
E) pós-ordem. 

3) Uma árvore balanceada T que armazena n chaves é uma árvore binária de pesquisa na qual 
A) A diferença entre as alturas de suas subárvores permanece constante em todo o caso, após inserções ou remoções de chaves. 
B) As operações de inserção e remoção de chaves em nodos internos v de T seguem um padrão linear de tempo de execução. 
C) A propriedade da altura/balanceamento é determinada pela extensão do caminho mais curto entre um nodo interno v até o nodo raiz de T. 
D) A variação da altura dos nodos filhos de cada nodo interno v de T é de, no máximo, uma unidade. 
E) o tempo de execução para todas as operações fundamentais sobre cada nodo interno v de T se mantém constante. 


4) Considere T uma árvore binária cheia, em que n, ne, ni e h representam o número de nós, o número de nós externos, o número de nós internos e a altura de T, respectivamente. Portanto, a essa árvore T aplica-se a seguinte propriedade:

(A) ni = ne + 1
(B) h - 1 ≤ ne ≤ 2h
(C) h + 1 ≤ ni ≤ 2h
(D) log(n+1) ≤ h ≤ n - 1
(E) 2h + 1 ≤ n ≤ 2h+1 – 1

5) Sobre árvores binárias, considere as afirmativas a seguir.
I. Qualquer nó de uma árvore binária é raiz de, no máximo, outras duas subárvores comumente denominadas subárvore direita e subárvore esquerda.
II. Uma dada árvore binária A armazena números inteiros e nela foram inseridos 936 valores não repetidos. Para determinar se um número x está entre os elementos dessa árvore, tal número será comparado, no máximo, com 10 números contidos na árvore A.
III. Uma dada árvore binária de busca A armazena números inteiros e nela foram inseridos 936 valores não repetidos. Para determinar se um número x está entre os elementos dessa árvore, serão feitas, no máximo, 10 comparações.
IV. Uma dada árvore binária de busca A armazena números inteiros e nela foram inseridos 936 valores não repetidos. Supondo que r seja o nó raiz da árvore A e que sua subárvore esquerda contenha 460 elementos e sua subárvore direita possua 475 elementos. Para determinar se um número x pertence a essa árvore, serão feitas, no máximo, 476 comparações.

Assinale a alternativa correta.
a) Somente as afirmativas I e II são corretas.
b) Somente as afirmativas I e IV são corretas.
c) Somente as afirmativas III e IV são corretas.
d) Somente as afirmativas I, II e III são corretas.
e) Somente as afirmativas II, III e IV são corretas.

6) Considere um grafo não dirigido G = (V,E), onde V é o conjunto de vértices e E o conjunto de arestas, no qual cada aresta possui um peso. G é uma instância para o Problema do Caixeiro Viajante (PCV), onde cada um de seus vértices são cidades e cada uma de suas arestas corresponde à ligação entre essas cidades. O peso de cada aresta corresponde à distância entre as duas extremidades. A árvore de busca, a seguir, corresponde à busca pela solução realizada por um algoritmo para o PCV. Sabendo-se que a busca pela solução ocorreu por profundidade, os nós da árvore de busca são analisados, explorando os “filhos” mais à esquerda primeiro (vértices com menor número).

Com base na estratégia de “poda” a ser utilizada para melhorar o desempenho e na análise das características da árvore de busca sobre a instância G, atribua V (verdadeiro) ou F (falso) às afirmativas a seguir.
( ) Ao encontrar o primeiro melhor caminho, deve-se registrá-lo, para não analisar caminhos que possuam mais vértices que este.
( ) Durante a abertura dos nós na árvore de busca, parar de seguir o caminho quando um ciclo é pior que o melhor encontrado até então.
( ) Manter o ciclo hamiltoniano de menor custo encontrado até então. Se, durante a busca, o caminho analisado ultrapassar este menor custo, parar tentativa por aquele caminho.
( ) Manter a distância atual do caminho percorrido e evitar abrir nós que a ultrapassem.
( ) Não realizar caminhos inversos aos que já foram analisados.
Assinale a alternativa que contém, de cima para baixo, a sequência correta.
a) V, V, F, V, F.
b) V, F, V, F, V.
c) F, V, F, V, F.
d) F, V, F, F, V.
e) F, F, V, F, V.


7) Observe a Árvore Binária de Busca (ABB) a seguir.



Assinale a alternativa que apresenta, corretamente, a sequência de inserção que gera essa ABB.

a) 30, 15, 40, 10, 20, 60, 80
b) 30, 15, 40, 10, 20, 80, 60
c) 30, 15, 60, 10, 20, 40, 80
d) 30, 60, 20, 80, 15, 10, 40
e) 30, 60, 40, 10, 20, 15, 80


8) Quanto à análise de algoritmos, considere as afirmativas a seguir.
I. A programação dinâmica pode levar a soluções eficientes para algoritmos recursivos com complexidade exponencial.
II. Os algoritmos tentativa e erro são impraticáveis com solução recursiva, pois são aplicados exaustivamente.
III. Um algoritmo recursivo tem tempo de execução inferior à codificação iterativa para a solução do mesmo problema.
IV. Uma árvore binária de pesquisa é adequada para a solução de problemas de natureza recursiva.

Assinale a alternativa correta.
a) Somente as afirmativas I e II são corretas.
b) Somente as afirmativas I e IV são corretas.
c) Somente as afirmativas III e IV são corretas.
d) Somente as afirmativas I, II e III são corretas.
e) Somente as afirmativas II, III e IV são corretas.

9) Um problema das árvores binárias de buscas convencionais é que a disposição dos elementos pode ficar semelhante à de uma estrutura linear, na qual as árvores criam uma profundidade maior que sua largura, como ocorre, por exemplo, em inserção de chaves em ordem crescente. Em árvores com essa característica, não há ganho substancial quanto ao tempo de busca de uma lista, por exemplo. As árvore AVL e SBB
são árvores projetadas para evitar esse problema e balancear o tempo de busca a seus elementos. Quanto às árvores AVL e SBB, assinale a alternativa que apresenta, corretamente, suas características.
a) Árvores AVL utilizam altura das subárvores como critério de balanceamento, enquanto árvores SBB utilizam orientação vertical e horizontal dos “apontadores” dos nós.
b) Árvores AVL utilizam quatro tipos diferentes de algoritmos de balanceamento, enquanto árvores SBB utilizam apenas dois tipos genéricos (direita e esquerda), levando em consideração a origem e a propagação de uma violação.
c) Árvores SBB utilizam alturas das subárvores como critério de balanceamento, enquanto árvores AVL utilizam orientação vertical e horizontal dos “apontadores” dos nós.
d) Árvores SBB utilizam quatro tipos diferentes de algoritmos de balanceamento, enquanto árvores AVL utilizam apenas dois tipos genéricos (direita e esquerda), levando em consideração a origem e a propagação de uma
violação.
e) As árvores AVL e SBB possuem diferença quanto à estrutura dos nós e à composição das chaves e das funções de busca, de inserção e de remoção.

10) Assinale a alternativa em que todas as propriedades de uma árvore vermelho e preto são verdadeiras.
a) Todo nó é vermelho ou preto. A raiz pode ser vermelha ou preta. Todas as folhas são vermelhas.
b) A raiz é preta. Todas as folhas são vermelhas. Para cada nó, todos os caminhos, desde um nó até as folhas
descendentes, contêm um mesmo número de nós pretos.
c) Toda folha é preta. Todo nó é vermelho ou preto. A raiz é preta.
d) Se um nó é vermelho, ambos os filhos são vermelhos. A raiz pode ser vermelha ou preta. Todas as folhas são pretas.
e) Todas as folhas são vermelhas. Todo nó é vermelho ou preto. A raiz pode ser vermelha ou preta.


11) Os algoritmos a seguir representam os três caminhamentos para árvores binárias.

caminhamento(binário)
se binário.esquerda 6= NULL então caminhamento(binário.esquerda)
escrever binário.valor
se binário.direita 6= NULL então caminhamento(binário.direita)

caminhamento(binário)
escrever binário.dado
se binário.esquerda 6= NULL então caminhamento(binário.esquerda)
se binário.direita 6= NULL então caminhamento(binário.direita)

caminhamento(binário)
se binário.esquerda 6= NULL então caminhamento(binário.esquerda)
se binário.direita 6= NULL então caminhamento(binário.direita)
escrever binário.valor

Assinale a alternativa que contém os nomes dos 3 caminhamentos, respectivamente.
a) pré-ordem, pós-ordem, em-ordem
b) pré-ordem, em-ordem, pós-ordem
c) pós-ordem, pré-ordem, em-ordem
d) em-ordem, pré-ordem, pós-ordem
e) em-ordem, pós-ordem, pré-ordem


12) Em uma Árvore B de ordemm, temos que: (i) cada nó contém no mínimomregistros (em+1 descendentes) e no máximo 2m registros (e 2m+1 descendentes), exceto o nó raiz que pode conter entre 1 e 2m registros; (ii) todas os nós folha aparecem no mesmo nível.  Sobre Árvores B, é correto afirmar:
a) O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser inserido em um nó
com 2m registros.
b) O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser inserido em um nó com
menos de 2m registros.
c) O particionamento de nós em uma Árvore B ocorre quando a chave do registro a ser inserido contém um valor
(conteúdo) intermediário entre os valores das chaves dos registros contidos no mesmo nó.
d) O particionamento de nós ocorre quando é necessário diminuir a altura da árvore.
e) Em uma Árvore B, aumenta em um nível sua altura, toda vez que ocorre o particionamento de um nó.


13) Considere uma árvore binária de busca T com n nós e altura h. A altura de uma árvore é o número máximo de nós de um caminho entre a raiz e as folhas. Analise as afirmativas a seguir:
I. h < 1 + log2 n ;
II. Todo nó que pertence à subárvore esquerda de um nó x tem valor maior que o pai de x.
III. Uma busca em ordem simétrica (in-order) em T produz uma ordenação crescente dos elementos de T.

Assinale a alternativa CORRETA:
A) Apenas a afirmativa I está correta;
B) Apenas a afirmativa II está correta;
C) Apenas a afirmativa III está correta;
D) Apenas as afirmativas I e II estão corretas;
E) Apenas as afirmativas I e III estão corretas.


14) Percorrendo a árvore binária a seguir em pré-ordem, obtemos que seqüência de
caracteres?



A) A C G F B E D
B) G C F A E B D
C) A B C D E F G
D) D B E A F C G
E) A B D E C F G

15) Dado um conjunto C contendo n inteiros distintos, qual das seguintes estruturas de
dados em memória principal permite construir um algoritmo para encontrar o valor
máximo de C em tempo constante?

A) Um vetor não ordenado.
B) Um vetor ordenado.
C) Uma árvore binária de busca balanceada.
D) Uma lista encadeada simples ordenada em ordem crescente.
E) Uma árvore rubro-negra.

16) Quais das seguintes propriedades não se aplicam a árvores rubro-negras?
A) Todo nó é vermelho ou preto.
B) Todo nó folha é preto.
C) Se um nó é preto, ambos seus filhos são vermelhos.
D) Se um nó é vermelho, ambos seus filhos são negros.
E) Todos os caminhos simples entre um nó e suas folhas descendentes contêm o
mesmo número de nós pretos.

17) Considere a árvore minimax abaixo, representando um jogo onde queremos
maximizar o valor da função de avaliação estática:

 

Assinale a alternativa que apresenta a quantidade de nós que não deverão ser
visitados em uma busca da melhor jogada se a estratégia de poda alfa-beta for utilizada.

A) 5
B) 8
C) 9
D) 10
E) 11


18) Seja T uma árvore AVL vazia. Supondo que os elementos 5, 10, 11, 7, 9, 3 e 6
sejam inseridos nessa ordem em T, indique a sequência abaixo que corresponde a um
percurso de T em pós-ordem.
(a) 3, 5, 6, 7, 9, 10 e 11.
(b) 7, 5, 3, 6, 10, 9 e 11.
(c) 9, 10, 7, 6, 11, 5 e 3.
(d) 11, 10, 9, 7, 6, 5 e 3.
(e) 3, 6, 5, 9, 11, 10 e 7.

19) Levando em conta as podas alfa-beta na árvore Mini-Max abaixo, assinale a
alternativa que apresenta a quantidade de folhas que deverão ser visitadas

 
(a) 7
(b) 8
(c) 10
(d) 11
(e) 13

Respostas:
1) E
2) E
3) D
4) E
5) B
6) E
7) C
8) B
9) A
10) C
11) D
12) A
13) C
14) E
15) B
16) C
17) B
18) E
19) B
[Exercícios] Árvores [Exercícios] Árvores Reviewed by Vinicius dos Santos on 06:17:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!