Instituto de Matematica e Estatıstica - USP

MAC2014 - Laboratorio de ProgramacaoEngenharia de Computacao

Prova unica - 4/2015 - Parte 2 - Casa

Assinando esta prova, declaro que fiz a prova individualmente

e estou ciente que a consequencia caso tenha quebrado este

cırculo de confianca e ser reprovado na disciplina.

Nome :

Assinatura :

Questao Valor Nota

Q1 15

Q2 15

Q3 15

Q4 20

total 65

1. Os codigos das funcoes devem ser entregues em arquivos separados .c, todos nomesmo projeto. Uma funcao main deve ser feita para chama-los.

2. Apenas os codigos das funcoes devem ser copiados no texto da prova (pode ser umarquivo .txt, ou .doc, ou .pdf, ou .tex).

3. As funcoes devem ser endentadas corretamente.

4. Empacote tudo num arquivo .zip e faca o upload no paca.

5. E permitido a consulta a livros, apontamentos ou Internet.

6. Nao e permitida a consulta a colegas, amigos, famılia, cachorro, papagaio e etc.

7. Duracao da prova: 7 dias.

Boa prova !

Rua do Matao, 1010 - Sao Paulo - SP

Q1. Uma arvore de recursao e um diagrama em formato de arvore que esquematiza achamada recursiva de uma funcao. Ela tem como raiz a chamada original da funcao,como vertices as chamadas recursivas da funcao (passo da recursao) e como folhasos valores ja fixados da base da recursao. Por exemplo, a figura abaixo e a arvorede recursao da seguinte funcao quando n = 2:

f(n) =

n if n ≤ 1;n + f(1

2n) if n is even, n > 1;

f(12(n + 1)) + f(1

2(n− 1)) if n is odd, n > 1.

(1)

f(2)

f(1)2

1

A. Desenhe as arvores de recursao para n = 5 e n = 6.

B. Escreva a versao recursiva e a versao iterativa de f .

C. Baseado no que voce aprendeu sobre arvores balanceadas, discuta a relacaoentre a forma de implementacao da funcao recursiva e sua eficiencia.

Q2. Baseado no texto sobre interfaces colocado no Grauna e nas diversas interfacesapresentadas em aula para as estruturas de dados, responda:

A. defina o que e interface, suas caracterısticas e usos.

B. escreva uma interface para um verificador ortografico. Para cada funcao dainterface, escreva a funcionalidade, a assinatura, especifique as entradas e assaıdas. Voce nao precisa implementar a interface.

Q3. Escreva as funcoes abaixo usando as interfaces apresentadas em aula.

A. Usando apenas a interface de fila implementada em uma lista circular (aula7), escreva uma funcao que mova o objeto com maior conteudo para o inıcioda fila e o objeto de menor conteudo para o fim da fila.

B. Usando apenas as interface de fila e de pilha das aulas 5 e 6, escreva umafuncao que inverta uma fila e outra funcao que inverta uma pilha.

Q4. Escreva uma funcao que converte uma arvore binaria em uma lista duplamenteligada onde os nos sao colocados na lista em ordem transversal de varredura inorder.Ao final da funcao, o apontador para a raiz deve apontar para o no mais a esquerdada lista duplamente ligada. Os ponteiros a direita e a esquerda devem ser usadospara mover-se ao longo da lista e ser NULL nas extremidades da lista.