Estrutura de Dados (uni4)

Prévia do material em texto

Exercícios Estrutura de Dados (Unidade 4) 
Deixe seu like!! 
1. Alguns problemas requerem estruturas que possibilitem operações como 
inserção e remoção de maneira dinâmica, tais como as árvores. Em relação 
às árvores e suas vantagens em relação às demais estruturas, 
marque a alternativa correta. 
 
Árvores são consideradas eficientes para guardar informações, pois apresentam uma forma de 
organização não linear. 
 
2. Considere que você precisa utilizar uma árvore binária e o TAD deve ter 
um campo para armazenar um número inteiro. Os nós podem ser 
representados na linguagem Python como uma classe com os seguintes 
atributos básicos: 
 
Número do nó, ponteiro para subárvore da direita e ponteiro para subárvore da esquerda. 
 
3. Durante a implementação de um TAD hierárquico, será necessário conhecer 
alguns termos para projetar os métodos. Acerca das terminologias da 
estrutura de dados do tipo árvore, considere a imagem a seguir e marque a 
alternativa correta: 
 
O grau do nó E é 2. 
 
4. Dada a seguinte árvore e considerando as propriedades de armazenamento 
de uma árvore binária, após a inserção do nó 9 e do nó 5, nessa ordem, pode-
se afirmar que esses nós serão filhos dos nós: 
 
9 será filho da esquerda do nó 10 e 5 será filho da direita do nó 4. 
 
5. Caso você tivesse que indicar uma estrutura de dados apropriada para 
armazenar uma sequência de comandos HTML e verificar sua sintaxe antes 
de apresentar as informações no browser, qual estrutura você indicaria? 
 
Árvore 
 
6. 
As árvores são estruturas de dados de grande contribuição, principalmente no 
que tange as expressões aritméticas, em que o percurso utilizado pode 
influenciar diretamente. 
O caminhamento em árvore é realizado de três formas, as quais variam 
conforme a posição de leitura do nó raiz, que podem ser: 
 
em-ordem, pós-ordem, pré-ordem. 
 
7. Árvores binárias possibilitam maior organização dos elementos adicionados, 
o que facilita separar os elementos a cada nível de crescimento da árvore. 
Dada a seguinte lista de caracteres [P, R, O, G, R, A, M, A, D, O, R, U, M], como 
ficaria seu resultado final em uma leitura pós-ordem, caso seus valores fossem 
adicionados sequencialmente, do primeiro ao último elemento, em uma árvore 
binária? Para montar uma árvore binária, os elementos menores ou iguais ao 
nó mais abaixo entrará à esquerda; caso contrário, ficará à direita. 
 
A D A M O M G O R R U R P. 
 
8. Uma árvore binária que tenha como finalidade resolver problemas aritméticos, 
necessita que sua leitura seja feita de tal modo a combinar dois operandos 
para o operador da expressão. Exemplo: A + B. 
Portanto, como uma árvore deveria posicionar seus elementos e qual seria a 
melhor forma de leitura para que as operações ocorram? 
 
É preferível que os valores da operação aritmética estejam localizados à esquerda e à direita da 
raiz, desde que o operador seja raiz, e a leitura da árvore seja feita em-ordem. 
 
9. O caminhamento de uma árvore binária influencia diretamente no resultado 
final de leitura de uma determinada sequência de símbolos, e pode se 
encontrar em 3 tipos, como percursos em pré-ordem, in-ordem e pós-ordem, 
variando, assim, a posição do valor raiz. 
Qual função a seguir descreve o percurso realizado em pós-ordem? 
 
def funcao(no): 
 if atual != None: 
 funcao(no.esquerdo) 
 funcao(no.direito) 
 print("Valor: ｛｝.".format(no.valor)) 
 
10. O modo como é feito o percurso determina como será o nível de prioridade de 
leitura dos elementos, podendo o nó raiz estar com prioridade (leitura em pré-
ordem), ou os elementos da subárvore à esquerda (leitura in-ordem), ou os 
elementos da subárvore à esquerda seguido da leitura à direita (pós-ordem). 
Considerando a imagem a seguir, mostre a sequência de expressões 
resultantes, conforme os percursos de pré-ordem, em-ordem e pós-ordem, 
respectivamente. 
 
 
* 3 * 5 13 
3 * 5 * 13 
3 5 13 * * 
 
