Atividade 4 (A2)_ Pesquisa e Ordenação

Prévia do material em texto

Iniciado em sexta, 30 set 2022, 12:58
Estado Finalizada
Concluída em sexta, 30 set 2022, 13:07
Tempo
empregado
9 minutos 36 segundos
Avaliar 10,00 de um máximo de 10,00(100%)
Questão 1
Correto
Atingiu 1,00 de 1,00
Questão 2
Correto
Atingiu 1,00 de 1,00
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.
a. .Nenhuma das alternativas.
b. .(Q = R - L), onde R = número de níveis a direita e L
 = número de níveis a esquerda.
c. .(Q = A - L), onde A = número de nó e L = número de níveis a esquerda.
d. .SE -1 ≤
 Q ≤ 1 - >Árvore desequilibrada.
e. . SE -1 ≤ Q ≤
 1 - >Árvore equilibra.
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.
a. .Nenhuma das alternativas
b. .Georgy Adelson Velsky e Evgenii Landis.
c. .Evgenii Landis e Frederic.
d. .Adelson e Velsky.
e. .Georgy Adelson e Valiston.
Questão 3
Correto
Atingiu 1,00 de 1,00
Questão 4
Correto
Atingiu 1,00 de 1,00
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.
a. II, III e IV.
b. II, IV e V.
c. I, II, III, IV e V.
d. I, II e V.
e. I, III, IV e V.
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.
a. .B(-2).
b. .H(1).
c. .F(0).
d. . D(0).
e. .G(0).
Questão 5
Correto
Atingiu 1,00 de 1,00
A busca é bem comum na área da computação, onde podemos usar muitos método e estruturas de dados para está realizando essa
busca, ela pode ser realizada pelo índice ou pelo valor. A busca realizada pelo índice é considerada uma busca direta, ou seja, vai direto
na posição da memória.
 
 Para realizar essa busca por valor temos duas maneiras, assinale a alternativa que condiz com essas maneiras.
a. .Busca sequencial e busca binária.
b. .Busca pelo método.
c. .Nenhuma das alternativas.
d. .Busca por nome e Busca por Número.
e. .Busca ordenada e desordenada.
Questão 6
Correto
Atingiu 1,00 de 1,00
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.
a.
. .
b.
. .
c. . Nenhuma das alternativas.
d.
. .
e.
. .
Questão 7
Correto
Atingiu 1,00 de 1,00
Questão 8
Correto
Atingiu 1,00 de 1,00
Questão 9
Correto
Atingiu 1,00 de 1,00
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.
a. .Hashing fechado e hashing disperso.
b. .Hashing aberto e hashing fechado.
c. .Nenhuma das alternativas.
d. .Hashing aberto e hashing chaves.
e. .Hashing de endereçamento e hashing disperso.
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
a. .Início = 5 e fim = 10.
b. .Início = 0 e fim = 9.
c. .Início = 1 e fim = 2.
d. .Início = 0 e fim = 6.
e. .Início = 0 e fim = 8.
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.
a. .Função de hashing e resolução de colisões.
b. .Função hashing e tabela hashing.
c. . Hashing modular e Função de espelhamento.
d. .Colisões e tabela de dispersão.
e. . Nenhuma das alternativas.
Questão 10
Correto
Atingiu 1,00 de 1,00
A pesquisa binária é o algoritmo de pesquisa mais popular, eficiente e também uma das técnicas mais usadas para solucionar problemas.
A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o
paradigma de divisão e conquista.
 
 Assinale a alternativa correta para forma como os vetores devem estar para busca binária funcionar.
a. .Ordenados.
b. .Desordenados.
c. .Mesclados.
d. .Intercalados.
e. .Dispersos.