{"id":81,"date":"2017-06-22T17:15:27","date_gmt":"2017-06-22T20:15:27","guid":{"rendered":"http:\/\/web.inf.ufpr.br\/didonet2\/?page_id=81"},"modified":"2017-06-22T17:20:45","modified_gmt":"2017-06-22T20:20:45","slug":"exerciciosthh","status":"publish","type":"page","link":"https:\/\/web.inf.ufpr.br\/didonet\/teaching-disciplinas\/exerciciosthh\/","title":{"rendered":"Exerc\u00edcios Trie Heap Hash"},"content":{"rendered":"

1<\/b>)<\/b> Dadas as palavras abaixo, cire uma \u00e1rvore Trie (graficamente) para armazen\u00e1-las.<\/span><\/p>\n

– roupa, rato, casa, castor, mesa, morro, gorro, galho.<\/span><\/p>\n

2<\/b>) <\/b>D\u00ea um exemplo de caso de uso de \u00e1rvores Tries.<\/span><\/p>\n

4<\/b>) <\/b>Qual \u00e9 a caracter\u00edstica principal de um Heap, em rela\u00e7\u00e3o \u00e0 ordem dos elementos?<\/span><\/p>\n

5<\/b>) <\/b>Implemente uma fun\u00e7\u00e3o recursiva que um nodo N de uma \u00e1rvore e que realize o procedimento de ajuste de heap (heapify<\/b>).<\/span><\/p>\n

6<\/b>)<\/b> Implemente a mesma fun\u00e7\u00e3o do exerc\u00edcio anterior, por\u00e9m uma vers\u00e3o iterativa.<\/span><\/p>\n

7<\/b>)<\/b> Explique o princ\u00edpio do algoritmo HeapSort.<\/span><\/p>\n

8<\/b>) Explique o princ\u00edpio b\u00e1sico de 3 m\u00e9todos para tratar colis\u00f5es em tabelas Hash. Porque colis\u00f5es acontecem?<\/span><\/p>\n

9<\/b>)<\/b> Cite duas caracter\u00edsticas desej\u00e1veis quando definimos uma fun\u00e7\u00e3o Hash.<\/span><\/p>\n

1<\/b>0<\/b>)<\/b> Explique o m\u00e9todo de divis\u00e3o, usado na cria\u00e7\u00e3o de fun\u00e7\u00f5es Hash. Cite um poss\u00edvel problema deste m\u00e9todo.<\/span><\/p>\n

1<\/b>1<\/b>)<\/b> Como o princ\u00edpio de chave,valor pode ser utilisado para distribui\u00e7\u00e3o de processamento de grandes quantidades de dados? D\u00ea um exemplo de aplica\u00e7\u00e3o real.<\/span><\/p>\n

1<\/b>2<\/b>)<\/b> Dada a fun\u00e7\u00e3o de espalhamento h(k) = k mod 8. O 8 representa o n\u00famero de blocos para armazenamento. Como esta fun\u00e7\u00e3o poderia ser modificada para melhorar o espalhamento? Explique o porqu\u00ea.<\/span><\/p>\n

1<\/span><\/b>3<\/b>) <\/b>Dada a tabela de frequencia de caracteres abaixo<\/span><\/span><\/p>\n

Caracteres <\/span><\/b>d e f g h j k l<\/span><\/span><\/p>\n

F<\/span><\/b>req<\/b>u\u00eancia<\/b> <\/b>32<\/b> <\/b>20<\/b> 12 1<\/b>8<\/b> <\/b>2<\/b> <\/b>2 4 10<\/b><\/span><\/span><\/p>\n

a) Crie uma \u00e1rvore Trie para armezenar o c\u00f3digo de Huffman correspondente.<\/span><\/p>\n

b) Usando a codifica\u00e7\u00e3o de (a), mostre o conjunto de caracteres da express\u00e3o ffgjeddk.<\/span><\/p>\n

typedef struct tNo {<\/span>\r\n    char chave;             \/* caracter *\/<\/span>\r\n    int freq;              \/* frequencia *\/<\/span>\r\n    tNo *esq, *dir;<\/span>\r\n  } tNo;<\/span><\/span><\/pre>\n
1<\/b>6<\/b>)<\/b> Usando a estrutura de dados acima, implemente o algoritmo de cria\u00e7\u00e3o da Trie com a codifica\u00e7\u00e3o de Huffman. A fun\u00e7\u00e3o tNo extraiMinimo (tNo *no)<\/i> pode ser usada. Esta retorna o menor elemento de uma fila de prioridades.<\/span><\/p>\n
17) <\/b>Crie um algoritmo para decodificar uma express\u00e3o de entrada que foi gerada a partir da \u00e1rvore da quest\u00e3o 1. O conjunto de caracteres de entrada pode ser armazenado em um vetor de caracteres. <\/span><\/p>\n
18) <\/b>Considere a necessidade de implementar uma agenda telef\u00f4nica, com o nome e telefone de contato. O n\u00famero estimado de elementos nessa tabela ser\u00e1 de 80 entradas. a) Implemente uma tabela hash para armazenar as entradas dessa agenda. b) Implemente uma fun\u00e7\u00e3o para incluir elementos nessa tabela. Inicialmente, considere que n\u00e3o haver\u00e3o colis\u00f5es. c) Implemente uma fun\u00e7\u00e3o para buscar elementos nessa tabela. Inicialmente, considere que n\u00e3o haver\u00e3o colis\u00f5es. d) Modifique a fun\u00e7\u00e3o da quest\u00e3o (b) para tratar colis\u00f5es, usando o m\u00e9todo e endere\u00e7amento direto, com sondagem linear. Implemente a fun\u00e7\u00e3o de busca correspondente. <\/span><\/p>\n
19) <\/b>Considere um conjunto de n chaves C formado pelos N primeiros m\u00faltiplos do n\u00famero . Quantas colisoes seriam obtidas mediante a aplica\u00e7\u00e3o de cada uma das fun\u00e7oes de hash que se seguem? Mostre como chegou nas suas respostas. a) x % 7 b) x % 14 c) x % 5 <\/span><\/p>\n
20) <\/b>Ilustre a inclus\u00e3o das chaves 5, 28, 19, 15, 20, 33, 12, 7 e 10 numa tabela hash onde colis\u00f5es s\u00e3o tratadas por encadeamento. Considere a tabela com m = 9 posi\u00e7\u00f5es e a fun\u00e7\u00e3o hash h(k) = k%m. Reconstrua a tabela para m = 13.<\/span><\/p>\n
\u00a0<\/span><\/span><\/span><\/span><\/pre>\n","protected":false},"excerpt":{"rendered":"
1) Dadas as palavras abaixo, cire uma \u00e1rvore Trie (graficamente) para armazen\u00e1-las. – roupa, rato, casa, castor, mesa, morro, gorro, galho. 2) D\u00ea um exemplo de caso de uso de \u00e1rvores Tries. 4) Qual \u00e9 a caracter\u00edstica principal de um Heap, em rela\u00e7\u00e3o \u00e0 ordem dos elementos? 5) Implemente uma fun\u00e7\u00e3o recursiva que um nodo…<\/p>\n","protected":false},"author":21,"featured_media":0,"parent":31,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-81","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/81","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/comments?post=81"}],"version-history":[{"count":4,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/81\/revisions"}],"predecessor-version":[{"id":88,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/81\/revisions\/88"}],"up":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/31"}],"wp:attachment":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/media?parent=81"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}