11. A estrutura de dados de árvore apresenta grande versatilidade. Pode ser 
aplicada na solução de um leque de problemas, como em indexação de bancos 
de dados, em buscas, em estruturas de diretórios em sistemas de arquivos, 
entre outros. 
Considerando uma árvore binária de busca, qual destas é uma de suas 
propriedades? 
 
A subárvore esquerda de um nó contém os nós com chaves menores ou iguais que a do nó. 
 
12. Uma árvore binária de busca é conhecida pela sua eficiência quando é 
necessária a pesquisa de algum valor, seguindo as regras de buscas, 
ramificando para a esquerda e para a direita. 
Sabendo disso, de acordo com a árvore na imagem, determine qual caminho a 
chave de busca percorreu para pesquisa do valor 87 e se este existe ou não. 
 
Visitou chave 70. 
Visitou chave 90. 
Visitou chave 83. 
Visitou chave 85. 
Visitou chave 89. 
Resultado: falha. 
 
13. Sempre que vimos uma árvore, presumimos a ordem em que seus elementos 
foram adicionados. Dessa forma, conforme a imagem utilizada no exercício 
anterior, defina uma possível ordem do vetor que culminou na árvore 
apresentada, lembrando que o primeiro valor corresponde à raiz da árvore. 
 
[70,90,4,114,2,23,83,116,72,15,85,89,63]. 
 
14. Uma árvore binária de busca, como o próprio nome sugere, é uma estrutura de 
dados que armazena dados de maneira que permita a realização de busca 
binária. Essa busca segue o paradigma de divisão e conquista e acaba tendo 
uma eficiência melhor do que uma busca linear. 
Existem duas abordagens para realizar a implementação dessa busca: a 
implementação recursiva e iterativa. Qual a principal diferença entre essas 
implementações? 
 
Na abordagem recursiva, um nó definido como base nele próprio realiza a repetição dos seus 
passos invocando a si próprio, executando todos os seus passos novamente até encontrar o valor 
buscado. Diferentemente da busca recursiva, a busca iterativa considera as ramificações de 
maneira explícita de cada nó para percorrer seus nós, pois não há uma chamada interna para a 
mesma função. 
 
15. Em termos de alocação de memória, podemos implementar uma árvore de 
busca binária utilizando alocação dinâmica ou alocação estática. 
Considerando a alocação estática, como ocorre a representação de uma 
árvore de pesquisa binária em um vetor? 
 
1- O nó raiz deve ficar na posição inicial do vetor. 
 
2- Para cada nó em determinada posição i de um vetor, seu filho esquerdo ficará na 
posição 2*i + 1, e seu filho direito ficará na posição 2*i + 2. 
 
16. Uma das principais vantagens das árvores binárias em relação às demais 
estruturas de dados é a sua eficiência no processo de realizar buscas. A árvore 
AVL é conhecida por ter um resultado muito eficiente durante a operação de 
busca, pois realiza uma distribuição homogênea dos dados. 
Qual a ideia central ao fazer o balanceamento em uma árvore? 
 
A ideia central do balanceamento é que, para cada novo elemento adicionado ou removido da 
árvore, seja realizado uma reorganização para que a distribuição dos elementos conforme sua 
subárvore, continue homogênea. 
 
17. As árvores AVL correspondem à família das árvores binárias, em que a 
distribuição dos elementos é feita de acordo com determinadas condições, as 
quais são necessárias para garantir o balanceamento da árvore. 
Em relação à altura de uma AVL, qual é a afirmação correta? 
 
A altura de uma árvore nula é igual a -1. 
 
18. Uma árvore AVL é uma árvore binária muito utilizada para armazenamento de 
dados em memória. Cada nó de uma árvore AVL necessita da informação de 
altura, pois é fundamental para o processo de balanceamento. Para um nó 
folha, que tem uma altura igual a 1, sendo que essa árvore AVL tem 7 nós. 
Qual é a altura máxima que essa árvore pode ter? 
 
3. 
 
19. Uma árvore AVL tem as funções básicas como inserção, remoção e busca, 
assim como uma árvore simples. Considere a seguinte árvore AVL. 
Qual das alternativas a seguir é a árvore AVL atualizada após a inserção de 
70? 
 
Confira a alternativa C: 
 
 
 
20. No processode realizar o balanceamento de uma árvore AVL, após a exclusão 
ou inclusão são realizadas operações para realizar o balanceamento. 
Quais das seguintes operações são usadas pelas árvores AVL? 
 
Rotação à esquerda e rotação à direita.