Exercicio arvores
As árvores no mundo da computação são estruturas de dados genéricas que ajudam a solucionar vários problemas. Árvore binária, Arvore B, Arvore AVL, Arvore rubro negra, são variações dessa estrutura. Outro assunto bastante recorrente na área são as operações de busca dentro dessas estruturas, essas operações envolvem algoritmos recursivos e costumam dar um nó na nossa cabeça.
Nesse post você vai encontrar vários exercícios sobre arvores e suas variações. Além disso, todos fizemos questão de exercícios resolvidos de arvore para apoiar seu aprendizado.
Atenção: todas as questões desse artigo foram aplicadas na POSCOMP e são de domínio público. Esse artigo tem a finalidade apoiar o ensino de computação e foram publicadas aqui com fim exclusivamente educativo.
1) [POSCOMP 2016 – FUNDATEC] 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:
Em pré-ordem percorre-se primeiro visitando a raiz e depois a sub-árvore da esquerda depois da direita. Ou seja: 12, 4, 2, 8 ,6 16
Em pós-ordem a raiz é a ultima a ser visitada: Sendo assim: 2,6,8,4,16,12
Resposta correta (E)
2) [POSCOMP 2016 – FUNDATEC] 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
Considerando que a raiz das árvores contém o ponteiro para os dois nós associados (sub-árvore da esquerda e sub-árvore da direita) então é necessário visitar todas subárvores e liberando os nós folha e posteriormente os nós raiz. Ou seja, esse percurso deve deixar a raiz por ultimo, caracterizando o percurso pós-ordem
Resposta correta (E)
3) [POSCOMP 2016 – FUNDATEC] Uma árvore balanceada T que armazena n chaves é uma árvore binária de pesquisa na qual
Existem diversos tipos de árvores balanceadas (técnicas para manter o balanceamento). Uma árvore é balanceada se a diferença de altura entre duas sub-árvores difere em apenas 1 unidade.
Resposta correta (D)
4) [POSCOMP 2015 – CENTRO DE SELEÇÃO – UFG] 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:
O número de nós de uma árvore cheia é dado por: 2^h+1 – 1.
2h + 1 representa 2 vezes a altura da arvore – 1, não existe possibilidade desse valor ser > que o número de nós.
Resposta correta (E)
5) [POSCOMP 2015 – COPS – UEL] 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.
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.
Correta – não é possível que uma árvore binária tenha mais de duas subárvores
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.
Errada – isso só seria real se a arvore estivesse balanceada, onde o tempo de busca é log(n).
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.
Errado – a arvore precisaria estar balanceada
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.
Correta – o ultimo número possível é o 475, sendo assim, não existe possibilidade de haver mais de 476 comparações.
Resposta correta (B)
6) [POSCOMP 2013 – COPS – UEL] 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.
Resposta correta (E)
7) [POSCOMP 2013 – COPS – UEL] 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.
É preciso inserir os nós raiz primeiro, a seguir inserir as folhas.
Resposta correta (C)
8) [POSCOMP 2013 – COPS – UEL] 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.
Os algoritmos de força bruta (tentativa e erro) são mesmo impraticáveis usando recursão. O tempo de execução de uma solução recursiva é maior do que a iterativa.
Resposta correta (B)
9) [POSCOMP 2012 – COPS – UEL] 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 SBBsã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.
Resposta correta (A)
10) [POSCOMP 2010 – COPS – UEL] Assinale a alternativa em que todas as propriedades de uma árvore vermelho e preto são verdadeiras.
Resposta correta (C)
11) [POSCOMP 2010 – COPS – UEL] 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.valorResposta correta (D)
12) [POSCOMP 2010 – COPS – UEL] Em uma Árvore B de ordem, temos que:
(i) cada nó contém no mínimo m registros (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:
Resposta correta (A)
13) [POSCOMP 2009] 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:
Resposta correta (C)
14) [POSCOMP 2009] Percorrendo a árvore binária a seguir em pré-ordem, obtemos que seqüência decaracteres?
Resposta correta (E)
15) [POSCOMP 2009] Dado um conjunto C contendo n inteiros distintos, qual das seguintes estruturas dedados em memória principal permite construir um algoritmo para encontrar o valormáximo de C em tempo constante?
(A) É falsa. A busca pelo valor máximo seria feita em tempo O(n), pois você precisaria verificar todos os elementos do vetor.
(B) É verdadeira. O valor máximo estará no final do vetor, portanto basta retornar o valor da última posição, algo que pode ser realizado em tempo O(1), pois o acesso aos elementos de um vetor pode ser feito em tempo constante.
(C) É falsa. A complexidade seria O(log n), isto é, a complexidade é proporcional à altura da árvore.
(D) É falsa. O valor máximo estará no último nó da lista, portanto, o acesso será realizado em tempo O(n). É claro, estamos considerando uma lista simples (sem nó cauda).
(E) É falsa. A justificativa é a mesma de C.
Resposta correta (B)
16) [POSCOMP 2009] Quais das seguintes propriedades não se aplicam a árvores rubro-negras?
Resposta correta (E)
17) [POSCOMP 2009] Considere a árvore minimax abaixo, representando um jogo onde queremosmaximizar 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 servisitados em uma busca da melhor jogada se a estratégia de poda alfa-beta for utilizada.
Resposta correta (B)
18) [POSCOMP 2007] Seja T uma árvore AVL vazia. Supondo que os elementos 5, 10, 11, 7, 9, 3 e 6sejam inseridos nessa ordem em T, indique a sequência abaixo que corresponde a umpercurso de T em pós-ordem.
Faça uma simulação de árvore AVL aqui
Resposta correta (E)
19) [POSCOMP 2007] Levando em conta as podas alfa-beta na árvore Mini-Max abaixo, assinale aalternativa que apresenta a quantidade de folhas que deverão ser visitadas
Resposta correta (B)
Esse post foi modificado em 16 de junho de 2021 15:10
This website uses cookies.
