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

Prévia do material em texto

 Pergunta 1 
1 em 1 pontos 
 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 . 
Chave 
3 
75 
16 
24 
21 
 
 
Resto 
 
0 
1 
4 
? 
 
 
Adote: h(x) = x mod 
m onde o m = 5 
0 
1 
2 
3 
4 
5 
6 
 
75 
16 
 
 
24 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Resposta Selecionada: 
. 0. 
Resposta Correta: 
. 0. 
Comentário 
da resposta: 
Resposta correta. Adotando h(x) = x mod m, onde o 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. 
 
 
 Pergunta 2 
1 em 1 pontos 
 Ambas árvore B e B+ são árvores de auto-equilíbrio que possuem operações 
logarítmicas de inserção, localização e exclusão. 
 
Entre as configurações a seguir, quais alternativas condizem com as propriedades 
da árvore B? 
 
I. Uma árvore B é definida pelo termo grau mínimo t. O valor de t 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. 
 
Agora, assinale a alternativa que apresenta as propriedades da árvore B. 
Resposta Selecionada: 
I, II e III. 
Resposta Correta: 
I, II e III. 
Comentário 
da resposta: 
Resposta correta. As propriedades da árvore B é definida pelo 
termo grau mínimo t. O valor de t depende do tamanho do bloco 
de disco. Assim como, todos os ( nós) (incluindo raiz) podem 
conter no máximo 2t - 1 chaves e Todo nó do tipo folha possui a 
mesma profundidade entre eles e o ( nó) da raiz. 
 
 
 Pergunta 3 
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 4 
1 em 1 pontos 
 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. 
Resposta Selecionada: 
.Georgy Adelson Velsky e Evgenii Landis. 
Resposta Correta: 
.Georgy Adelson Velsky e Evgenii Landis. 
Comentário da 
resposta: 
Resposta correta. Em 1962, dois cientistas da computação 
soviéticos, Georgy Adelson Velsky e Evgenii Landis, mudaram para 
sempre o cenário das estruturas da Árvore de Pesquisa Binária. 
 
 
 Pergunta 5 
1 em 1 pontos 
 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: Vetor Ordenado 
Assinale a alternativa com a afirmativa corretas para o meio desse intervalo. 
 
Resposta Selecionada: 
.4. 
Resposta Correta: 
.4. 
Comentário da 
resposta: 
Resposta correta. meio = (posiçaoInicial + posicaoFinal) / 
2 
meio = (0 + 9) / 2 
meio = 4.5 (Pegar inteiro 4) vetor formado por números 
inteiros. 
 
 
 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 
 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. 
 
Resposta Selecionada: 
.Função de hashing e resolução de colisões. 
Resposta Correta: 
.Função de hashing e resolução de colisões. 
Comentário da 
resposta: 
Resposta correta. O hashing é uma técnica que usa uma função 
para transformar uma chave em um endereço. Já a colisão 
acontece quando a função hashing produz o mesmo 
endereçamento para chaves diferentes. 
 
 
 Pergunta 8 
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 9 
0 em 1 pontos 
 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 
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 
 
Agora, assinale a alternativa que apresenta os tipos de rotações usado para realizar o 
equilíbrio de uma árvore. 
 
Resposta Selecionada: 
II, III e IV. 
Resposta Correta: 
I, II, IV e V. 
Comentário 
da resposta: 
Sua resposta está incorreta. Existem basicamente 4 tipo de 
rotações, temos dois tipos primitivos de rotações e dois tipos 
compostos de rotações. Releia o e-book e procure sobre os tipo de 
rotações para responder corretamente à questão. 
 
 
 Pergunta 10 
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.