DAS 5102
Fundamentos da Estrutura da Informação
Prof. Dr. rer. nat. Daniel D. Abdala
[email protected]
Lista para Complementação de Nota Relativa a P2
Considerações gerais para qualificar esta lista como valendo um ponto extra na p2:
•
•
•
Os programas devem ser tratados tal como um roteiro de laboratório. Eles devem ser
implementados em C e devem funcionar corretamente;
A lista pode ser resolvida em grupos de até quatro pessoas;
A lista deve ser entregue impressa até dia 03/11/2011.
1. Escreva uma função que verifica se duas listas dadas são iguais, ou melhor, se têm o
mesmo conteúdo. Faça duas versões: uma iterativa e uma recursiva;
2. Considere a representação pictográfica de uma estrutura de fila dinâmica dada abaixo:
Explique o problema em se utilizar esta estrutura. É possível implementar uma fila
usando este modelo? Justifique.
3. Crie uma função que receba uma árvore binária dinâmica como parâmetro e retorne o
número de folhas que se encontram no último nível e o número de folhas no
penúltimo nível.
4. Crie uma função que recebe uma fila de prioridade implementada usando listas
encadeadas ordenadas e retorne uma heap estática. Considere que os elementos da
fila de prioridade possuem dois campos além dos ponteiros necessários, chave e dado.
5. Com relação as operações increase_key() e decrease_key() que incrementam e
decrementam a chave do nó raiz de uma heap em uma unidade, respectivamente,
quais serão os passos necessários para garantir que a heap esteja consistente
(obedecendo as duas propriedades) apos a execução de cada uma destas funções.
Descreva o que pode acontecer graficamente (tal como no roteiro de heaps) e
implemente as duas funções.