Prévia do material em texto
Atividade – 4 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO 1- 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. 2- 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. 3- 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 4- 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 monde o m = 10 2 24 75 16 5- 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. 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. 7- 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. 8- 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. 9- 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. 10- 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.