Exercicio 4 Estrutura de dados

Prévia do material em texto

exercicio 
1 Seja as seguintes afirmações sobre árvores binárias: 
I - Os nós que não possuem filhos são chamados de nós folhas. 
II - O nó raiz é um nó na árvore que não possui antecessor (ou não tem pai). 
III - As árvores binárias são estruturas não lineares. 
Estão corretas as afirmativas: 
R- I, II e III. 
2 As afirmativas abaixo são feitas com base na estrutura de dados "Árvore Binária de Busca". Em relação ao algoritmo de busca 
em uma árvore binária de busca, analise as afirmativas abaixo: 
I -A complexidade da busca é definida pela altura da árvore binária de busca. No pior caso O(n). 
II - A busca é definida de forma recursiva, parte da raiz, comparando a chave buscada com a armazenada na raiz, caso seja igual 
temos o sucesso da busca, caso contrário, se a chave buscada for menor, devemos proceder recursivamente no ramo esquerdo, 
se a chave buscada for maior, proceder recursivamente no ramo direito. 
III - Sempre é necessário percorrer toda a árvore no algoritmo de busca. Em todos os casos, mesmo em árvores completas. 
IV - A condição de parada da busca é encontrar a chave buscada ou ter que descer por um ramo vazio. 
V - É possível escrever o algoritmo da busca de forma não recursiva. 
R – I, II, IV e V são corretas. 
3 As árvores AVL constituem uma importante estrutura de dados que disponibilizam operações de busca, inserção e remoção. 
Classifique como verdadeiro ou falso as afirmativas abaixo: 
I - As árvores de Fibonacci são as árvores de altura máxima h com número mínimo do nós n e altura proporcional a log n. 
II - As árvores completas são árvores AVL. 
III - É possível construir uma topologia de uma árvore AVL que não seja nem completa nem de Fibonacci com altura proporcional 
a log n. 
IV - Uma vez que a altura das árvores AVL é proporcional a log n, podemos garantir que a busca ocorre numa complexidade de 
O(log n). 
V - Na remoção, pode ser necessário realizar todas as rotações, no pior caso, do pai de uma folha que está sendo removida até a 
raiz. Por esta razão, a complexidade da remoção é maior que O(log n). 
R – I-V, II-V, III-V, IV-V, V-F. 
 
 
 
 
 
 
4 Considere a seguinte estrutura de árvore. Marque a alternativa correta: 
 
R – Pode-se afirmar que o número de passos para buscar um elemento na árvore acima é, no máximo, O(log n).5 A raiz é 
o ponto de partida para acessar todos os elementos de uma árvore. Marque a opção correta acerca dos principais 
conceitos de árvore binária de busca: 
5 Seja a seguinte árvore AVL abaixo. Com a inserção da chave 90, marque a opção que indica exatamente o que acontecerá com 
a árvore resultante após essa inserção: 
 
R – A árvore resultante irá desbalancear à esquerda do nó de chave 60. 
6 Um percurso é uma forma organizada de acesso à informação armazenada nos nós de uma estrutura de dados. Sobre Árvores 
Binárias de Busca, marque a opção correta: 
R – No pior cenário, uma busca por um elemento em uma árvore binária de busca pode exceder O(log n) , chegando a 
n passos nessa busca. 
7 Árvores de busca são organizadas de forma hierárquica, onde cada nó é um objeto que contém informação e cada nó filho é 
uma subdivisão da informação contida no nó pai. Sobre árvores binárias de busca, marque a opção correta. 
R – As rotações simples e duplas possuem complexidade de execução O(1). 
8 Em uma Árvore B, temos que: Cada nó contém no mínimo m registros (m+1 descendentes) e no máximo 2m registros (e 2m+1 
descendentes), exceto o nó que é raiz que pode conter entre 1 e 2m registros e todos os nós folhas aparecem no mesmo 
nível. Sobre Árvores B, é correto afirmar: 
R – O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser inserido em um nó com 2m 
registros.