PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO - ATIVIDADE 04

Prévia do material em texto

• Pergunta 1 
1 em 1 pontos 
 
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 Selecionada: 
I, II e V. 
Resposta Correta: 
I, II e V. 
Comentário 
da resposta: 
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. 
 
 
• Pergunta 2 
1 em 1 pontos 
 
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 Selecionada: 
.Função de hashing e resolução de colisões. 
Resposta Correta: 
.Função de hashing e resolução de colisões. 
Comentário da 
resposta: 
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. 
 
 
• Pergunta 3 
1 em 1 pontos 
 
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 Selecionada: 
.Georgy Adelson Velsky e Evgenii Landis. 
Resposta Correta: 
.Georgy Adelson Velsky e Evgenii Landis. 
Comentário da 
resposta: 
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. 
 
 
• Pergunta 4 
1 em 1 pontos 
 
A pesquisa binária funciona apenas em um conjunto com elementos 
ordenados. Para usar a pesquisa binária em uma coleção, a coleção deve 
primeiro ser classificada. 
Quando a pesquisa binária é usada para executar operações em um 
conjunto ordenado, o número de iterações sempre pode ser reduzido com 
base no valor que está sendo pesquisado. 
 
 
Antes de iniciar a pesquisa binária, primeiro definimos o início e fim do 
intervalo, assinale a alternativa com a afirmativa corretas para o início e o 
fim desse intervalo. 
Vamos considerar a seguinte matriz: 
1 2 3 4 5 6 7 8 9 10 
 
Figura: Vetor Ordenado 
Resposta Selecionada: 
.Início = 0 e fim = 9. 
Resposta Correta: 
.Início = 0 e fim = 9. 
Comentário da 
resposta: 
Resposta correta. O início do intervalo é definido como Low 
= 0, e o fim do intervalo é definido como High = n-1, ou seja, 
High = 10-1 = 9. 
 
 
• Pergunta 5 
1 em 1 pontos 
 
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 Selecionada: 
.B(-2). 
Resposta Correta: 
.B(-2). 
Comentário 
da resposta: 
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). 
 
 
• Pergunta 6 
1 em 1 pontos 
 
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 Selecionada: 
. AVL. 
Resposta Correta: 
. AVL. 
Comentário da 
resposta: 
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. 
 
 
• Pergunta 7 
1 em 1 pontos 
 
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 Selecionada: 
.Cada nó tem no máximo M filhos. 
Resposta Correta: 
.Cada nó tem no máximo M filhos. 
Comentário da 
resposta: 
Resposta correta. Uma árvore B+ da ordem M é uma árvore 
que cada nó tem no máximo M filhos. 
 
 
• Pergunta 8 
0 em 1 pontos 
 
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 Selecionada: 
. . 
Resposta Correta: 
. . 
Comentário 
da resposta: 
Sua resposta está incorreta. Para corrigir o desequilíbrio onde a 
rotação simples nao funciona, podemos adotar como solução, 
realizar uma rotação à direita na subárvore da direita e em 
seguida realizar uma rotação à esquerda na árvore original. 
 
• Pergunta 9 
1 em 1 pontos 
 
Ambas árvore B e B+ são árvores de auto-equilíbrio que possuem operações 
logarítmicas de inserção, localização e exclusão. 
 
Entre as configurações a seguir, quais alternativas condizem com as propriedades 
da árvore B? 
 
I. Uma árvore B é definida pelo termo grau mínimo t. O valor de t depende do 
tamanho do bloco de disco. 
II.Todos os ( nós) 
(incluindo raiz) podem conter no máximo 2t - 1 chaves. 
III.Todo nó 
do tipo folha possui a mesma profundidade entre eles e o ( nó) da raiz. 
IV.Nenhuma das folhas estão no mesmo nível. 
V.Nenhum nó 
possui a mesma profundidade entre o ( nó) da raiz. 
 
Agora, assinale a alternativa que apresenta as propriedades da árvore B.Resposta Selecionada: 
I, II e III. 
Resposta Correta: 
 
I, II e III. 
Comentário 
da resposta: 
Resposta correta. As propriedades da árvore B é definida pelo 
termo grau mínimo t. O valor de t depende do tamanho do bloco 
de disco. Assim como, todos os ( nós) (incluindo raiz) podem 
conter no máximo 2t - 1 chaves e Todo nó do tipo folha possui a 
mesma profundidade entre eles e o ( nó) da raiz. 
 
• Pergunta 10 
1 em 1 pontos 
 
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. 
Uma vez detectado o desequilíbrio na árvore o próximo passo é entender como 
corrigir o desequilíbrio. 
 
Assinale a alternativa com a forma a qual podemos corrigir este desequilíbrio. 
 
Resposta Selecionada: 
.Rotações. 
Resposta Correta: 
.Rotações. 
Comentário da 
resposta: 
Resposta correta. 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.