Questões de Concurso sobre Árvores

Uma Árvore Binária de Pesquisa (ABP) organiza chaves de forma que, para cada nó, todos os valores na subárvore esquerda são menores e todos na subárvore direita são maiores. A Árvore AVL é uma ABP autoequilibrada que mantém, em cada nodo, a invariante de que as alturas das subárvores esquerda e direita diferem em, no máximo, 1. Nesse contexto, assinale a alternativa correta.

As árvores são estruturas de dados hierárquicas amplamente utilizadas em sistemas de gerenciamento de bancos de dados, motores de busca e compiladores. No contexto de um sistema de informação em saúde, estruturas do tipo árvore são empregadas, por exemplo, na indexação de registros de pacientes e na organização hierárquica de categorias de procedimentos médicos, em que a eficiência das operações de busca e crítica. Com base nas propriedades e tipos de árvores em estruturas de dados, assinale a alternativa CORRETA.

Observe a imagem a seguir.

Fonte: NISHIMURA, R. Y. Banco de dados II. Londrina: Editora e Distribuidora Educacional S.A., 2019. p. 98.

A imagem apresentada ilustra uma estrutura hierárquica de dados organizada em árvore, na qual um nó raiz representa os Projetos Gerais da Empresa, que se ramificam em subconjuntos como Projetos de Engenharia e Projetos de TI, com múltiplos níveis de relacionamento entre os nós.

Considerando a modelagem de dados em bancos de dados não relacionais, especialmente bancos de dados de grafos, modelos agregados e bancos de documentos, avalie as afirmativas a seguir.

I. A estrutura apresentada pode ser modelada de forma natural em um banco de dados de grafos, no qual cada elemento (A, B, C, etc.) corresponde a um vértice, e as relações hierárquicas entre projetos são representadas por arestas direcionadas.

II. Em um banco de dados de documentos, a hierarquia exibida poderia ser representada por meio de documentos aninhados, mas consultas que envolvam navegação em múltiplos níveis da estrutura tendem a exigir maior processamento quando comparadas a bancos de grafos.

III. Caso essa estrutura seja armazenada em um banco de dados chave-valor, a navegação eficiente entre os diferentes níveis hierárquicos exigiria o uso de chaves compostas ou a duplicação de referências, uma vez que esse modelo explicita relacionamentos.

IV. A modelagem dessa estrutura em um banco de dados de famílias de colunas é especialmente adequada para operações de travessia hierárquica complexa, pois esse tipo de banco é otimizado para consultas recursivas e relacionamentos profundos entre registros.

Está CORRETO o que se afirma em

Considere árvores B não vazias, com grau mínimo t ≥ 2. Para árvores B+, adote a convenção usual de sistemas de indexação: todas as chaves de dados permanecem nas folhas, enquanto os nodos (nós) internos armazenam apenas chaves separadoras; todas as folhas estão na mesma profundidade. Nesse contexto, analise as assertivas a seguir:

I. Em uma árvore B de grau mínimo t, todo nodo não raiz armazena entre t−1 e 2t−1 chaves; a raiz armazena entre 1 e 2t−1 chaves.

II. A altura de uma árvore B aumenta somente quando a raiz é dividida e diminui somente quando, após uma fusão, uma raiz interna fica sem chaves e é substituída por seu único filho.

III. Na inserção em uma árvore B+, a divisão de uma folha cheia remove da folha a chave separadora promovida ao pai, exatamente como ocorre na divisão de um nodo em uma árvore B convencional.

IV. A altura h de uma árvore B de grau mínimo t, com n chaves, satisfaz h ≤ log_t((n+1)/2). Para t=500 e n=10⁹, conclui-se que h ≤ 3; ou seja, o caminho da raiz até uma folha contém no máximo 4 nodos. Assumindo um nodo por página de disco e a raiz residente em memória principal, uma busca exige, no máximo, 3 acessos a disco.

Quais estão corretas?

Assinale a alternativa correta a respeito da estrutura de dados do tipo árvore.

Observe as assertivas abaixo e, em seguida, assinale a alternativa correta.

I. Uma árvore rubro-negra com 𝑛 nós internos tem altura no máximo 2 𝑙𝑔 (𝑛 +1) .

PORQUE

II. As propriedades das árvores rubro-negras garantem que nenhum caminho da raiz até uma folha seja mais do que duas vezes mais longo que qualquer outro caminho, mantendo a árvore aproximadamente balanceada.

Em regra, em algoritmos de gradient boosting, quanto maior o número de estimadores usados, menor o erro de generalização do modelo, pois cada árvore adicionada corrige os erros residuais da anterior.

Árvores de decisão (AD) são classificadores muito utilizados em Ciência de Dados. Com relação as características da AD, analise as afirmativas a seguir.

I. É a representação de uma função que mapeia um vetor de valores de atributos para um único valor de saída.

II. Uma árvore de decisão chega à sua decisão realizando uma sequência de testes, começando por uma de suas raízes e seguindo o ramo apropriado até que uma folha seja alcançada.

III. Cada nó interno na árvore corresponde a um teste do valor de um dos atributos de entrada, os ramos a partir do nó são rotulados com os possíveis valores do atributo, e os nós folha especificam qual valor deve ser retornado pela função.

