1) Dadas as palavras abaixo, cire uma árvore Trie (graficamente) para armazená-las.

– roupa, rato, casa, castor, mesa, morro, gorro, galho.

2) Dê um exemplo de caso de uso de árvores Tries.

4) Qual é a característica principal de um Heap, em relação à ordem dos elementos?

5) Implemente uma função recursiva que um nodo N de uma árvore e que realize o procedimento de ajuste de heap (heapify).

6) Implemente a mesma função do exercício anterior, porém uma versão iterativa.

7) Explique o princípio do algoritmo HeapSort.

8) Explique o princípio básico de 3 métodos para tratar colisões em tabelas Hash. Porque colisões acontecem?

9) Cite duas características desejáveis quando definimos uma função Hash.

10) Explique o método de divisão, usado na criação de funções Hash. Cite um possível problema deste método.

11) Como o princípio de chave,valor pode ser utilisado para distribuição de processamento de grandes quantidades de dados? Dê um exemplo de aplicação real.

12) Dada a função de espalhamento h(k) = k mod 8. O 8 representa o número de blocos para armazenamento. Como esta função poderia ser modificada para melhorar o espalhamento? Explique o porquê.

13) Dada a tabela de frequencia de caracteres abaixo

Caracteres d e f g h j k l

Frequência 32 20 12 18 2 2 4 10

a) Crie uma árvore Trie para armezenar o código de Huffman correspondente.

b) Usando a codificação de (a), mostre o conjunto de caracteres da expressão ffgjeddk.

typedef struct tNo {
    char chave;             /* caracter */
    int freq;              /* frequencia */
    tNo *esq, *dir;
  } tNo;

16) Usando a estrutura de dados acima, implemente o algoritmo de criação da Trie com a codificação de Huffman. A função tNo extraiMinimo (tNo *no) pode ser usada. Esta retorna o menor elemento de uma fila de prioridades.

17) Crie um algoritmo para decodificar uma expressão de entrada que foi gerada a partir da árvore da questão 1. O conjunto de caracteres de entrada pode ser armazenado em um vetor de caracteres.

18) Considere a necessidade de implementar uma agenda telefônica, com o nome e telefone de contato. O número estimado de elementos nessa tabela será de 80 entradas. a) Implemente uma tabela hash para armazenar as entradas dessa agenda. b) Implemente uma função para incluir elementos nessa tabela. Inicialmente, considere que não haverão colisões. c) Implemente uma função para buscar elementos nessa tabela. Inicialmente, considere que não haverão colisões. d) Modifique a função da questão (b) para tratar colisões, usando o método e endereçamento direto, com sondagem linear. Implemente a função de busca correspondente.

19) Considere um conjunto de n chaves C formado pelos N primeiros múltiplos do número . Quantas colisoes seriam obtidas mediante a aplicação de cada uma das funçoes de hash que se seguem? Mostre como chegou nas suas respostas. a) x % 7 b) x % 14 c) x % 5

20) Ilustre a inclusão das chaves 5, 28, 19, 15, 20, 33, 12, 7 e 10 numa tabela hash onde colisões são tratadas por encadeamento. Considere a tabela com m = 9 posições e a função hash h(k) = k%m. Reconstrua a tabela para m = 13.