\documentclass[12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}

\setlength{\parskip}{0.3cm}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{21.5cm}
\input{epsf}
\begin{document}
\begin{center}
{\large MAC 323 -- Estruturas de Dados -- Prim. Sem. 1998}

Quinta Lista de Exerc\'\i cios (30 pontos) -- Entrega: 25 de maio
\end{center}

\begin{enumerate}

\item (valor 5 pontos) \\
Seja $T$ a \'arvore rubro--negra a seguir. Mostre todos os passos resultantes
da inser\c c\~ao de 12.
$$\epsffile{lista5f1.eps} $$


\item (valor 5 pontos) \\
Dados 
\[ \begin{array}{llll}
          & a_1 = 3 & a_2 = 2 & a_3 = 5\\
    b_0=0 & b_1 = 1 & b_2 = 7 & b_3 = 2
   \end{array} \] 
construa (mostrando os passos da constru\c c\~ao), a \'arvore de busca bin\'aria
\'otima correspondente.   

\item (valor 5+5+5 pontos)\\
Considere o algoritmo de compressão de textos baseado no Código de Huffman,
dado em sala de aula. \\
a. Mostre a árvore resultante da construção com a seguinte freqüência de
acessos: 
\[ \begin{array}{rrrrrrrrrrrrrrrr}
A  & B & C  & D & E & I & J & L & M & O & P & R & S & T & U & \\
23 & 4 & 18 & 7 & 19& 12& 5 & 10& 10& 11& 3 & 4 & 9 & 8 & 2 & 12\\
\end{array}
\]
b. Qual é o código correspondente à frase abaixo: 
\begin{quote}
 TRICOLOR CAMPEAO PAULISTA
\end{quote}
\item (valor 5+5 pontos)\\
Considere a seguinte B-\'arvore. 

$$\epsffile{lista5f2.eps}$$

a. Mostre os passos resultantes da inser\c c\~ao de 40.\\
b. Mostre os passos resultantes da remo\c c\~ao de 6. 
\end{enumerate}
\end{document}