PESQUISA ATV4

Prévia do material em texto

Curso PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO 
Teste ATIVIDADE 4 (A4) 
Resultado da tentativa 10 em 10 pontos 
 
 
 
 
 Pergunta 1 
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. 
 
 
 Pergunta 2 
1 em 1 pontos 
 
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 Selecionada: 
I, II e V. 
Resposta Correta: 
I, II e V. 
Comentário da 
resposta: 
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. 
 
 
 Pergunta 3 
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 4 
1 em 1 pontos 
 
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. 
 
Resposta Selecionada: 
.Busca sequencial e busca binária. 
Resposta Correta: 
.Busca sequencial e busca binária. 
Comentário da 
resposta: 
Resposta correta. Para realizar essa busca por valor temos duas maneiras 
ou realizamos uma busca sequencial ou uma busca binária. 
A busca sequencial ela percorre todas as posições do vetor verificando uma 
a uma até achar o valor desejado ou simplesmente chegou ao final sem 
achá-lo, já na busca binária é dividido o vetor ao meio e a busca é realizada 
apenas em uma das metades. 
 
 
 Pergunta 5 
1 em 1 pontos 
 
O hashing fechado, também conhecido como endereçamento aberto, é uma alternativa para 
resolver colisões com listas vinculadas. Em um sistema de hashing fechado, se ocorrer uma 
colisão, células alternativas são tentadas até que uma célula vazia seja encontrada. 
 
Assinale a alternativa com o valor da posição para a chave 3 descrita na tabela abaixo, use a 
técnica de hashing fechado . 
 
Chave 
3 
75 
16 
24 
 
 
 
Resto 
? 
5 
6 
4 
 
 
 
Adote: h(x) = x mod m onde 
o m = 10 
 
 
 
2 
24 
75 
16 
 
0 
1 
2 
3 
4 
5 
6 
 
 
 
 
Resposta Selecionada: 
. 0. 
Resposta Correta: 
. 0. 
Comentário da 
resposta: 
Resposta correta. Adotando h(x) = x mod m, onde o m = 10, temos h(3) = 3 
mod 10 = 3. Como a posição 3 encontra-se ocupada, procura-se a próxima 
posição disponível para que o 3 
seja alocando, portanto a próxima posição livre é a posição 0. 
 
 
 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 da base até 
chegar ao início. Vários algoritmos foram desenvolvidos para a construção de árvores de 
busca que permanecem equilibradas (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 dois tipos de árvores de busca. 
 
Resposta Selecionada: 
.AVL e B+. 
Resposta Correta: 
.AVL e B+. 
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. As árvores B 
e B+ são formas de árvore de pesquisa equilibrada baseada em árvores 
gerais. 
 
 
 Pergunta 7 
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 8 
1 em 1 pontos 
 
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 Selecionada: 
.Hashing aberto e hashing fechado. 
Resposta Correta: 
.Hashing aberto e hashing fechado. 
Comentário da 
resposta: 
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. 
 
 
 Pergunta 9 
1 em 1 pontos 
 
Uma vez detectado o desequilíbriona á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 Selecionada: 
.( Q = R - L), onde R = número de níveis a direita e L 
= número de níveis a esquerda. 
Resposta Correta: 
.(Q = R - L), onde R = número de níveis a direita e L 
= número de níveis a esquerda. 
Comentário da 
resposta: 
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. 
 
 
 Pergunta 10 
1 em 1 pontos 
 
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. 
 
Resposta Selecionada: 
.Ordenados. 
Resposta Correta: 
.Ordenados. 
Comentário da 
resposta: 
Resposta correta. A busca binária só funciona em vetores que estejam de 
forma ordenados, ela divide o vetor ao meio e procura apenas em uma das 
metades, ou seja, o algoritmo é executado até encontrar o valor ou posição.