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

Prévia do material em texto

Pergunta 1
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 Correta: I, II e V
Pergunta 2
O hashing aberto tem a desvantagem de exigir ponteiros. Isso tende a desacelerar um pouco o
algoritmo por causa do tempo necessário para alocar novas células e também requer
essencialmente a implementação de uma segunda estrutura de dados.
Assinale a alternativa com o valor da posição para a chave 21 descrita na tabela abaixo, use a
técnica de hashing aberto .
Resposta Correta: .0.
Pergunta 3
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 .
Resposta Correta: .4.
Pergunta 4
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 Correta: I, II e V
Pergunta 5
Imagine esse vetor ordenado como a Figura abaixo, onde se pretende procurar o elemento 8, a
primeira coisa que o vetor irá fazer é descobrir a posição inicial, depois descobrir a posição final.
Vamos considerar a seguinte matriz:
1 2 3 4 5 6 7 8 9 10
Figura: Ve tor Ordenado
Assinale a alternativa com a afirmativa corretas para o meio desse intervalo.
Resposta Correta: .4.
Pergunta 6
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 Correta: Hashing aberto e hashing fechado
Pergunta 7
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 Correta: Ordenados
Pergunta 8
O reequilíbrio eficiente é a chave para fazer a Árvore AVL funcionar bem sem sacrificar o
desempenho. Para recuperar o equilíbrio de uma árvore AVL, realizaremos uma ou mais
rotações na árvore.
Entre as configurações a seguir, quais são os tipo de rotações usado para manter e quilí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
Agora, assinale a alternativa que apresenta os tipos de rotações usado para realizar o equilíbrio
de uma árvore.
Resposta Correta: I, II, IV e V
Pergunta 9
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.
Resposta Correta: (Q = R - L) onde R = número de níveis a direita e L = número de níveis a
esquerda
Pergunta 10
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 dadireita. 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 Correta: B(-2)