QUESTIONÁRIO 01 – ED II

QUESTIONÁRIO 01 – ÁRVORES, CONCEITOS GERAIS

1)         A estrutura de uma árvore é especializada em representar hierarquia. Defina e caracterize de forma completa o conceito da Estrutura Árvore.

Resposta:

Constituem uma das estruturas mais importantes da área da computação, inclusive em aplicações. Dentro da estrutura de árvores existe um relacionamento lógico entre os componentes da estrutura, isto é; existe uma hierarquia ou subordinação onde um subconjunto dos componentes é subordinado a outro. A estrutura de árvore é utilizada em casos onde os dados ou objetos a serem representados possuem relações hierárquicas entre si.

2)         O conceito da estrutura árvore é muito importante para as disciplinas de Sistema Operacional e Banco de Dados. Dê exemplos da aplicação prática da estrutura de dados árvore, explicando cada exemplo (pelo menos 3).

Resposta:

Hierarquia de classes (classes/subclasses) – hierarquia ou subordinação onde um subconjunto dos componentes é subordinado a outro.

Abstração de Composição – um objeto é composto por outros objetos

Organogramas de empresas – hierarquia entre os empregados

Ordenação de Valores – Árvore ordenada. Ex. esquerda / raiz / direita

Árvores de Derivação – Análise Sintática

3)         Para compreender o conceito de árvore é necessário entender alguns conceitos básicos. Explique o conceito de raiz, nó filho, nó pai, nó terminal, nó ascendente, nó descendente, grau, altura, nível, profundidade, caminho e floresta.

Resposta:
Uma árvore é um conjunto finito A de zero ou mais nós, tais que:

Caso o número de nós seja maior que zero, existe um nó denominado raiz da árvore, os demais nós formam m >= 0 conjuntos disjuntos S1, S2, ..., Sm, onde cada um destes conjuntos é uma árvore (Si são denominadas sub-árvores)

Número de nós zero: árvore vazia

Cada nó da árvore é a raiz de uma sub-árvore.

Grau de um Nó é o número de sub-árvores de um nó. Nó de grau zero é denominado nó folha ou nó terminal.

Nível de um Nó raiz possui nível zero. Demais nós: é o comprimento do caminho que vai da raiz até o nó.

Altura de uma Árvore é o maior nível de uma árvore (mais alto).

Floresta conjunto de zero ou mais árvores disjuntas. Se o nó raiz de uma árvore for eliminado, as sub-árvores, que restarem serão chamadas de floresta.

Nó Pai – é o pai das raízes de suas sub-árvores. Nó Filho – possui um nó pai associado. Nós Irmãos – são os vários filhos de um nó pai.

4)         Existem diversas maneiras de representar a estrutura de uma árvore. Demonstre e conceitue a representação Hierárquica, Diagrama de Inclusão, Expressão parametrizada e Expressão não parametrizada.

Resposta:
Representação hierárquica:

        

Representação por conjuntos (diagrama de inclusão)

Representação por expressão parentetizada (parênteses aninhados)

Cada conjunto de parênteses correspondentes contém um nodo e seus filhos. Se um nodo não tem filhos, ele é seguido por um par de parênteses sem conteúdo.

( A ( B ( D ( ) E ( ) ) ) ( C ( F ( ) ) ) )

Representação por expressão não parentetizada

Cada nó é seguido por um número que indica a quantidade de filhos desse nodo, e em seguida por esses filhos, representados do mesmo modo.

A 2 B 2 D 0 E 0 C 1 F 0