Estruturas de Dados: Árvores
48 Questions
4 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Na árvore binária de pesquisa fornecida, qual nó seria o pai de '30'?

  • 35
  • 5
  • 28 (correct)
  • 20

    • Na hierarquia de classes apresentada, qual classe herda diretamente de AbstractBinaryTree?

  • LinkedBinaryTree (correct)
  • Tree
  • BinaryTree
  • SearchBinaryTree

    • De acordo com a estrutura da árvore binária de pesquisa, qual nó seria o filho direito de '80'?

  • 105
  • 85
  • 70
  • 84 (correct)

    • Qual das seguintes classes na hierarquia apresentada é uma interface?

    <p>Tree (D)</p> Signup and view all the answers

    Na árvore binária de pesquisa, qual é o ancestral mais próximo comum de '25' e '30'?

    <p>28 (C)</p> Signup and view all the answers

    Qual é o principal objetivo da abstração Position na interface da ADT Árvore?

    <p>Ocultar a implementação específica do nodo, expondo apenas o método <code>getElement()</code> para acesso ao elemento armazenado. (B)</p> Signup and view all the answers

    Qual método é definido na interface Position?

    <p><code>getElement()</code> (A)</p> Signup and view all the answers

    Como a interface Position contribui para o encapsulamento na ADT Árvore?

    <p>Restringindo o acesso aos detalhes internos do nodo, permitindo apenas a consulta do elemento. (C)</p> Signup and view all the answers

    Por que foi feita a opção de abstrair a entidade nodo através da interface Position na ADT Árvore?

    <p>Para conseguir referenciar os nodos ao nível da interface da árvore, antes de estes serem definidos concretamente. (A)</p> Signup and view all the answers

    Qual é a relação entre a interface Position e a classe Node (que implementa a estrutura concreta da árvore)?

    <p>A classe <code>Node</code> implementa a interface <code>Position</code>. (A)</p> Signup and view all the answers

    Qual das seguintes estruturas de dados é melhor para representar informações hierárquicas?

    <p>Árvores (D)</p> Signup and view all the answers

    Em uma estrutura de árvore, como são chamados os nós que não possuem descendentes?

    <p>Folhas (A)</p> Signup and view all the answers

    Qual é a característica principal de um nó em uma árvore, em relação à sua relação com outros nós?

    <p>Um nó só pode ter um pai. (A)</p> Signup and view all the answers

    Qual é a finalidade do método node(Position p) na classe LinkedBinaryTree?

    <p>Validar e converter uma <code>Position</code> para um <code>Node</code>. (A)</p> Signup and view all the answers

    Na implementação de árvores, a combinação de classes abstratas e concretas visa principalmente qual objetivo?

    <p>Reutilização de código (D)</p> Signup and view all the answers

    Se p é uma Position válida em uma LinkedBinaryTree, e node(p).getLeft() retorna null, o que isso indica?

    <p>Que <code>p</code> não tem um filho esquerdo. (D)</p> Signup and view all the answers

    Qual tipo de nó se encontra no topo da hierarquia em uma árvore?

    <p>Raiz (C)</p> Signup and view all the answers

    Qual operação é realizada pelo método addRoot(E e)?

    <p>Adiciona um novo nó como raiz, se a árvore estiver vazia. (C)</p> Signup and view all the answers

    Quais são exemplos de aplicações de estruturas em árvore mencionadas no texto?

    <p>Classificação de seres vivos e árvores genológicas (C)</p> Signup and view all the answers

    O que acontece com o tamanho da árvore ao executar addLeft(Position p, E e)?

    <p>O tamanho da árvore é incrementado em 1. (B)</p> Signup and view all the answers

    Em relação à hierarquia da implementação de árvores, o que representa a classe AbstractTree?

    <p>Uma classe abstrata para árvores genéricas. (A)</p> Signup and view all the answers

    O que o método parent(Position p) da LinkedBinaryTree retorna?

    <p>O nó pai da posição <code>p</code>. (C)</p> Signup and view all the answers

    No contexto da implementação de árvores, o que é a JCF?

    <p>Uma biblioteca de classes abstratas e concretas para estruturas de dados. (D)</p> Signup and view all the answers

    Qual condição impede a adição de um novo nó como raiz usando addRoot(E e)?

    <p>Se a árvore já possuir um nó raiz. (A)</p> Signup and view all the answers

    Em qual cenário o método addLeft(Position p, E e) retornaria null?

    <p>Quando o nó em <code>p</code> já possui um filho esquerdo. (C)</p> Signup and view all the answers

    Qual é a principal aplicação de uma árvore de decisão no contexto de Inteligência Artificial?

    <p>Representação de algoritmos de aprendizagem automática, onde a árvore cresce automaticamente com base em dados. (C)</p> Signup and view all the answers

    Qual a complexidade de pesquisa em uma árvore binária de pesquisa balanceada?

    <p>Logarítmica, O(log n), visto que o número de iterações é proporcional ao número de níveis. (D)</p> Signup and view all the answers

    Numa árvore binária de pesquisa, qual a regra de organização dos nodos?

    <p>O elemento de um nodo é sempre maior do que qualquer elemento na subárvore esquerda e menor na subárvore direita. (B)</p> Signup and view all the answers

    Como as folhas (nodos sem filhos) se comportam numa árvore binária de pesquisa?

    <p>As folhas armazenam elementos e não realizam decisões, sendo nodos finais na busca. (C)</p> Signup and view all the answers

    Se uma árvore binária de pesquisa tem 20 níveis, qual o tamanho máximo da coleção que ela pode gerir?

    <p>Mais de 1 milhão de elementos, até um limite de 1048575 elementos. (A)</p> Signup and view all the answers

    Qual a principal diferença entre uma árvore binária de pesquisa e uma árvore de decisão?

    <p>A árvore binária de pesquisa usa hierarquia para organização e pesquisa, e a árvore de decisão é usada para tomada de decisões baseadas em atributos. (D)</p> Signup and view all the answers

    Qual a fórmula para calcular o número máximo de nodos numa árvore binária de pesquisa, dado o número de níveis 'k'?

    <p>$n = 2^k - 1$ (A)</p> Signup and view all the answers

    Qual a semelhança entre uma árvore binária de pesquisa e uma árvore de decisão?

    <p>Em ambas, a questão em um nodo interno é se o elemento procurado é maior ou menor que o elemento guardado. (C)</p> Signup and view all the answers

    Qual método da interface BinaryTree retorna a posição do nó esquerdo de um nó dado?

    <p><code>left(Position p)</code> (D)</p> Signup and view all the answers

    Na classe AbstractBinaryTree, o que acontece se o nó p passado para o método sibling(Position p) for a raiz da árvore?

    <p>Retorna <code>null</code>. (C)</p> Signup and view all the answers

    Qual o objetivo do método numChildren(Position p) na classe AbstractBinaryTree?

    <p>Retornar a quantidade de filhos (nós filhos) que o nó <code>p</code> possui. (C)</p> Signup and view all the answers

    Qual tipo de dado é retornado pelo método children(Position p) da classe AbstractBinaryTree?

    <p>Uma coleção (Iterable) de objetos <code>Position</code> representando os filhos. (A)</p> Signup and view all the answers

    Na classe aninhada Node dentro da classe LinkedBinaryTree, qual atributo armazena o nó filho esquerdo?

    <p><code>left</code> (A)</p> Signup and view all the answers

    O que o método getParent() na classe Node dentro de LinkedBinaryTree retorna?

    <p>O nó pai do nó atual. (D)</p> Signup and view all the answers

    Qual o propósito do método setElement(E e) na classe Node?

    <p>Atualizar o elemento armazenado no nó. (C)</p> Signup and view all the answers

    Se um nó na classe LinkedBinaryTree não tem filho esquerdo, o que o método getLeft() retornará?

    <p><code>null</code>. (D)</p> Signup and view all the answers

    Na estrutura de uma árvore binária, qual é a relação entre um nó e seu 'irmão' (sibling)?

    <p>Eles compartilham um mesmo pai. (C)</p> Signup and view all the answers

    Qual interface define os métodos left(Position p), right(Position p), e sibling(Position p)?

    <p><code>BinaryTree</code> (A)</p> Signup and view all the answers

    Como a classe AbstractBinaryTree implementa o método sibling(Position p)?

    <p>Verificando se <code>p</code> é filho esquerdo e retornando o filho direito (se existir), ou vice-versa. (B)</p> Signup and view all the answers

    Na classe LinkedBinaryTree, o que representa o atributo element na classe Node?

    <p>O valor armazenado no nó. (A)</p> Signup and view all the answers

    Qual é a capacidade inicial da lista criada dentro do método children(Position p) da classe AbstractBinaryTree?

    <p>2 (C)</p> Signup and view all the answers

    O que acontece se o nó passado para o método sibling(Position p) não tiver um irmão?

    <p>Retorna <code>null</code>. (B)</p> Signup and view all the answers

    Qual método da classe Node permite atualizar a referência para o nó filho direito?

    <p><code>setRight()</code> (B)</p> Signup and view all the answers

    Study Notes

    Árvores

    • Árvores n-árias, árvores binárias, árvores de decisão, árvores binárias de pesquisa, AVLs, Heaps e travessias são estruturas de dados.

    Estruturas em Árvore

    • As estruturas em forma de árvore (invertida) representam hierarquicamente informação, como classificação de seres vivos, árvores geneaógicas, árvores de decisão e diagramas organizacionais.
    • Um conjunto de nodos interligados, formando uma hierarquia (pais e filhos), com um nodo raiz (topo). Os nodos descendentes são intermédios e terminais, sendo estes últimos as folhas (nodos externos).

    Implementação de Árvores

    • A implementação das estruturas em árvore usa classes abstratas e concretas para maior reutilização de código (semelhante ao JCF).
    • Um diagrama ilustra a hierarquia dos tipos de árvore a criar.

    Abstraindo a entidade nodo - Position

    • A interface da ADT Árvore (Tree) abstrai a entidade nodo chamada Position, que tem apenas um método consultor getElement().
    • Esta abstração isola as funcionalidades internas do nodo, permitindo encapsulamento e abstração.
    • A interface Position é usada para referenciar nodos na árvore antes que eles sejam definidos.

    A Interface Tree<E>

    • Interface para árvores onde cada nodo pode ter um número arbitrário de filhos/descendentes.
    • Métodos para obter a raiz, ancestrais, filhos, número de filhos, se é nodo interno/externo/raiz e tamanho da árvore.
    • Metodos para percorrer todas as posições na árvore.

    Iteração duma Árvore

    • Tornar um iterador a navegar numa árvore pode ser complexo, mas pode-se copiar o conteúdo para uma coleção linear para simplificar o processo.
    • Iteradores de captura instantânea guardam uma cópia da árvore, permitindo iterar sem afetar a árvore original.
    • O iterador percorre a coleção linear copiada e é eficiente.

    Iterador a usar numa estrutura em árvore

    • Duas formas de iterar através da árvore: Snapshot Iterator (coleção estática copiada da árvore a cada iteração) e Coleção Iterável (coleção mantém as referências aos elementos da árvore, sendo mais flexível, mas potencialmente dependente da árvore para funcionar eficientemente).

    A classe abstrata Abstract Tree<E>

    • Fornece uma implementação de métodos abstratos da interface Tree.
    • Define um iterador para percorrer a árvore.

    Árvore Binária

    • Estrutura hierárquica com no máximo dois descendentes por nodo (esquerdo e direito).

    Ligação dos nodos numa árvore binária

    • Diagramas mostram a ligação dos nodos na estrutura da árvore binária.

    Representação mais rigorosa das ligações numa árvore binária

    • Diagramas mostram uma representação mais detalhada da ligação dos nodos na árvore binária.

    A Interface BinaryTree<E>

    • Interface para árvores binárias, onde cada nodo tem no máximo dois filhos.
    • Métodos para obter os nodos esquerdo, direito e irmão de um determinado nodo.

    A classe abstrata AbstractBinaryTree<E>

    • Fornece métodos abstratos e suporte para a interface BinaryTree.

    A classe LinkedBinaryTree<E>

    • Implementação concreta de árvores binárias usando uma estrutura de nó ligada.
    • Detalhes de classes internas Node<E> e métodos para criar/aceder/alterar nós na árvore binária.
    • Métodos para obter o tamanho, a raiz, o pai, o filho esquerdo, o filho direito e manipular a árvore.

    Árvore binária de pesquisa (ABP)

    • Estrutura de dados para armazenar e pesquisar dados de forma eficiente.
    • Os elementos são armazenados de acordo com uma ordem/propriedade, permitindo buscas com tempo logarítmico (O(log n)).
    • Cada nodo tem um valor maior que os nodos na subárvore esquerda e menor que os nodos na subárvore direita.

    Árvore binária de pesquisa (ABP) - exemplo

    • Exemplo de árvore binária de pesquisa com valores inseridos.

    A ABP SearchBinaryTree<E>

    • Hierarquia de interfaces e classes para implementar Árvore Binária de Pesquisa (ABP).

    Árvores de Decisão

    • Usadas como instrumentos de apoio a decisões complexas.
    • Um nodo interno representa uma condição (sim/não).
    • O caminho na árvore representa um conjunto de decisões.
    • Uma folha representa uma decisão a tomar.

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    Arvores - Algoritmos e Estrutura de Dados PDF

    Description

    Este questionário explora o conceito de árvores e suas variações, como árvores binárias, árvores de decisão e heaps. Aprenda sobre a hierarquia das estruturas em árvore e como implementar essas estruturas utilizando classes abstratas. Teste seu conhecimento sobre a abstração de nodos e suas funções dentro das árvores.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser