Ead ii

MC202 Estrutura de Dados Lista 2 1. Considerea existˆncia de um tipo abstrato Pilha de n´ meros reais, cuja e u interface est´ definida no arquivo pilha.h da seguinte forma: a typedef struct pilha Pilha Pilha* pilha_cria(void) Pilha pilha_empilha(Pilha* p, float v) float pilha_desempilha(Pilha* p) int pilha_vazia( Pilha* p) void pilha_libera(Pilha* p) Sem conhecer a representa¸˜o interna desse tipo abstrato e de posse ca apenas das fun¸˜es declaradas no arquivo de interface: co • Implemente uma fun¸˜o que receba uma pilha como parˆmetro e ca a retorne o valor armazenado em seu topo, restaurando o conte´do u da pilha. Essa fun¸˜o deve obedecer ao prot´tipo: ca o float topo(Pilha* p); • Implemente uma fun¸˜o que receba duas pilhas, p1 e p2 , e passe ca todos os elementos da pilha p2 para o topo da pilha p1 . Note que, ao final dessa fun¸˜o, a pilha p2 vai estar vazia, e a pilha p1 conter´ ca a todos os elementos das duas pilhas. Essa fun¸˜o deve obedecer ao ca prot´tipo: void concatenaPilhas(Pilha* p1 , Pilha* p2 ); o 2. Mostre como uma pilha pode ser implementada usando duas filas. 3. Considere estruturas de ´rvores bin´rias que armazenam valores inteia a ros e implemente as seguintes fun¸˜es: co • devolver a quantidade de n´s que guardam n´ meros pares. (int o u pares (ArvBin* a);) • devolver o valor do m´ximo conte´ do de um n´ da ´rvore. a u o a • devolver a altura da ´rvore. a • listar o conte´ do dos n´s da ´rvore em pr´-ordem. u o a e • devolver a quantidade de folhas da ´rvore. a 1

4. Desenhe a ´rvore bin´ria que tem os percursos descritos abaixo. a a Pr´-ordem: C E A D H K J B M F L G I e In-ordem: DAKHECBJLFMGI

5. (a) Desenhe a seguinte ´rrvore bin´ria dada em nota¸˜o textual: a a ca (A (B (D () (G () () ))) (C (F()()) ())) (b) Desenhe a anterior ´rvore bin´ria com fios a a 6. Escreva uma fun¸˜o n˜o-recursiva para implementar um percurso em ca a in-ordem (sem pilha) em ´rvores bin´rias com fios. a a 7. Considerando os algoritmos vistos em sala de aula,