Pesquisa - Atividade 4

Prévia do material em texto

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.Θ(logn2)
b.
Θ(n2).
c.
Θ.
d.
Θ(n2).
e.
Θ(n2).
Limpar minha escolha
Questão 2
Ainda não respondida
Vale 1,00 ponto(s).
Marcar questão
Texto da questão
De acordo com Viana, Cintra e Nobre (2015), o reequilíbrio eficiente de uma estrutura é a chave para fazer a árvore AVL funcionar corretamente, sem sacrificar seu desempenho. Para recuperar o equilíbrio de uma árvore AVL, devemos realizar uma ou mais rotações em sua estrutura.
VIANA, G. V. R.; CINTRA, G. F.; NOBRE; R. H. Pesquisa e ordenação de dados. 2. ed. Ceará: EdeuECE, 2015.
Assim sendo, entre as configurações a seguir, quais são os tipos de rotações usados para manter o equilíbrio da árvore?
I. Rotação à direita.
II. Rotação à esquerda.          
III. Rotação tripla à direita.
IV. Rotação dupla à esquerda.
V. Rotação dupla à direita.
Está correto o que se afirma em:
a.
I, III e V, apenas.
b.
II, III e IV, apenas.
c.
II, III, IV e V, apenas.
d.
I, II, IV e V, apenas.
e.
I, II e III, apenas.
Questão 3
Ainda não respondida
Vale 1,00 ponto(s).
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 por método e conteúdo.
c.
Buscas sequencial e binária.
d.
Buscas sequencial e ordenada.
e.
Buscas ordenada e desordenada.
Limpar minha escolha
Questão 4
Ainda não respondida
Vale 1,00 ponto(s).
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.
4.
c.
0.
d.
1.
e.
3.
Limpar minha escolha
Questão 5
Ainda não respondida
Vale 1,00 ponto(s).
Marcar questão
Texto da questão
Conforme pudemos estudos, de acordo com Viana, Cintra e Nobre (2015), a rotação dupla à esquerda é exatamente o que o nome sugere. Diz respeito aos primeiros nós que estão na subárvore da direita passarem para a esquerda, fazendo com que o filho da direita se torne a nova raiz.
VIANA, G. V. R.; CINTRA, G. F.; NOBRE; R. H. Pesquisa e ordenação de dados. 2. ed. Ceará: EdeuECE, 2015.
Assim, analise com cuidado a figura a seguir.
Fonte: Elaborada pela autora, 2019.
Agora, assinale a alternativa com a opção correta para realizar o equilíbrio na árvore da figura anterior, utilizando a rotação dupla à esquerda.
a.
b.
c.
d.
e.
Limpar minha escolha
Questão 6
Ainda não respondida
Vale 1,00 ponto(s).
Marcar questão
Texto da questão
A pesquisa binária é o algoritmo mais popular e eficiente, também tida como uma das técnicas mais usadas para solucionar problemas. Conforme pudemos compreender ao longo dos nossos estudos, trata-se de um algoritmo de busca em vetores que segue o paradigma de divisão e conquista.
Sendo assim, assinale a alternativa a seguir que traz a forma como os vetores devem estar dispostos para a busca binária funcionar.
a.
Mesclados.
b.
Dispersos.
c.
Desordenados.
d.
Ordenados.
e.
Intercalados.
Limpar minha escolha
Questão 7
Ainda não respondida
Vale 1,00 ponto(s).
Marcar questão
Texto da questão
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.
A+ e B+.
b.
AVL e B+.
c.
ATL e B.
d.
ALM e B.
e.
AVL e B-.
Limpar minha escolha
Questão 8
Ainda não respondida
Vale 1,00 ponto(s).
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ção e 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.
II, III e IV, apenas.
b.
III e IV, apenas.
c.
I, III, IV e V, apenas.
d.
I, II e III, apenas.
e.
II, IV e V, apenas.
Questão 9
Ainda não respondida
Vale 1,00 ponto(s).
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.
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 desequilibrada.
e.
Se -1 ≤ Q ≤ 1, temos uma árvore equilibrada.
Limpar minha escolha
Questão 10
Ainda não respondida
Vale 1,00 ponto(s).
Marcar questão
Texto da questão
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 alguns detalhes, como fator de carga, pois, caso contrário, os limites de tempo não são válidos. Além disso, também é válido escolher a função hashing com cuidado quando a chave não for uma sequência curta ou um número inteiro.
Sendo assim, a respeito do assunto, analise as configurações a seguir e as funções de hashings consideradas satisfatórias. Marque V para as afirmativas verdadeiras e F para as falsas.
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 de forma uniforme na tabela hashing.
Agora, assinale a alternativa com a sequência correta.
a.
V, V, F, F, V.
b.
F, V, V, F, F.
c.
V, F, V, V, V.
d.
V, V, F, V, F.
e.
F, V, F, V, V.