Baixe o app para aproveitar ainda mais
Prévia do material em texto
GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO PTA - 202010.ead-29770911.06 · Pergunta 1 1 em 1 pontos 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. Resposta Selecionada: .Cada nó tem no máximo M filhos. Resposta Correta: .Cada nó tem no máximo M filhos. Feedback da resposta: Resposta correta. Uma árvore B+ da ordem M é uma árvore que cada nó tem no máximo M filhos. · Pergunta 2 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. Feedback 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 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. Feedback 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 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 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. Feedback 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 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. Feedback 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 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. Feedback 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 7 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. Feedback 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 8 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 a base até chegar ao início (VIANA, Gerardo Valdisio Rodrigues; CINTRA, Glauber Ferreira; NOBRE; Ricardo Holanda. Pesquisa e ordenação de Dados. 2 edição. EdeuECE, 2015.). Assinale a alternativa que diz respeito a uma árvore de busca balanceada. Resposta Selecionada: . AVL. Resposta Correta: . AVL. Feedback 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, e adicionar essas regras a métodos para se manter o equilíbrio da árvore. · Pergunta 9 1 em 1 pontos 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 Resposta Selecionada: .Início = 0 e fim = 9. Resposta Correta: .Início = 0 e fim = 9. Feedback da resposta: Resposta correta. O início do intervalo é definido como Low = 0, e o fim do intervalo é definidocomo High = n-1, ou seja, High = 10-1 = 9. · Pergunta 10 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. Feedback 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. Quinta-feira, 16 de Abril de 2020 21h56min08s BRT
Compartilhar