Questões de Concurso sobre Árvores

No contexto de uma Árvore B, estrutura comumente utilizada na indexação de tabelas relacionais, considere as seguintes propriedades numa Árvore B de grau g.

1. Todas as folhas estão no mesmo nível de profundidade na árvore.

2. Todos os nós podem conter, no máximo, 2g - 1 chaves.

3. Exceto pelo nó raiz, todos os demais nós devem conter, no mínimo, g -1 chaves.

4. Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n).

5. Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(log n).

Estão corretas as afirmativas

A Figura a seguir exibe uma árvore binária.

Suponha que uma função percorra essa árvore em ordem simétrica e exiba os valores de seus nós no console.

Qual será o sexto valor a ser exibido por essa função?

Observe a figura a seguir.

Para a árvore binária apresentada, qual a ordem correta de visitação dos nós em um percurso em pós-ordem(pós-fixo)?

A criação de índices espaciais otimiza o armazenamento e a busca por dados de interesse do usuário, em comparação com a busca sequencial. Algumas heurísticas foram propostas e implementadas com essa finalidade, com destaque naquelas que se baseiam em árvores.

Assinale a opção que melhor descreve uma R-Tree.

Um desenvolvedor Java está implementando um sistema que precisa manipular grandes conjuntos de dados e deseja otimizar o desempenho da aplicação. Qual estrutura de dados em Java é mais adequada para armazenar elementos sem duplicação, permitindo acesso eficiente e verificação de existência?

Considere as seguintes três afirmações com base no código:

I - A função list() percorre a árvore e imprime os elementos em ordem crescente.

II - A função search() realiza uma busca recursiva na árvore binária e retorna um ponteiro para o nó que contém o elemento procurado, se encontrado.

III - A função list() não é recursiva.

Assinale a alternativa correta:

Considere a construção da estrutura de uma árvore binária: cada nó é de um tipo registro chamado de noh com um campo com um inteiro (dado) e dois campos para os nós filhos (ant) e (prox), que são apontadores para noh (aqui convencionado como noh^). O elemento apontado por uma variável apontadora pt, por exemplo, é ‘pt^’. Considere o seguinte pseudocódigo do procedimento de construção da árvore:

O parâmetro “nodearv” é passado para “construa” por referência, e a função “novo” aloca espaço na memória para um novo nó. Suponha que a variável “raiz” é do tipo “noh^” e é inicializada com ‘NULO’. Então, para cada valor ‘x’ em {2,6,1,9,4,7,3,8,5}, nessa ordem, nós chamamos “construa(raiz, x);”, acarretando a construção da árvore com esses valores. As folhas dessa árvore (nós sem filhos) resultam, portanto, em:

Com relação às árvores de decisão, analise as afirmativas a seguir e assinale (V) para a verdadeira e (F) para a falsa.

( ) A estrutura hierárquica presente nas árvores de decisão as torna imunes a qualquer tipo de deficiência nos dados de treinamento, garantindo uma generalização perfeita do modelo, sendo incomuns problemas de overfitting.

( ) Em uma árvore de decisão, o coeficiente de Gini de um nó geralmente é menor que o do seu pai.

( ) A árvore de decisão é um modelo em que cada nó consiste em uma decisão sobre um atributo ou conjunto de atributos que determina como os dados estão particionados pelos seus nós pais.

As afirmativas são, respectivamente,

Uma árvore binária é classificada como balanceada (AVL) quando as alturas das subárvores da maioria dos nós dessa árvore diferem entre si em apenas uma unidade.

As árvores B são caracterizadas por minimizarem os custos de tempo em discos magnéticos e possuírem, no máximo, dois filhos em cada nó.

Considerando os algoritmos de construção de árvores de decisão ID3 e C4.5, é correto afirmar que:

Considere as afirmativas abaixo sobre estruturas de dados homogêneas e heterogêneas, incluindo vetores e matrizes, registros, listas, filas, pilhas e árvores, métodos de busca e ordenação, e recursividade. Sobre o assunto, julgue as seguintes afirmações como verdadeiras (V) ou falsas (F):

(__)Em uma árvore binária de busca, o valor de cada nó à esquerda de um nó raiz é menor ou igual ao valor do nó raiz, e o valor de cada nó à direita é maior ou igual.

(__)A busca binária pode ser aplicada eficientemente em listas não ordenadas.

(__)Em uma pilha, a operação de inserção (push) ocorre no início da estrutura e a operação de remoção (pop) ocorre no final.

Assinale a alternativa cuja respectiva ordem de julgamento esteja correta:

Em estruturas de dados, existem conjuntos __________________ nos quais o elemento removido do conjunto pela operação ‘Delete’, por exemplo, é especificado previamente. Em uma ___________, o elemento eliminado do conjunto é o mais recente inserido, a política implementada é “último a entrar, primeiro a sair”, ou LIFO (last-in, first-out). Já em uma ____________, o elemento eliminado é sempre o que estava no conjunto a mais tempo, a política implementada é “primeiro a entrar, primeiro a sair”, ou FIFO (first-in, first-out).

Assinale a alternativa que preenche, correta e respectivamente, as lacunas do trecho acima.

Árvores binárias de busca (BST) garantem a eficiência de inserções e buscas em tempo O (log n), desde que a árvore esteja balanceada, o que mantém a estrutura equilibrada e otimiza a altura da árvore.

Os algoritmos baseados em árvore de decisão definem modelos com uma técnica para estimar a probabilidade de um evento ocorrer sob determinada circunstância, usando-se uma estimativa a priori da probabilidade de sua ocorrência.

Micael, atuando como analista no desenvolvimento de um sistema de gerenciamento de biblioteca, enfrenta o desafio de selecionar uma estrutura de dados que otimize o armazenamento de informações sobre os livros. O sistema requer uma solução que combine a eficiência em realizar buscas rápidas por título, a capacidade de adicionar novos títulos frequentemente e a preservação da ordem alfabética para melhorar a experiência de navegação. Levando em conta os critérios de acesso, busca, inserção e ordenação nas estruturas de dados, Micael identifica que a melhor opção para cumprir esses requisitos é a(o):

A figura a seguir ilustra um jogo chamado de Torre de Hanoi, em vista lateral:

O objetivo é remover os discos de diferentes diâmetros do pino A para o pino C, utilizando o pino B como intermediário. Cada movimento deve ser feito com apenas um disco, e o resultado do movimento nunca deve dispor um disco maior sobre um disco menor. Para a implementação do jogo, as estruturas de dados mais naturais para armazenamento dos discos são de qual tipo?

No contexto de estrutura de dados, um grafo que consiste em um conjunto de vértices e um conjunto de arestas relacionadas entre esses vértices, onde não há nenhum ciclo direcionado, é um

Seja T uma árvore binária completa com n nós e altura h. O valor de n que indica uma árvore cheia é

Árvores binárias balanceadas podem ser utilizadas para armazenar elementos de maneira a reduzir a quantidade de testes durante uma busca. Considerando que uma árvore com apenas um elemento (a raiz) possui 1 nível, marque a alternativa que indica a quantidade de níveis necessários para armazenar um total de 50 elementos utilizando todos os nós em uma árvore binária balanceada.