GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO GR2409202 - 202020 ATIV 4

Prévia do material em texto

15/09/2020 Blackboard Learn
https://fmu.blackboard.com/webapps/late-Course_Landing_Page_Course_100-BBLEARN/Controller# 1/4
Curso GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO GR2409202 -
202020.ead-29774993.06
Teste ATIVIDADE 4 (A4)
Iniciado 15/09/20 19:18
Enviado 15/09/20 19:50
Status Completada
Resultado da
tentativa
10 em 10 pontos 
Tempo decorrido 31 minutos
Resultados
exibidos
Respostas enviadas, Respostas corretas, Comentários
Pergunta 1
Resposta Selecionada: 
Resposta Correta: 
Feedback
da
resposta:
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.
.Ordenados.
.Ordenados.
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.
Pergunta 2
Resposta Selecionada: 
Resposta Correta: 
Feedback
da
resposta:
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.
.Busca sequencial e busca binária.
.Busca sequencial e busca binária.
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 3
Resposta Selecionada:
 
Resposta Correta:
 
Feedback
da
resposta:
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.
.( Q = R - L), onde R = número de níveis a direita e L 
= número de níveis a esquerda.
.(Q = R - L), onde R = número de níveis a direita e L
= número de níveis a esquerda.
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.
1 em 1 pontos
1 em 1 pontos
1 em 1 pontos
15/09/2020 Blackboard Learn
https://fmu.blackboard.com/webapps/late-Course_Landing_Page_Course_100-BBLEARN/Controller# 2/4
Pergunta 4
Resposta Selecionada: 
Resposta Correta: 
Feedback
da
resposta:
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 aleatoriament
e. 
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.
I, II e V.
I, II e V.
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 5
Resposta Selecionada: 
Resposta Correta: 
Feedback da
resposta:
Formalmente, definimos uma Árvore B + pelos valores M e L, onde M é igual ao número máximo de
filhos que um determinado nó pode ter e L é igual ao número máximo de registros de dados
armazenados em um nó folha.
 
Uma árvore B + da ordem M é uma árvore que satisfaz uma das propriedade abaixo, assinale qual.
.Cada nó tem no máximo M filhos.
.Cada nó tem no máximo M filhos.
Resposta correta. Uma árvore B+ da ordem M é uma árvore que cada nó tem no
máximo M filhos.
Pergunta 6
Resposta Selecionada: 
Resposta Correta: 
Feedback
da
resposta:
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.
.Georgy Adelson Velsky e Evgenii Landis.
.Georgy Adelson Velsky e Evgenii Landis.
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.
1 em 1 pontos
1 em 1 pontos
1 em 1 pontos
15/09/2020 Blackboard Learn
https://fmu.blackboard.com/webapps/late-Course_Landing_Page_Course_100-BBLEARN/Controller# 3/4
Pergunta 7
Resposta Selecionada: 
Resposta Correta: 
Feedback
da
resposta:
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.
I, II e V.
I, II e V.
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 8
Resposta Selecionada: 
Resposta Correta: 
Feedback
da
resposta:
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.
I, II e III.
I, II e III.
Resposta correta. As propriedades da árvore B é definida pelo termo grau mínimo t. O
valor de tdepende do tamanho do bloco de disco. Assim como, todos os ( nós) (incluindoraiz) 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 9
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
Resto
?
5
Adote: h(x) = x mod m onde o
m = 10 
 
 
 
0
1
2
1 em 1 pontos
1 em 1 pontos
1 em 1 pontos
15/09/2020 Blackboard Learn
https://fmu.blackboard.com/webapps/late-Course_Landing_Page_Course_100-BBLEARN/Controller# 4/4
Terça-feira, 15 de Setembro de 2020 19h50min36s BRT
Resposta Selecionada: 
Resposta Correta: 
Feedback
da
resposta:
16
24
 
 
6
4
 
 
2
24
75
16
3
4
5
6
 
. 0.
. 0.
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 10
Resposta Selecionada: 
Resposta Correta: 
Feedback
da
resposta:
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.
.AVL e B+.
.AVL e B+.
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.
1 em 1 pontos