Avaliação de Estruturas de Dados: Árvores Rubro-Negra e 234

UENP Universidade Estadual do Norte do Paraná Campus Luiz Meneghel Centro de Ciências Tecnológicas Curso Ciência da Computação Prof Bruno Miguel Alunonº Avaliação 4 de Estrutura de Dados 1 15 Dado a árvore RubroNegra abaixo qualis movimentos é são necessários para que ela atenda as regras deste tipo de árvore Após alterações faça a inserção do número 4 e depois insira o número 3 realizando as operações necessárias Para os dois casos mostre a árvore resultante Indicando P Preto V Vermelho 2 25 Dado a árvore 234 a seguir responda as questões e mostre a árvore resultante das seguintes operações a 05 Quais são as regras para uma árvore 234 b 10 Inserção 56 21 22 e 95 c 10 Remoção 101 20 e 52 3 20 Em uma Universidade existe a necessidade de armazenamento de 252322 registros de alunos Sabendo que cada registro ocupa o espaço indicado na tabela a UENP Universidade Estadual do Norte do Paraná Campus Luiz Meneghel Centro de Ciências Tecnológicas seguir e que o Disco Rígido onde serão armazenados estes registros possui blocos de tamanho de 2KB 2048 Bytes Calcule mostre como você chegou nos resultados a 05 Utilizando o conceito de árvore multicaminhos qual seria o tamanho ideal de cada nó b 05 Quantos registros itens de dados e quantos ponteiros poderiam ser armazenados por nó c 05 Quantos blocos serão necessários para armazenar em disco os dados acima utilizando o tamanho ideal de cada nó d 05 Utilizando indexação pelo número de matrícula qual seria o tamanho ocupado em disco pela tabela de índices considerando que o endereço de um bloco ocupa 2 bytes Informação Tipo Tamanho Matrícula Long int 8 bytes Nome Char80 80 bytes Endereço Char120 120 bytes Curso Char60 60 bytes Telefone Char12 12 bytes TOTAL 280 bytes 4 20 Transforme a árvore não AVL a seguir em uma árvore AVL aplicando a regra do balanceamento e as rotações necessárias mostre as transformações para cada subárvore modificada e depois mostre a árvore toda balanceada 5 30 Sobre HASH responda a 05 Qual o objetivo de uma tabela HASH O que é uma função HASH b 05 Cite as vantagens e desvantagens de utilizar HASH em relação a outras estruturas de dados c 05 O que é uma Colisão Cite e explique pelo menos 3 estratégias de colisão em HASH UENP Universidade Estadual do Norte do Paraná Campus Luiz Meneghel Centro de Ciências Tecnológicas d 15 Dado os valores 2341 4234 2839 430 22 397 3920 e uma tabela hash de 7 posições onde a função HASH é hx x mod 7 mostre cada tabela hash resultante depois da inserção destes valores na ordem dada para cada tipo de estratégia de colisão uma tabela hash para cada tipo diferente de colisão Usando as estratégias de encademanto quadrático e hash duplo