Esta lista deve ajuda-lo na preparação para o primeiro exercício escolar.
Esta lista é individual. Em caso de cópia será atribuída a nota 0 (zero) a todas as listas idênticas.
Todas as implementações devem ser feitas em C, o codigo
fonte disponibilizado em disquete, devidamente documentado, que possa ser executado pelos monitores.
Cada dia de atraso implica em 0,5 ponto a menos na nota desta lista.
A solução deve ser entregue durante a aula ou em
horario de monitoria.
Esta lista contem 3 questões.
Escrever um procedimento para, dado um conjunto de
inteiros, inserir eles em uma árvore binária de busca
(implementada com apontadores). Após isso, você deve
identificar o "fator de equilíbrio" de cada nó. O "fator de
equilíbrio" é um inteiro (positivo ou negativo) que indica a
diferença entre as alturas das sub-árvores à esquerda e à direita do vértice. Note que este deve ser um procedimento recursivo, onde a informação é passada bottom-up, ou seja, de baixo para cima. A base da recursão está nas folhas, onde as soluções são triviais. (4.0)
Quando discutimos as Arvores Binarias de Busca (ou de Pesquisa), vimos em detalhes na aula a implementaçao das funçoes ELEMENTO e INSERIR. Com base nessa discussao, implemente um programa para representar um conjunto ordenado segundo uma Arvore Binaria de Pesquisa. As funçoes ELEMENTO e INSERIR ja estao praticamente implementadas, faltando apenas a implementaçao das funçoes MIN e SUPRIMIR. O programa devera ser testado com uma lista de dados fornecida pelos monitores. (3.0)
Quando discutimos o TDA Dicionario implementado segundo a tecnica de endereçamento dispersado, vimos em detalhes a abordagem aberta. Com base na implementaçao para as funçoes ZERAR, ELEMENTO e INSERIR, mostradas em aula, faça um programa que implemente o TDA Dicionario segundo a tecnica de endereçamento dispersado aberta. As funçoes ZERAR, ELEMENTO e INSERIR ja estao praticamente implementadas, faltando apenas a implementaçao da funçao SUPRIMIR. O programa devera ser testado com uma lista de dados fornecida pelos monitores. (3.0)