PO E TÉCNICAS DE ARMAZENAMENTO - A3

Prévia do material em texto

1. Uma vez detectado o desequilíbrio na árvore o próximo passo é entender como corrigir o 
desequilíbrio. O equilíbrio da árvore é corrigido através das chamadas rotações. 
 
Assinale a alternativa com a fórmula para calcular o fator de equilíbrio de uma árvore AVL. 
Resposta correta. Para calcular o fator de equilíbrio adotamos a equação ( Q = R - L), onde R = número de 
níveis a direita e L = número de níveis a esquerda. 
• .Nenhuma das alternativas. 
• . SE -1 ≤ Q ≤ 
1 - >Árvore equilibra. 
• . SE -1 ≤ 
Q ≤ 1 - >Árvore desequilibrada. 
• .( Q = A - L), onde A = número de nó e L = número de níveis a esquerda. 
✓ .( Q = R - L), onde R = número de níveis a direita e L 
= número de níveis a esquerda. 
 
2. De acordo com Viana a rotação dupla à esquerda consiste em como o próprio nome sugere, os 
primeiros (nós) que estão na subárvore da direita passam para a esquerda fazendo com que o filho 
da direita se torne a nova raiz (VIANA, Gerardo Valdisio Rodrigues; CINTRA, Glauber Ferreira; 
NOBRE; Ricardo Holanda. Pesquisa e ordenação de Dados. 2 edição. EdeuECE, 2015.). 
 
Assinale a alternativa com a opção correta para realizar o equilíbrio na árvore da figura abaixo, 
usando a rotação dupla à esquerda. 
 
Figura: Árvore binária desequilibrada. Fonte: Autor. 
Resposta correta. Para corrigir o problema de desequilíbrio proposto pela figura podemos adotar como 
solução, realizar uma rotação à direita na subárvore da direita logo em seguida realizar uma rotação à 
esquerda na árvore original. 
• 
 
. Nenhuma das alternativas. 
• . . 
• . . 
• . . 
✓ . 
 
3. A idéia essencial por trás de uma tabela de dispersão é que todas as informações são 
armazenadas em uma matriz de tamanho fixo. O hashing é usado para identificar a posição em 
que um item deve ser armazenado. 
 
Assinale a alternativa com os tipos de hashing mais usados. 
Resposta correta. Os tipos de hashing pode ser divididos em duas formas, sendo ela hashing fechado no 
qual é permitido o armazenar um conjunto de informações de tamanho limitado e o hashing aberto no 
qual é permitido armazenar um conjunto de informações de tamanho limitado. 
• .Nenhuma das alternativas. 
• .Hashing fechado e hashing disperso. 
• .Hashing de endereçamento e hashing disperso. 
• .Hashing aberto e hashing chaves. 
✓ .Hashing aberto e hashing fechado. 
 
4. As vantagens da tabela de dispersão é que ela pode ser usada como índice, porém a grande 
vantagem está em se ter uma operação cujo acesso é direto, ou seja não é preciso fazer um 
percurso em uma árvore, não é preciso comparar registro, pois é uma operação onde vai direto 
para aquele registro. 
 
O hashing tem dois ingredientes fundamentais, assinale a alternativa com os respectivos. 
Resposta correta. O hashing é uma técnica que usa uma função para transformar uma chave em um 
endereço. Já a colisão acontece quando a função hashing produz o mesmo endereçamento para chaves 
diferentes. 
• . Nenhuma das alternativas. 
• .Colisões e tabela de dispersão. 
• . Hashing modular e Função de espelhamento. 
• .Função hashing e tabela hashing. 
✓ .Função de hashing e resolução de colisões. 
 
5. Formalmente, definimos uma Árvore B + pelos valores M e L, onde M é igual ao número máximo de 
filhos que um determinado nó pode ter e L é igual ao número máximo de registros de dados 
armazenados em um nó folha. 
 
Uma árvore B + da ordem M é uma árvore que satisfaz uma das propriedade abaixo, assinale qual. 
Resposta correta. Uma árvore B+ da ordem M é uma árvore que cada nó tem no máximo M filhos. 
• .Nenhuma das alternativas. 
• . O maior registro de dados entre as chaves de pesquisa x e y é igual a x. 
• .O nó tem pelo menos vinte filhos se não for uma folha. 
• . Nenhuma das folhas aparecem no mesmo nível da árvore. 
✓ .Cada nó tem no máximo M filhos. 
 
6. Uma pesquisa sequencial é quando você olha para cada parte dos dados, um por um, e não para 
até encontrar o que está procurando. Você pode usar uma pesquisa sequencial em qualquer dado. 
No entanto, a pesquisa sequencial é a única opção que você pode usar quando é preciso 
pesquisar dados desordenados. 
 
Entre as configurações a seguir, quais são as diferenças entre os métodos de busca sequencial e 
busca binária? 
 