Está correto o que se afirma em

Em uma árvore binária de busca, considerando valores distintos, a propriedade que orienta a organização dos nós estabelece que:

Em estruturas de dados, algumas árvores possuem mecanismos que mantêm sua altura aproximadamente balanceada, garantindo eficiência nas operações. Assinale a alternativa que apresenta apenas exemplos de árvores balanceadas.

Um índice em memória para autocompletar nomes de documentos utiliza uma estrutura de árvore para buscas eficientes. O analista comparou árvore binária de busca (BST) com árvore balanceada.

É CORRETO afirmar que:

Analise as afirmativas abaixo sobre as propriedades de uma Árvore Binária de Busca (BST).

I. Para qualquer nó 𝑥, se 𝑦 é um nó na subárvore esquerda de 𝑥, então a chave de 𝑦 é maior ou igual à chave de 𝑥.

II. O percurso em ordem (in-order tree walk) de uma árvore binária de busca imprime as chaves em ordem crescente.

III. O tempo de execução das operações básicas como inserção e busca em uma BST é proporcional à altura da árvore.

IV. No pior caso, a altura de uma árvore binária de busca com 𝑛 nós é Θ(n).

Estão corretas apenas as afirmativas

Em relação às árvores de decisão, julgue os itens a seguir.

I Essa categoria de algoritmos da análise supervisionada realiza a classificação dos dados em um número limitado de classes, de modo a utilizar apenas os valores das variáveis de entrada como base.

II As árvores de decisão são mais apropriadas para dados categóricos e intervalares, portanto, o uso de variáveis contínuas em árvores de decisão requer a discretização, que consiste na transformação de variáveis numéricas contínuas em intervalos ou categorias.

III O algoritmo Random Forest utiliza o método bagging para a criação de múltiplas árvores de decisão independentes e combina as previsões para melhorar a precisão e reduzir o risco de overfitting.

Assinale a opção correta.

Considerando uma árvore B não vazia de ordem 𝑑, considere como verdadeira (V) ou falsa (F) cada uma das afirmativas a seguir:

I. A raiz é uma folha ou tem no mínimo 𝑑 − 1 filhos;

II. Cada nó diferente das folhas tem no máximo 2𝑑 + 2 filhos;

III. Todas as folhas estão no mesmo nível.

A sequência correta é

Considere o uso de uma estrutura de dados do tipo árvore. A afirmação VERDADEIRA sobre uma Árvore Binária de Busca é:

Sobre florestas aleatórias, avalie as seguintes afirmações:

l. Florestas aleatórias utilizam um conjunto de árvores de decisão para realizar tarefas de classificação ou regressão.

Il. Uma vantagem da floresta aleatória é a alta precisão em comparação com um único modelo de árvore de decisão.

III. Florestas aleatórias não correm risco de super ajuste do modelo.

IV. O método k-means é diretamente relacionado à floresta aleatória.

Assinale a alternativa que apresenta APENAS as afirmações corretas.

Acerca dos algoritmos de mineração de dados, analise as afirmativas a seguir, e assinale (V) para a verdadeira e (F) para a falsa.

( ) Uma árvore de decisão é um grafo cíclico direcionado em que cada nó é um nó de divisão.

( ) Em uma rede neural artificial multicamadas os neurônios estão conectados a todos os neurônios da camada anterior.

( ) As máquinas de vetores de suporte (SVM - Support Vector Machine) são aplicadas em problemas de classificação nos quais busca-se dividir os dados por meio de um hiperplano.

As afirmativas são, respectivamente,

Com relação às árvores binárias de busca, assinale a opção INCORRETA.

Uma árvore Trie, também conhecida como árvore prefixada ou árvore digital, é uma estrutura de dados eficiente para armazenar um conjunto de strings, especialmente quando se trata de busca por prefixos. A Trie é útil em diversas aplicações, como autocompletar, busca de palavras, e processamento de texto.

Sobre as árvores Trie, informe verdadeiro (V) ou falso (F) para as assertivas abaixo e, em seguida, marque a opção que apresenta a sequência correta.

( ) Uma Trie é uma árvore M-ária cujos nós são vetores de M componentes com campos correspondentes aos dígitos ou caracteres que formam as chaves.

( ) Cada nó no nível i representa o conjunto de M / 2 chaves que começam com a mesma sequência de i dígitos ou caracteres.

( ) Considerando as chaves como sequência de bits (isto é, M = 2), o algoritmo de pesquisa digital é semelhante ao de pesquisa em árvore, exceto que, em vez de se caminhar na árvore de acordo com o resultado de comparação entre chaves, caminha-se de acordo com os bits de chave.

( ) O formato das árvores Tries, diferentemente das árvores binárias comuns, não depende da ordem em que as chaves são inseridas e sim da estrutura das chaves através da distribuição de seus bits.

Sobre a estrutura de dados árvore, foram feitas as seguintes afirmações:

I. Toda árvore é um conjunto de vértices e arestas, que podem ou não ter ciclos.

II. Em uma árvore, para existir uma aresta (a, b), precisa então existir os vértices a e b.

III. São exemplos de árvores: árvore binária, árvore B, árvore B+e árvore rubro-negra.

Sobre as afirmações acima, pode-se afirmar que: