Questões de Concurso Comentadas sobre árvores em algoritmos e estrutura de dados

Em uma árvore binária de busca do tipo rubro-negra,

Considere as seguintes afirmativas sobre árvores binárias, árvores binárias ordenadas e árvores binárias ordenadas balanceadas (AVL), assinale V para a afirmativa verdadeira e F para a falsa.

( ) Uma árvore binária é uma estrutura de dados que consiste em nós, onde cada nó tem no máximo dois filhos.
( ) Uma árvore binária ordenada é uma árvore binária em que os valores dos nós são ordenados de forma crescente ou decrescente.
( ) Uma árvore binária ordenada balanceada (AVL) é uma árvore binária ordenada em que a altura de qualquer subárvore não difere da altura de sua subárvore oposta em mais de um.

As afirmativas são, respectivamente,

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 são uma das estruturas de dados mais fundamentais, sendo usadas em diversas aplicações, desde a implementação de expressões matemáticas até a construção de tabelas de símbolos. Além disso, compreender a complexidade das operações nessas estruturas é essencial para escolher a melhor árvore para um determinado problema. Considere as seguintes afirmações sobre árvores binárias, AVL, B, B+ e a complexidade das operações associadas a essas estruturas:

I. A complexidade da busca, inserção e remoção em uma árvore binária de busca desbalanceada no pior caso é O(n), mas, em uma árvore AVL, essas operações sempre têm complexidade O(log n) no pior caso;
II. Em uma árvore AVL, a rotação simples e a rotação dupla são operações fundamentais para manter a árvore balanceada após inserções e remoções, mas essas rotações podem fazer com que o tempo de execução de uma inserção ou remoção se degrade para O(n) em casos específicos;
III. Árvores B são ideais para sistemas de banco de dados porque permitem que várias operações de busca, inserção e remoção sejam realizadas em tempo O(log n), com a vantagem adicional de minimizar o número de acessos a disco devido à estrutura de nós de múltiplas chaves;
IV. Em uma árvore B+, ao contrário de uma árvore B, todas as chaves estão armazenadas apenas nos nós folha, o que significa que as buscas por chaves sempre resultam em acessos aos nós folha. Embora isso possa tornar a busca ligeiramente menos eficiente em comparação com uma árvore B, na qual a busca pode ser resolvida em um nó interno, a árvore B+ oferece outras vantagens, como uma estrutura mais simples e suporte eficiente para operações de intervalo e varreduras de dados;
V. Apesar de as árvores B e B+ serem amplamente usadas em bancos de dados, uma desvantagem das árvores B+ em relação às árvores B é que a estrutura de encadeamento entre os nós folha pode aumentar significativamente o tempo de execução das operações de inserção e remoção, devido à necessidade de reorganização frequente dos nós folha.

Assinale a opção CORRETA: 

    Em aprendizado de máquina, especialmente em algoritmos de árvores de decisão, é fundamental avaliar como os dados são organizados e classificados em diferentes níveis da árvore. Três conceitos-chave que auxiliam na construção e otimização dessas árvores são o gini impurity, a entropy e o information gain. A respeito desses conceitos, julgue os itens a seguir.

I Gini impurity mede a redução da entropy após a divisão de um conjunto de dados com base em um atributo.

II Entropy mede a quantidade de incerteza ou impureza no conjunto de dados.

III Information gain mede a probabilidade de uma nova instância ser classificada incorretamente, com base na distribuição de classes no conjunto de dados.

Assinale a opção correta.

Estruturas de Dados são formas de organizar dados. Neste sentido, a forma como dados são inseridos e removidos varia e caracteriza cada tipo diferente de estrutura de dados. Observe a seguinte coleção de dados em que o início é à esquerda.


4 8 1 3 8 1 3 1 3 5 1 3
Elaborado pelo(a) autor(a).
Considerando a representação de como a estrutura se comporta durante as operações sucessivas de adição e remoção de elementos, infere-se que a estrutura de dados é uma: 

Como é chamada a estrutura de dados baseada em listas encadeadas que possui um nó superior, também chamado de raiz, que aponta para outros nós, chamados de nós filhos, que podem ser pais de outros nós?

Em uma Árvore Binária de Busca (BST) balanceada, qual das seguintes operações geralmente exibe uma complexidade de tempo média de O (log n), considerando a estrutura balanceada da árvore?

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, 3 chaves.
4. Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n2 ).
5. Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n).