I.Os dados de entrada precisam ser classificados na Pesquisa binária e não na Pesquisa linear. 
II.A pesquisa linear faz o acesso sequencial, enquanto a pesquisa binária acessa dados 
aleatoriamente. 
III. A pesquisa binária realiza o acesso de forma sequencial. 
IV.A pesquisa linear não realiza o acesso sequencial. 
V.A pesquisa linear realiza comparações de igualdade e a pesquisa binária realiza comparações de 
pedidos. 
 
Agora, assinale a alternativa que apresenta as diferenças existentes entre as duas buscas, ou seja, 
tanto a sequencial como a binária. 
Resposta correta. As diferenças importantes entre a busca sequencial e busca binária é que os dados de 
entrada precisam ser classificados na Pesquisa binária e não na Pesquisa linear, assim como para a 
pesquisa linear é realizado o acesso sequencial, enquanto a pesquisa binária acessa dados de forma 
aleatória. 
A Complexidade temporal da pesquisa linear é -O(n) e para pesquisa binária possui complexidade 
temporal de O(log n). 
A pesquisa linear realiza comparações de igualdade e a pesquisa binária realiza comparações de 
pedidos. 
• II, III e IV. 
• I, III, IV e V. 
• I, II, III, IV e V. 
• II, IV e V. 
✓ I, II e V. 
 
7. Em 1962, dois cientistas da computação, mudaram para sempre o cenário das estruturas da 
Árvore de Pesquisa Binária quando criaram uma árvore revolucionária de auto-equilíbrio que 
alcança a pior complexidade temporal de O (log n ). 
 
Assinale a alternativa com os respectivos nomes desses cientistas. 
Resposta correta. Em 1962, dois cientistas da computação soviéticos, Georgy Adelson Velsky e Evgenii 
Landis, mudaram para sempre o cenário das estruturas da Árvore de Pesquisa Binária. 
• .Nenhuma das alternativas 
• .Adelson e Velsky. 
• .Georgy Adelson e Valiston. 
• .Evgenii Landis e Frederic. 
✓ .Georgy Adelson Velsky e Evgenii Landis. 
 
8. O equilíbrio de uma árvore de busca é medido subtraindo o número de níveis na subárvore da 
esquerda do número de níveis na subárvore da direita. 
 
De acordo com a Figura abaixo assinale a alternativa que contém o nó 
que encontra-se em desequilíbrio. 
 
Figura: Árvore binária AVL. Fonte: Autor. 
Resposta correta. Uma árvore está desequilibrada quando este número for maior do que 1 ou menor que 
-1, ou seja em alguns casos não podemos fazer a árvore ter um equilíbrio completamente nulo. Qualquer 
número entre 1 e -1, será considerado o desequilíbrio, portanto o Nó 
no qual se inicia o desequilíbrio é o B(-2). 
• .F(0). 
• . D(0). 
• .H(1). 
• .G(0). 
✓ .B(-2). 
 
9. As tabelas de hashing podem ser usadas para implementar a inserção e encontrar operações em 
tempo médio constante. É especialmente importante prestar atenção a detalhes como fator de 
carga ao usar tabelas de hashing, pois caso contrário os limites de tempo não são válidos. Também 
é importante escolher a função hashing com cuidado quando a chave não for uma sequência curta 
ou um número inteiro. 
 
Entre as configurações a seguir, quais funções de hashing são consideradas satisfatória? 
 
I. Rápido de calcular o O(1) 
II.Tem menos colisões 
III.Tem mais colisões 
IV. Distribui as chaves de forma não uniforme na tabela 
V.Espalha as chaves uniforme na tabela hashing 
 
Agora, assinale a alternativa que apresenta os conceitos de uma boa funções hashing. 
Resposta correta. Uma função hashing é considerada satisfatória quando é rápida de calcular o O(1) e 
apresenta poucas colisões, assim como as chaves são espalhadas de forma distribuída entre a tabela de 
dispersão. 
• II, III e IV. 
• I, III, IV e V. 
• I, II, III, IV e V. 
• II, IV e V. 
• I, II e V. 
 
10.Nas árvores de busca balanceada, as chaves alocadas são mantidas ordenadas, permitindo que a 
operação de busca seja realizada, percorrendo um ramo da árvore, desde a base até chegar ao 
início (VIANA, Gerardo Valdisio Rodrigues; CINTRA, Glauber Ferreira; NOBRE; Ricardo Holanda. 
Pesquisa e ordenação de Dados. 2 edição. EdeuECE, 2015.). 
 
Assinale a alternativa que diz respeito a uma árvore de busca balanceada. 
Resposta correta. A árvore AVL é uma árvore binária que vai seguir as mesmas regras para inserção, 
busca e remoção de elementos, e adicionar essas regras a métodos para se manter o equilíbrio da 
árvore. 
• .DEF. 
• .BCG. 
• .CVF. 
• .AVC. 
✓ . AVL.