FichaTrabalho2 ED2

Prévia do material em texto

Exercícios de preparação para a prova 
 
1. Uma expressão aritmética pode ser representada por uma árvore binária cujos nós 
externos (folhas) são associados com variáveis ou constantes e cujos nós internos são 
associados com operadores. Cada nó deste tipo de árvore tem um valor associado. Se o 
nó é externo, seu valor é o da sua variável ou constante; Se o nó é interno, então seu 
valor é definido aplicando-se sua operação sobre o valor de seus filhos. Seguindo a 
definição acima, encontre o valor da expressão aritmética da árvore binária da figura 
abaixo 
 
2. Suponha que tem-se números entre 1 e 1000 em uma árvore de busca binária e se quer 
procurar o número 363. Quais das seguintes sequências podem ser a sequência de nós 
examinados? a) 2,253,402,399,331,342,397,363 b) 926,201,911,242,912,246,363 c) 10, 
100, 1000, 500, 250, 300,363 d) 924,220,950,244,898,248,362,363 
 
3. Desenhe a árvore Trie que represente as seguintes chaves na árvore: “gnu” “emacs” 
“gpg” “else” “gnome” “go” “eps2eps” “expr” “exec” “google” “elif” “email” “exit” 
“epstopdf 
 
4. Considere uma trie (T) que represente um conjunto de strings. Para simplificar assuma 
que os caracteres são do alfabeto romano e a sua representação na árvore será 
codificada com números de 1 a 26. Segue abaixo um exemplo de uma implementação 
da estrutura em C: 
 
 
 
a. Explique o que faz a função abaixo. 
 
 
 
b. Implemente a função de busca de uma chave na trie, que retorne 1 em caso de 
sucesso e 0 no caso contrário. 
c. Escreva uma função que imprima todas as strings representadas na trie. 
 
 
 
5. Um sistema informático usa a Hash Table para guardar as senhas dos seus utilizadores. 
Suponha que tenha acesso a um ficheiro com a lista de user names e os valores da 
tabela hash correspondente as senhas e tenha também acesso a função de hash que foi 
usada para criar a tabela. Com esta informação conseguirá ter acesso as contas dos 
utilizadores? Explique. 
 
6. Considere uma implementação de de uma tabela Hash de tamanho M=11, com 
endereçamento aberto utilizando a função k mod M. 
a. Mostre a configuração da tabela após a inserção dos registos com as chaves: 4, 
17,13,35,25,11,2,10,32 
b. Mostre a tabela apos a remoção dos registos com as chaves 25,11 
c. Mostre a tabela apos a inserção dos registos com as chaves 40,3 
7. Explique o que é uma colisão em tabelas hash