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

Prévia do material em texto

Viana, Cintra e Nobre (2015) mencionam que, nas árvores de buscas balanceadas, as chaves alocadas são mantidas ordenadas, permitindo que a operação de busca seja realizada. Desta forma, percorre-se um ramo da árvore, da base até o início. Além disso, vários algoritmos foram desenvolvidos para a construção de árvores de busca que permanecem equilibradas.
VIANA, G. V. R.; CINTRA, G. F.; NOBRE; R. H. Pesquisa e ordenação de dados. 2. ed. Ceará: EdeuECE, 2015.
Sendo assim, a respeito dos tipos de árvores de buscas, assinale a alternativa a seguir que traz exemplos.
a.
AVL e B+.
b.
ATL e B.
c.
A+ e B+.
d.
ALM e B.
e.
AVL e B-.
Infelizmente sua resposta está errada. A alternativa assinalada não é uma árvore binária que vai seguir regras para inserção, busca e remoção de elementos. Releia nosso material de estudos e tente responder novamente!
Feedback
Sua resposta está incorreta.
A resposta correta é:
AVL e B+.
Questão 2
Correto
Atingiu 1,00 de 1,00
Marcar questão
Texto da questão
Conforme nossos estudos, 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 em uma árvore, o próximo passo é entender como corrigir o problema.
Sendo assim, assinale a alternativa a seguir que apresenta a forma como podemos corrigir um desequilíbrio.
a.
Movimentando apenas os filhos da árvore.
b.
Deslocamento.
c.
Movimentando apenas as raízes da árvore.
d.
Alterações de nós com filhos.
e.
Rotações.
Muito bem, sua resposta está certa! Uma vez detectado o desequilíbrio na árvore, o próximo passo é entender como corrigi-lo. Para tanto, podemos utilizar as chamadas rotações.
Feedback
Sua resposta está correta.
A resposta correta é:
Rotações.
Questão 3
Correto
Atingiu 1,00 de 1,00
Marcar questão
Texto da questão
A busca por elementos é bem comum na área da computação, em que podemos usar métodos e estruturas de dados diferenciadas. Assim, a procura pode ser realizada pelo índice ou pelo valor do elemento. A busca realizada pelo índice é considerada direta, ou seja, vai direto à posição da memória.
Sendo assim, para realizar a busca por valores, temos duas maneiras. Quais seriam elas?
a.
Buscas por nome e número.
b.
Buscas ordenada e desordenada.
c.
Buscas sequencial e binária.
Isso mesmo, sua resposta está correta! Para realizar a busca por valores, temos duas maneiras: sequencial ou binária. A busca sequencial percorre todas as posições do vetor, verificando uma a uma, até se achar o valor desejado ou chegar ao final sem achá-lo.Já na busca binária o vetor é dividido ao meio e a busca é realizada apenas em uma das metades.
d.
Buscas por método e conteúdo.
e.
Buscas sequencial e ordenada.
Feedback
Sua resposta está correta.
A resposta correta é:
Buscas sequencial e binária.
Questão 4
Correto
Atingiu 1,00 de 1,00
Marcar questão
Texto da questão
Com base em nosso material de estudos, pudemos entender que uma das 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 ou comparar registro.
Nesse sentido, temos que o hashing tem dois ingredientes fundamentais. Quais são eles?
a.
Função e tabela hashings.
b.
Tabela hashing e espelhamento.
c.
Hashing modular e função de espelhamento.
d.
Colisões e tabela de dispersão.
e.
Função de hashing e resolução de colisões.
Isso mesmo, sua resposta está correta! O hashing é uma técnica que usa certa função para transformar uma chave em endereço. Já a colisão acontece quando a função produz o mesmo endereçamento para chaves diferentes.
Feedback
Sua resposta está correta.
A resposta correta é:
Função de hashing e resolução de colisões.
Questão 5
Correto
Atingiu 1,00 de 1,00
Marcar questão
Texto da questão
O hashing fechado, também conhecido como endereçamento fechado, é uma alternativa para resolver colisões com listas vinculadas. Em um sistema de hashing fechado, se acontecer uma colisão, células alternativas são tentadas até que uma célula vazia seja encontrada.
Sendo assim, analise a tabela a seguir.
Fonte: Elaborada pela autora, 2019.
Agora, assinale a alternativa com o valor da posição para a chave 3 descrita na tabela, utilizando o método do hashing fechado.
a.
4.
b.
0.
Resposta correta, parabéns! Adotando h(x) = x mod m, em que m = 10, temos h(3) = 3 mod 10 = 3. Como a posição 3 se encontra ocupada, procura-se a próxima posição disponível (0) para que o 3 seja alocando.
c.
3.
d.
2.
e.
1.
Feedback
Sua resposta está correta.
A resposta correta é:
0.
Questão 6
Incorreto
Atingiu 0,00 de 1,00
Marcar questão
Texto da questão
Em 1962, dois cientistas da computação mudaram o cenário das estruturas da árvore de pesquisa binária. Eles criaram uma árvore revolucionária de equilíbrio automático que alcança a pior complexidade temporal. Tanto as operações de inserção quanto de remoção percorrem, no pior caso, todos os níveis da heap binária, realizando trocas de valores.
Sendo assim, assinale a alternativa a seguir com o pior caso de tempo de execução para procurar um elemento equilibrado em uma árvore de pesquisa binária, tendo esta n2n elementos.
a.
Θ(n2).
b.
ΘNão.
c.
Θ(n2).
d.
Θ(logn2)
Infelizmente sua resposta está incorreta. Tanto as operações de inserção quanto de remoção percorrem, no pior caso, todos os níveis da heap binária, realizando trocas de valores. Como a estrutura é plenamente balanceada, ela mantém sempre a altura logarítmica. Reveja o conteúdo sobre o tema e tente responder novamente!
e.
Θ(n2).
Feedback
Sua resposta está incorreta.
A resposta correta é: ΘNão.
Questão 7
Correto
Atingiu 1,00 de 1,00
Marcar questão
Texto da questão
O equilíbrio está relacionado à altura da subárvore. Assim, podemos escrever um método de “altura” que desça determinada subárvore. No entanto, isto pode ser caro em termos de tempo de CPU, pois os cálculos precisam ser feitos repetidamente, enquanto tentamos determinar o equilíbrio de cada subárvore. Em vez disso, é mais fácil armazenar um "fator de equilíbrio" em cada nó.
Sendo assim, assinale a alternativa a seguir com a fórmula para calcular o fator de equilíbrio de uma árvore AVL.
a.
Se -2 ≤ Q ≤ 1, temos uma árvore equilibrada.
b.
(Q = R - L), em que “R” é o número de níveis à direita e “L” é o número de níveis à esquerda.
Resposta correta, parabéns! Para calcular o fator de equilíbrio, adotamos a equação Q = R – L, em que “R” é o número de níveis à direita e “L” é o número de níveis à esquerda.
c.
(Q = A - L), em que “A” é o número de nós e “L” é o número de níveis à esquerda.
d.
Se -1 ≤ Q ≤ 1, temos uma árvore equilibrada.
e.
Se -1 ≤ Q ≤ 1, temos uma árvore desequilibrada.
Feedback
Sua resposta está correta.
A resposta correta é:
(Q = R - L), em que “R” é o número de níveis à direita e “L” é o número de níveis à esquerda.
Questão 8
Correto
Atingiu 1,00 de 1,00
Marcar questão
Texto da questão
Conforme nossos estudos, sabemos que o equilíbrio de uma árvore de busca é medido com a subtração do número de níveis na subárvore da esquerda do número de níveis na subárvore da direita.
Assim sendo, analise com atenção a estrutura de uma árvore AVL na figura a seguir.
Fonte: Elaborada pela autora, 2019.
De acordo com a figura anterior, assinale a alternativa que contém o nó que se encontra em desequilíbrio.
a.
B(-2).
Resposta correta, parabéns! Uma árvore está desequilibrada quando o número for maior que 1 ou menor que -1. Em alguns casos, não podemos fazer a árvore ter um equilíbrio completamente nulo. Assim, qualquer número entre 1 e -1 será considerado o desequilíbrio. No caso em questão, se inicia o desequilíbrio em B(-2).
b.
H(1).
c.
F(0).
d.
G(0).
e.
D(0).
Feedback
Sua resposta está correta.
A resposta correta é:
B(-2).
Questão 9
Correto
Atingiu 1,00 de 1,00
Marcar questão
Texto da questão
Árvores B são usados por vários sistemas de arquivos para representarem dados e diretórios. Em comparação aos blocos indiretos tradicionais, as árvores B oferecem busca, inserçãoe remoção garantidas de chaves de tempo logarítmico. Além disso, elas podem representar de forma satisfatória arquivos esparsos.
Sendo assim, entre as configurações listadas a seguir, quais condizem com as propriedades da árvore B?
I. Uma árvore B é definida pelo termo grau mínimo “t”, sendo que seu valor 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.
Está correto o que se afirma em:
a.
I, III, IV e V, apenas.
b.
I, II e III, apenas.
Isso mesmo, certa resposta! As propriedades da árvore B são definidas pelo termo grau mínimo “t”, sendo que seu valor depende do tamanho do bloco de disco. Além disso, todos os nós, incluindo raiz, podem conter, no máximo, 2t - 1 chaves. Todo nó do tipo folha possui a mesma profundidade entre eles e o nó da raiz.
c.
II, IV e V, apenas.
d.
III e IV, apenas.
e.
II, III e IV, apenas.
Feedback
Sua resposta está correta.
A resposta correta é:
I, II e III, apenas.
Questão 10
Correto
Atingiu 1,00 de 1,00
Marcar questão
Texto da questão
Conforme descobrimos em nossos estudos, o hashing aberto tem a desvantagem de exigir ponteiros. Isto tende a desacelerar um pouco o algoritmo por causa do tempo necessário para alocar novas células,assim como requer essencialmente a implementação de uma segunda estrutura de dados.
Sendo assim, analise a tabela a seguir.
Fonte: Elaborada pela autora, 2019.
Agora, assinale a alternativa com o valor da posição para a chave 21 descrita na tabela, utilizando o método do hashing aberto.
a.
2.
b.
1.
c.
3.
d.
4.
e.
0.
Resposta correta, muito bem! Adotando h(x) = x mod m, em que m = 5, temos h(21) = 21 mod 5 = 1. Trabalhando com a técnica de hashing aberto, é possível a inserção da chave na posição da função hashing, ou seja, o 21 será alocado na posição 1 na segunda estrutura de dados.
Feedback
Sua resposta está correta.
A resposta correta é:
0.
<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 0 240 240" width="16" height="16" preserveAspectRatio="xMinYMid meet"><style>.st0{display:none}.st1{display:inline;fill:url(#SVGID_1_);stroke:#000;stroke-width:.5;stroke-miterlimit:10}.st2{fill:url(#SVGID_2_)}.st3,.st4,.st5{stroke-miterlimit:10}.st3{fill:#e29b46;stroke-width:.5;stroke:#e29b46}.st4,.st5{stroke:#000}.st4{display:none;fill:none;stroke-width:13}.st5{stroke-width:.5}</style><image width="15" height="15" xlink:href="57724704FC4A9760.jpg" transform="scale(16)" overflow="visible" id="Ebene_1" class="st0"/><g id="Ebene_3"><g id="Ebene_4" class="st0"><linearGradient id="SVGID_1_" gradientUnits="userSpaceOnUse" x1=".5" y1="120.5" x2="240.5" y2="120.5"><stop offset="0" stop-color="#e6c1a8" stop-opacity=".9"/><stop offset="1" stop-color="#f7ac4b" stop-opacity=".9"/></linearGradient><path class="st1" d="M.5.5h240v240H.5z"/></g><linearGradient id="SVGID_2_" gradientUnits="userSpaceOnUse" x1="11.569" y1="120.274" x2="226.145" y2="120.274" gradientTransform="matrix(1 0 0 -1 0 237.258)"><stop offset="0" stop-color="#e6c1a8" stop-opacity=".9"/><stop offset="1" stop-color="#f7ac4b" stop-opacity=".9"/></linearGradient><path class="st2" d="M85.7 224.9c-13.5 2.5-20.5-3.2-25-18.7-1.6-5.7-2.1-11.5 5.7-24.7 10-17 11-19 20-46 1-3-7.2-.8-22.7-2.3-17-1.6-42-5.7-50-22.7-4.2-9-2.7-17.8 10.3-27.8 0 0-10.5-10.2-3-21.7 8.2-12.6 13-6.8 13-6.8-.5-1.5-2.3-13.6 1-17.8 7-9 15.1-4.9 19.7-11.6 3.2-4.7 4.2-7.4 9.3-11.5 11-9 34-4.7 38.8-3.8 5.2 1 9.3-1.7 29.2.1 11 1 42.5 23.1 52.7 29.2 5.9 3.5 34.2-3 33.5 5.8-2 24 20.2 29.5-1.8 72.5-2.1 4.1-8.1-.1-21.7.2-8.1.2-8.6 1.1-10 1.4-7.3 1.6-12.7 5.2-15 8-12 14-18.6 20.6-34 37.3-13.4 14.6-21.9 18.5-29 26-18 19-11.4 29.3-15.7 35.7-1.3 1.9-3.4-1.1-5.3-.8z"/><path class="st3" d="M229 79.3c0 14.2-3.8 28.2-11.5 41.7h-24.9c-5.8 0-10 .8-12.6 2.4-2.6 1.6-7.1 6-13.5 13.2l-5.9 6.5c-6.7 7.4-11.3 12.4-14 15L107.1 193l-10.7 33.3-6.2 4.7c-22.3-4.4-33.4-15.4-33.4-32.9 0-6.3 3.7-15.4 11-27l3.4-4.9c6.1-9.9 10-20.2 11.7-30.8h-5.3c-20.9 0-37.6-3-50.2-8.8-12.6-5.9-19-13.7-19-23.4 0-8.4 3.8-16 11.5-22.8-3.1-4.1-4.7-8-4.7-11.6 0-4.5 1.5-8.2 4.4-11.1 2.9-3 7.2-5.1 12.8-6.4-.3-2.1-.4-3.8-.4-4.9 0-11.1 1.7-17.1 17-18.2-.3-1.5 5.6-2.5 5.6-3.2C54.7 12.5 65.2 6.3 86 6.3h9.1l7.6 3.2c9.2-2.1 17.4-3.2 24.7-3.2 2.6 0 6.6 3.2 11.9 3.6 17 6.5 32.9 10.7 47.4 24.6l31.8 3c7 13.9 10.5 27.9 10.5 41.8zm-46.8-35.7c-11.8-13-27.1-18-46-27.1l-8.3-3.2c-3 0-6.6.4-10.8 1.1l23.2 12.7c-4.4 8-7.3 11.2-14.4 15.6l10.2 8.1c-5.5 8.2-8.6 11-15.1 14.5l5.4 3c-4.9 9.1-8.7 15.4-17.7 19.1l4.3 5.8c-8.4 15.3-18.6 20-36.8 20-3.4 0-7.2-.4-11.3-1.3-4.1-.8-8.6-2.1-13.7-3.9l-17.3-.2 10-8.9 10 .4c5.4 1.9 10.1 3.3 14.1 4.3 3.9.9 7.2 1.4 9.8 1.4 9.8 0 17.6-3.7 23.5-11L62.6 79.7l-13 .1c-8.5 0-15.7 2.4-21.6 7.1-5.9 4.7-8.9 10.5-8.9 17.3 0 7.5 5.7 13.2 17.1 16.9 11.3 3.7 28.3 5.5 50.9 5.5l1.7 3 5.8 2c0 13.9-5.5 28.5-16.7 43.9l-2.7 3.9c-4.9 6.7-7.3 13-7.3 18.7 0 11.1 7.1 18.7 21.4 22.7l8.5-32.8 42.8-37.9c7.2-7.5 12.7-13.3 16.3-17.4 9.1-10.6 15.9-16.8 20.5-18.6 4.5-1.7 15.7-2.7 33.6-2.7 4.9-11.2 7.3-22.6 7.3-34.1 0-9.8-2.2-20.1-6.6-30.8l-29.5-2.9zM75.1 57.8H52.5c-8.6 0-15.1.9-19.5 2.7-4.3 1.9-6.5 4.6-6.5 8.2 0 1.9 1 3.9 2.7 6 5.5-2.5 13.6-3.8 24.3-3.8h11.3l31.7 11.8c7-1.5 12.9-5.1 17.9-10.6L75.1 57.8zm7.7-21.3h-16C50.2 36.5 41.9 40 41.9 47l.6 2.3L77 49l32.6 12c4.7-1.9 8.7-4.5 12.1-7.7.4-.5 1-1.1 1.7-1.8l-40.6-15zM93 14.6h-7c-13.8 0-26.7 3.9-26.7 11.8v1.1h25.6l30.5 11.3c4.1-2.6 7.5-5.4 10.2-8.6.6-.6 1.3-1.4 2.3-2.5L93 14.6z" id="Layer_1"/><g id="Layer_1_1_" class="st0"><path class="st5" d="M220.6 199.9l-31.8 3c-14.6 13.9-30.4 18.1-47.4 24.6-5.4.4-9.4 3.6-11.9 3.6-7.3 0-15.5-1.1-24.7-3.2l-7.6 3.2H88c-20.9 0-31.3-6.2-31.3-18.6 0-.7-5.9-1.7-5.6-3.2-15.3-1-17-7.1-17-18.2 0-1.2.1-2.8.4-4.9-5.7-1.3-10-3.4-12.8-6.4-2.9-2.9-4.4-6.6-4.4-11.1 0-3.6 1.5-7.5 4.7-11.6-7.6-6.8-11.5-14.4-11.5-22.8 0-9.7 6.3-17.4 19-23.4 12.6-5.8 29.4-8.8 50.2-8.8H85c-1.7-10.6-5.6-20.9-11.7-30.8l-3.4-4.9c-7.3-11.7-11-20.7-11-27 0-17.6 11.1-28.6 33.4-32.9l6.2 4.7 10.7 33.3 39.4 34.8c2.7 2.6 7.3 7.6 14 15l5.9 6.5c6.4 7.2 10.9 11.6 13.5 13.2 2.6 1.6 6.8 2.4 12.6 2.4h24.9c7.6 13.5 11.5 27.5 11.5 41.7 0 13.7-3.5 27.8-10.4 41.8zm-7-9.2c4.5-10.7 6.6-21 6.6-30.8 0-11.5-2.4-22.9-7.3-34.1-17.9 0-29-.9-33.6-2.7-4.6-1.7-11.4-8-20.5-18.6-3.6-4.1-9.1-10-16.3-17.4L99.7 49.2l-8.5-32.8C77 20.5 69.9 28.1 69.9 39.2c0 5.7 2.4 12 7.3 18.7l2.7 3.9c11.1 15.4 16.7 30 16.7 43.9l-5.8 2-1.7 3c-22.5 0-39.5 1.9-50.9 5.5-11.4 3.8-17.1 9.4-17.1 16.9 0 6.8 3 12.6 8.9 17.3 5.9 4.7 13.1 7.1 21.6 7.1l13 .1 38.6-14.4c-5.8-7.3-13.7-11-23.5-11-2.6 0-5.8.5-9.8 1.4-4 1-8.6 2.4-14.1 4.3l-10 .4-10-8.9 17.3-.2c5-1.7 9.5-3.1 13.7-3.9 4.1-.8 7.9-1.3 11.3-1.3 18.2 0 28.5 4.7 36.8 20l-4.3 5.8c8.9 3.6 12.8 10 17.7 19.1l-5.4 3c6.6 3.4 9.6 6.3 15.1 14.5l-10.2 8.1c7.2 4.4 10 7.6 14.4 15.6L119 222.8c4.2.7 7.9 1.1 10.8 1.1l8.3-3.2c18.9-9.1 34.2-14.1 46-27.1l29.5-2.9zM116.5 165c-4.9-5.5-10.9-9.1-17.9-10.6l-31.7 11.8H55.6c-10.7 0-18.8-1.3-24.3-3.8-1.8 2.1-2.7 4.2-2.7 6 0 3.6 2.2 6.3 6.5 8.2 4.3 1.8 10.8 2.7 19.5 2.7h22.6l39.3-14.3zm8.9 20.7c-.6-.7-1.2-1.3-1.7-1.8-3.4-3.3-7.5-5.9-12.1-7.7l-32.6 12-34.4-.2-.6 2.3c0 6.9 8.3 10.5 24.9 10.5h16l40.5-15.1zm4.5 23.9c-1-1-1.7-1.9-2.3-2.5-2.7-3.2-6.1-6-10.2-8.6l-30.5 11.3H61.3v1.1c0 7.9 12.9 11.8 26.7 11.8h7l34.9-13.1z"/></g></g></svg>