Estruturas de Dados - Fila, Árvore Binária e Busca

Prévia do material em texto

TÓPICOS INTEGRADORES II
AOL 3
1. 
Parte superior do formulário
Pergunta 1
1 ponto
A Fila, tanto estática quanto dinâmica, fornece ao programador o seu estado em relação à quantidade de dados inseridas nela; caso esteja “limpa” ou “vazia”, seu estado é de que não contém elementos. Para o programador saber esse estado, a Fila contém a função isEmpty(), que significa literalmente “está limpa?”. Essa função que determina que se retorne true para sim, e false para não, determinando se ela está cheia.
Agora analise a função abaixo, sabendo que qtdElementos é contador de itens da Fila.
public boolean isEmpty(){
return (qtdElementos==-1);
}
Com base nessas informações e no conteúdo estudado, analise as afirmativas a seguir em relação ao código:
I. A linha do return poderia ser substituída por (qtdElementos==-1)? true : false;
II. O objeto qtdElementos é uma instância da classe Fila.
III. O tipo de retorno de isEmpty() é de acordo com o tipo do valor que armazena a estrutura.
IV. A qtdElementos fornece a quantidade de elementos da estrutura.
Está correto o que se afirma em:
I e IV.
Parte superior do formulário
Pergunta 2
1 ponto
As árvores dinâmicas são estruturas que organizam de forma hierárquica os dados. Existem muitas formas de representá-los: as que representam desenhos geralmente são mais simples de entender, porém mais difíceis de demonstrar em consoles de programas.
Observe a figura abaixo:
BQ03 - Tópicos Integradores II(ADS) - Questão 4.png
Com base nessas informações e no conteúdo estudado, determine o nome da representação da árvore na figura:
Diagrama de inclusão.
Parte superior do formulário
Pergunta 3
1 ponto
A árvore binária é uma aplicação da estrutura árvore, muito utilizada na computação, sobretudo por conta de suas propriedades e característica de balanceamento a cada operação; a princípio, ele se torna lento em muitas adições e subtrações de itens, mas, quando se trata de buscas, torna-se muito veloz, pois pode facilmente verificar quando tem o elemento buscado em si ou não.
Considerando essas informações e o conteúdo estudado, analise as afirmativas sobre as propriedades de Nó a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s):
I. ( ) O filho à esquerda de um nó tem o valor da chave menor que seu Pai, e o filho à direita possui o valor da chave maior ou igual a seu Pai.
II. ( ) Um nó é um conjunto de subárvores ou vazio.
III. ( ) Um nó é uma interligação entre dois nós.
IV. ( ) Um nó só pode ter de 0,1 até no máximo 2 filhos.
Agora, assinale a alternativa que apresenta a sequência correta:
V, F, F, V.
Parte inferior do formulário
Parte superior do formulário
Pergunta 4
1 ponto
A árvore possui muitos elementos interligados conhecidos como Nodes, que são objetos autorreferenciáveis que podem prover diversas formas de representar uma topologia ou interligação de objetos. Uma árvore geralmente armazena seus filhos e um valor que, em terminologia de árvore, pode chamar-se chave.
Com base nessas informações e no conteúdo estudado, assinale a alternativa contendo os atributos dos Nodes de uma árvore:
chave, esquerda e direita.
Parte superior do formulário
Pergunta 5
1 ponto
As árvores possuem muitas propriedades e suas propriedades podem ser usadas por muitos algoritmos. Elas são importantes pois, através delas, podemos ter um panorama real de como a estrutura da árvore se encontra.
Considerando as informações acima e o conteúdo estudado, analise as afirmativas sobre o(s) item(ns) que corresponde(m) ao termo Floresta:
I. ( ) Florestas são conjuntos de nós pais após a Raiz.
II. ( ) Floresta é o Nó que possui filhos.
III. ( ) Floresta é um conjunto de 0 ou mais árvores.
IV. ( ) Floresta é uma Raiz.
Está correto apenas o que se afirma em:
I e III.
Parte superior do formulário
Pergunta 6
1 ponto
A estrutura de árvore de representação encadeada demonstra um espaço entre os endereços dos filhos da direita e da esquerda e uma simbologia para os Nós nulos dos nós folhas ou folhas.
BQ03 - Tópicos Integradores II(ADS) - Questão 16.png
Observando a árvore acima e considerando o conteúdo estudado, identifique os valores da altura, grau da árvore e grau de saída de 16:
altura: 3, grau da árvore: 2 e grau de saída: 0
Parte inferior do formulário
Parte superior do formulário
Pergunta 7
1 ponto
A busca em árvore binária é o principal propósito da estrutura, a função de busca denominada buscar, no código abaixo, primeiramente recebe um valor e verifica se a chave do elemento é igual ao valor que está sendo buscado, depois ele retorna o que localizou através da variável true.
Leia o código abaixo:
public boolean buscar(int valor)
{
Node aux = this.raiz;
while ( aux != null )
{
if( aux.chave == valor ) return true;
aux = ( ___________ )? aux.esquerda : aux.direita;
}
return false;
}
Com base nessas informações e no conteúdo estudado, é correto afirmar que poderia ser utilizado na linha aux:
aux.chave > valor
Parte superior do formulário
Pergunta 8
1 ponto
A árvore é uma estrutura que é composta de node e suas ligações, porém sua organização e forma de utilização dependem do algoritmo escolhido, pois, utilizando uma árvore binária, os nós poderão possuir somente dois filhos e, dependendo das regras de balanceamento a cada nó inserido, ocorrerá o realinhamento de todos os nós. A árvore, diferente das demais estruturas, possui diversas propriedades, conceitos e terminologias que não se aplicam a outras estruturas.
Considerando essas informações e o conteúdo estudado, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s):
I. ( ) Node é uma estrutura referenciável que armazena valores dentro de uma árvore.
II. ( ) Cada Node possui apenas um Pai.
III. ( ) Cada Node pode possuir vários “irmãos”.
IV. ( ) Cada Node poderá ter dois antecessores.
Agora, assinale a alternativa que apresenta a sequência correta:
V, V, V, F.
Parte superior do formulário
Pergunta 9
1 ponto
As árvores são estruturas que em si são simples: possuem raiz, pais e filhos. O que diferencia uma árvore da outra é seu formato de trabalho ao inserir nós, suas regras primordiais para que a considere balanceada ou formas de balanceá-la.
Cada árvore geralmente tem o nome de uma das suas regras, como, por exemplo, a árvore binária que só pode ter 2 filhos, a árvore rubro-negra que insere atributo cor nos nodes para que haja balanceamento etc.
As árvores do tipo 2-3, por exemplo, são árvores diferenciadas que implementam o formato binário, e em alguns casos conseguem ser mais velozes que as demais árvores.
Considerando essas informações e o conteúdo estudado, analise as afirmativas a seguir sobre a árvore do tipo 2-3 e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
I. ( ) possui um pai com um único valor chave.
II. ( ) não possui no máximo dois irmãos.
III. ( ) não possui apenas um valor na chave.
IV. ( ) possui dois pais com dois valores chaves.
Agora, assinale a alternativa que apresenta a sequência correta:
F, V, V, F.
Parte inferior do formulário
Parte superior do formulário
Pergunta 10
1 ponto
Dentro da estrutura de árvores, os nós terminais são extremamente importantes, pois definem o limite da estrutura. Da mesma forma que a raiz inicia a ligação entre todos os elementos, o nó terminal finaliza a busca ou percurso.
BQ03 - Tópicos Integradores II(ADS) - Questão 19.png
Com base nessas informações e no conteúdo estudado, é correto afirmar que são os elementos terminais dessa árvore:
3, 4, 5 e 6.