\input acentos
\hyphenpenalty=500
\tolerance=500
\overfullrule=0pt
\catcode`@=11 % borrow the private macros of PLAIN (with care)
% (now Appendix E resumes again)
% macros for verbatim scanning
\chardef\other=12
\def\ttverbatim{\begingroup
  \catcode`\\=\other
  \catcode`\{=\other
  \catcode`\}=\other
  \catcode`\$=\other
  \catcode`\&=\other
  \catcode`\#=\other
  \catcode`\%=\other
  \catcode`\~=\other
  \catcode`\_=\other
  \catcode`\^=\other
  \obeyspaces \obeylines \tt}

\outer\def\begintt{$$\let\par=\endgraf \ttverbatim \parskip=\z@
  \catcode`\|=0 \rightskip-5pc \ttfinish}
{\catcode`\|=0 |catcode`|\=\other % | is temporary escape character
  |obeylines % end of line is active
  |obeyspaces|global|let =| % spaces are active
  |gdef|ttfinish#1^^M#2\endtt{#1|vbox{#2}|endgroup$$}}

\centerline{MAC324\hfill\bf EXERCÍCIOS\hfill\sl24/4/99}
\bigskip

\medskip
\noindent{\bf Obs.}\enspace 
Nos exercícios com listas ligadas, vamos assumir que temos
\begintt
  typedef struct node *link;
  struct node { Item item; link next; }
\endtt

\medskip
\noindent{\bf 1.}\enspace
Neste exercício, assuma que implementamos listas ligadas sem cabeça e
sem cauda de lista.  Escreva uma função de protótipo 
\begintt
  link reverta(link h);
\endtt
que recebe um ponteiro para o primeito elemento de uma lista ({\tt
NULL} caso esta lista seja vazia) e devolve um ponteiro para o
primeiro elemento da {\it reversão\/} da lista dada, isto é, uma lista
com exatamente os mesmos elementos da lista original, mas com os
elementos em ordem reversa.  Aqui, você deve apenas alterar os
ponteiros dos elementos da lista para conseguir este objetivo; você
não deve alocar mais memória para produzir a lista nova.

\medskip
\noindent{\bf 2.}\enspace
Suponha neste exercício que as nossas listas estão implementadas com
cabeças de listas (em particular, a lista `vazia' contém exatamente um
elemento, a saber, a cabeça de lista).  Ademais, assuma que {\tt Item}
é o tipo {\tt int}.  Escreva uma função de protótipo 
\begintt
  link acerte_prim_el(link h);
\endtt
que recebe um ponteiro para o começo de uma lista e reorganiza os
elementos desta lista de forma que o elemento com a menor chave (isto
é, com o menor campo {\tt item}) é o primeiro elemento da lista nova.
A sua função deve devolver um ponteiro para o começo da nova lista.

\medskip
\noindent{\bf 3.}\enspace
Escreva uma função de protótipo
\begintt
  link ordene(link h);
\endtt
que ordena os elementos de uma lista em ordem crescente das chaves
(isto é, campo {\tt item}, que assumimos serem inteiros).  Use a
função do exercício anterior.  Tanto a lista original como a lista
resultante devem ter cabeças de lista.

\medskip
\noindent{\bf 4.} [3.36 do Sedgewick]\enspace
Escreva uma função que rearranja os elementos de uma lista dada, pondo
todos os elementos que ocorrem nas posições pares antes de todos os
elementos de ocorrem nas posições ímpares.  Você deve preservar a
ordem relativa dos elementos pares entre si, e a ordem relativa dos
elementos ímpares entre si.

\medskip
\noindent{\bf 5.} [3.38 do Sedgewick]\enspace
Escreva uma função de protótipo
\begintt
  link copia(link h);
\endtt
que recebe um ponteiro para o começo de uma lista e devolve um
ponteiro para uma nova lista, que é uma cópia da lista dada.  A nova
lista deve conter uma cópia de cada elemento da lista original; estas
cópias devem ocorrer `na mesma ordem' que na lista original.

\medskip
\noindent{\bf 6.}\enspace
Assuma que pomos
\begintt
  typedef struct { float Re; float Im; } *Complex;
\endtt
Escreva uma função de protótipo
\begintt
  Complex COMPLEXmult(Complex z, Complex w);
\endtt
que devolve (um ponteiro) para o produto de {\tt z} e {\tt w}.  

\medskip
\noindent{\bf 7.}\enspace
Suponha novamente que temos definido o tipo {\tt Complex}.  Suponha
também que temos listas ligadas com {\tt Item} definido como {\tt
Complex}.  Escreva uma função de protótipo
\begintt
  Complex COMPLEXsum(link h);
\endtt
que recebe uma lista ligada representando uma seqüência de números
complexos, e que devolve a soma desta lista de números complexos.
Assuma que a lista não tem nem cabeça nem cauda de lista.

\medskip
\noindent{\bf 8.} [4.6 do Sedgewick]\enspace
Este é um exercício sobre pilhas.  Na seqüência
\begintt
E A S * Y * Q U E * * * S T * * * I O * N * * *  
\endtt
uma letra significa {\it empilhe\/} e um asterisco {\it desempilhe}.
Qual é a seqüência de letras devolvida pelos {\it desempilhe\/}? 

\medskip
\noindent{\bf 9.} [4.7 do Sedgewick]\enspace
Continuemos usando a notação do exercício anterior.  Diga como devemos
inserir asteriscos na seqüência {\tt E A S Y} para que os {\it
desempilhe\/} devolva as seguintes seqüências: ({\it i\/}) {\tt E A S
Y}, ({\it ii\/}) {\tt Y S A E}, ({\it iii\/}) {\tt A S Y E}, ({\it
iv\/}) {\tt A Y S E}, ({\it v\/}) {\tt E Y A S}.  Note que nem sempre
podemos obter a saída desejada; nestes casos, argumente por que a dada
saída não pode ser obtida desta forma.

\medskip
\noindent{\bf 10.} [4.9 do Sedgewick]\enspace
Converta a expressão
\begintt
( 5 * ( ( 9 * 8 ) + ( 7 * ( 4 + 6 ) ) ) )
\endtt
para a notação pósfixa e para a notação infixa.

\medskip
\noindent{\bf 11.} [4.31 do Sedgewick]\enspace
Este é um exercício sobre filas.  Na seqüência
\begintt
E A S * Y * Q U E * * * S T * * * I O * N * * * 
\endtt
uma letra significa inserção no fim da fila e um asterisco significa
remoção do começo da fila.  Qual é a seqüência de letras devolvida
por esta seqüência de operações em nossa fila?

\medskip
\noindent{\bf 12.} [O problema das panquecas]\enspace
Suponha que temos, por exemplo, a seqüencia de números
\begintt
  8 2 3 5 1 4 9 7 6 0
\endtt
Imagine que esta seqüência indica uma pilha de panquecas de 10
tamanhos distintos, empilhadas de forma que a menor está no fundo da
pilha, a maior é a quarta panqueca a partir do fundo da pilha, a
segunda maior está no topo, etc.  As únicas operações permitidas são
inverter um segmento inicial desta seqüência.  Portanto, existem 9
operações não-triviais para a pilha acima; uma delas produz, por
exemplo,
\begintt
  5 3 2 8 1 4 9 7 6 0
\endtt
Podemos chamar esta operação deste exemplo de `operação número 4', já
que invertemos a ordem das 4 panquecas do topo.  O problema é o
seguinte: dados um inteiro positivo {\tt n} e uma permutação dos
inteiros não-negativos menores do que {\tt n}, determinar uma
seqüência de operações (permitidas) que resultam na seqüência
\begintt
  0 1 2 ... n - 1
\endtt
Isto é, com as panquecas em ordem crescente, do topo para o fundo.
Escreva uma função de protótipo 
\begintt
  void imprima_solucao(int n, int panq[]);
\endtt
para resolver este problema.

\medskip
\noindent{\bf 13.} [5.11 do Sedgewick]\enspace
Escreva um programa recursivo que converte uma expressão em notação
infixa em notação pósfixa.

\medskip
\noindent{\bf 14.} [5.14 do Sedgewick]\enspace
Escreva uma função recursiva que remove o último elemento de uma lista
ligada. 

\medskip
\noindent{\bf 15.} [5.17 do Sedgewick]\enspace
Escreva uma função recursiva de protótipo
\begintt
  Item max_el(link h);
\endtt
que recebe um ponteiro para o começo de uma lista ligada (sem cabeça e
sem cauda) e que devolve a maior chave (isto é, campo {\tt item})
presente na lista, onde assumimos que {\tt Item} é o tipo {\tt int}. 

\medskip
\noindent{\bf 16.} [5.48 do Sedgewick]\enspace
Determine o conteúdo dos vetores {\tt maxKnown[]} e {\tt itemKnown[]}
que são determinados pelo programa 5.13 (prog5.13.c da página) na
chamada {\tt knap(17)}, com os itens 
\begintt
        0   1   2   3   4
item    A   B   C   D   E
size    3   4   7   8   9
valor   4   5  10  11  13  
\endtt   

\medskip
\noindent{\bf 17.} [5.55 do Sedgewick]\enspace
Lembre que os coeficientes binomiais satisfazem a recorrência
$$
{N\choose k}={N-1\choose k}+{N-1\choose k-1}
$$
para todo~$k\geq1$ e todo~$N$.  Ademais, temos ${N\choose0}={N\choose
N}=1$.  Escreva uma função recursiva de protótipo
\begintt
  long binom(long N, long k);
\endtt
que calcula $N\choose k$.  Use programação dinâmica.  Verifique
experimentalmente a diferença de eficiência entre as implementações
sem e com programação dinâmica.  

\medskip
\noindent{\bf 18.} [5.62 do Sedgewick]\enspace
Existe uma correspondência entre árvores binárias e certas seqüências
de bits.  Para uma seqüência de bits corresponder a uma AB, devemos ter
que o número de {\tt 0}s excede de um o número de {\tt 1}s e ainda
vale que, lendo a seqüência da esquerda para a direita, o número de
{\tt 0}s nunca excede o número de {\tt 1}s.  Estas seqüências (que
chamaremos de {\it válidas\/}) também podem ser caracterizadas da
seguinte forma: a seqüência com um único bit {\tt 0} é valida; se
duas seqüências são válidas então a concatenação delas, antecedida por
um bit {\tt 1}, é válida.

Desenhe a AB que corresponde à seqüência válida
\begintt
  1 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 0 0
\endtt

\medskip
\noindent{\bf 19.} [5.63 do Sedgewick, variante]\enspace
ABs são equivalentes a seqüências bem-formadas de parênteses.  Note
que seqüências bem-formadas de parênteses podem ser definidas desta
forma: a seqüência {\tt ( )} é bem-formada.  Se duas seqüências {\tt
s} e {\tt t} são bem-formadas, então {\tt ( s t )} é bem formada.  

Desenhe a AB que corresponde à seqüência
\begintt
  ( ( ( ( ) ( ( ) ( ) ) ) ( ( ( ) ( ) ) ( ) ) ) ( ) )
\endtt

\medskip
\noindent{\bf 20.} [5.79 do Sedgewick]\enspace
Suponha que percorremos as árvores abaixo em pré-ordem, in-ordem, 
pós-ordem, e por níveis, imprimindo o conteúdo dos nós.  Quais são as
seqüências de caracteres assim obtidas?
\begintt
(i)  D           (ii)  C           (iii)  E            
       B                 B                  C          
         A                 A                  B        
           N                 N                  A      
           N                 N                    N    
         C                 N                      N    
           N             D                      N      
           N               N                  D        
       F                   E                    N      
         E                   N                  N      
           N                 N              H          
           N                                  F        
         G                                      N      
           N                                    G      
           N                                      N    
                                                  N    
                                              I        
                                                N      
                                                N      
\endtt

\noindent{\it Observação}.  Obtivemos as saídas acima através de algo como 
\begintt
  printnode(h->token); /* assumimos que printnode() acerta a endentacao */
  show(h->l);          /* a subárvore esquerda primeiro, recursivamente */
  show(h->r);          /* depois a direita */
\endtt
executado recursivamente.  
\bye