Estão corretas apenas as afirmativas

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

Considere uma árvore que contém todo e qualquer nó em um grafo, mais formalmente, uma spanning tree de um grafo G = (N, E) e um grafo G' = (N, E') tal que E' é um subconjunto de E, G' é conectado, G' não contém nenhum ciclo e G' contém todos os nós originais em G.

Se cada enlace tiver um custo associado e o custo de uma árvore for a soma dos custos dos enlaces, é correto afirmar que uma árvore cujo custo seja o mínimo entre todas as spanning trees é denominada: 

Um sistema de banco de dados normalmente possui estruturas de dados auxiliares, chamadas de índices ou estruturas de indexação, que são utilizadas para agilizar a recuperação de registros em resposta a certas condições de pesquisa. Existem diversos métodos de indexação, tanto para dados convencionais, baseados em tipos numéricos e textuais, quanto para dados espaciais representados por pontos, linhas e polígonos.
Nesse contexto, analise as afirmativas a seguir e assinale (V) para a verdadeira e (F) para a falsa.
( ) Tanto as Árvores-B+ quanto as Árvores-R são árvores balanceadas. ( ) Em uma Árvore-B+, uma busca por um valor de chave iniciada pelo nó raiz percorre apenas um único caminho até um nó folha (ou terminal). ( ) Em uma Árvore-R, uma busca iniciada pelo nó raiz pode exigir a verificação de mais de uma sub-árvore desse nó raiz para selecionar os itens que satisfazem o critério de busca. ( ) Uma quad-tree sempre é uma árvore balanceada. ( ) Uma das desvantagens de um Árvore-k-d (k-d-tree) é que ela é uma estrutura sensível à ordem nos quais os pontos são inseridos.
As afirmativas são, respectivamente,

Os seguintes números serão inseridos, nessa ordem, em uma árvore AVL: 3, 13, 17, 23, 7, 9, 21, 25, 2.

O quinto elemento da árvore a ser visitado, quando é realizada uma busca em pré-ordem, é o número:

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):

O aprendizado de máquina (do inglês, machine learning) é um conjunto de técnicas da ciência de dados que permite que os computadores usem os dados existentes para prever comportamentos, resultados e tendências. Uma das formas de classificar o aprendizado é em razão da natureza do sinal de entrada ou feedback do processo. As árvores de decisão, agrupamento e regras de associação são, respectivamente, técnicas de aprendizado de máquina:

Considere as afirmações abaixo sobre estruturas de dados em árvore.

I – Uma árvore AVL (Adelson-Velskii e Landis) é uma árvore na qual as alturas das subárvores esquerda e direita de cada nó diferem no máximo em um elemento.

II – A árvore B é uma estrutura de dados que foi projetada para minimizar o número de acessos à memória secundária, sendo que cada nó associado pode ter mais de uma chave.

III – Uma Black-Red Tree é uma árvore B+ que possui um bit extra para armazenar a cor de cada nó.

Está CORRETO o que consta em:

Árvores AVL são uma estrutura de dados de árvore binária de busca balanceada, onde a diferença de altura entre as

subárvores esquerda e direita de qualquer nó não deve ser maior que 1. Considere as seguintes operações de rotação para balancear a árvore AVL:

I. Rotação simples à direita (RR).

II. Rotação simples à esquerda (RL).

III. Rotação dupla à direita (DRR).

IV. Rotação dupla à esquerda (DRL).

Dado o seguinte trecho de pseudocódigo para uma inserção em uma árvore AVL:

função inserir_avl(T, chave)

se T é vazia

criar novo nó com chave

senão se chave< T.chave

T.esquerda = inserir_avl(T.esquerda, chave)

se laltura(T.esquerda) - altura(T.direita)| > 1

realizar operação de rotação necessária

senão se chave> T.chave

T.direita = inserir_avl(T.direita, chave)

se laltura(T.esquerda)- altura(T.direita)| > 1

realizar operação de rotação necessária

Qual das seguintes opções descreve corretamente quando a rotação simples à direita (RR) deve ser aplicada durante a inserção?

O Registro do Windows é um banco de dados hierárquico que contém dados críticos para a operação do sistema operacional e dos aplicativos e serviços executados nele. Os dados são estruturados em um formato de árvore, e cada nó dessa árvore é chamado de: