Questões de Concurso
Sobre árvores em algoritmos e estrutura de dados
Foram encontradas 344 questões
I. Árvores são estruturas de dados lineares. II. Em uma árvore cada nó pode ter no máximo dois filhos. III. Nós que não possuem filhos são chamados de Folhas.
Está correto o que se afirma em
( ) 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 é
Considere uma função de busca recursiva em uma estrutura de dados do tipo árvore binária de busca. A eficiência dessa função é crucial para a performance de consultas em um banco de dados que utiliza essa estrutura para indexação.
Elaborado pelo(a) autor(a).
Dada a importância da escalabilidade e do consumo eficiente de recursos, e considerando uma árvore binária de busca balanceada, a opção que oferece a melhor implementação para a função de busca é aquela que
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.
Que sequência obteremos, se executarmos o percurso em pós-ordem?
Considere o algoritmo a seguir, apresentado na forma de uma pseudolinguagem e que implementa uma certa funcionalidade, para responder às questões de números 50 e 51.
Início
- as [
- asd Tipo TM = matriz[1..4, 1..4] de inteiros;
- asdas Inteiro: c, i, j, k;
- asda TM: Mat;
- asdas c ← 1;
- asdasd Para i de 1 até 4 faça
- asd[
- as Se (c é ímpar)
- asd[
- asas Então
- asd[ c ← c + 3*i;
- asd Para j de 1 até 4 faça
- ad[
- asdMat[i,j] ← i + j + c;
- a]
- ,]
- asas Senão
- ,[
- asasddc ← c + 2*i + 1
- asdasd; Para k de 1 até 4 faça
- [
- asdasdiiaMat[i,k] ← i + k - c;
- aaaad]
- aasa]
- aaa]
- ii,,]
- ,]
- Fim.
Considere a seguinte estrutura de dados do tipo árvore.
Trata-se de uma árvore
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:
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
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
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:
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,
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.
Um dos possíveis somatórios do 2º , do 3º e do 4º valores exibidos por essa função é