\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}
\input{epsf}

\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 818 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 323 -- Estruturas de Dados}
\end{center}

\begin{center}
Quarta Lista de Exerc\'\i cios (30 pontos) -- Entrega: 27 de abril
\end{center}

\begin{enumerate}
\item (6 pontos) \\
Simule a execução do algoritmo de Ordenação Topológica visto em sala de aula,
para construir a estrutura de dados e fazer uma ordenação topológica para a
seguinte ordem parcial: 

\[ 4<3 \; \; \; 2 < 5 \; \; \; 7 < 8 \; \; \; 5 < 7 \; \; \; 3 < 8 \; \; \; 4
< 2\]

\item (6+6 pontos) \\
Descreva uma representação de árvores (não necessariamente binárias). \\
a. Escreva um método {\tt ImprimePorNivel()} \\
b. Escreva um método {\tt Elemento MaiorGrau()} que retorna o elemento de
maior grau. 

\item (10 pontos) \\
Escreva um programa que recebe a lista de nós de uma árvore quando percorrida
em in-ordem e pré-ordem e devolve a árvore. 

\item (6 pontos) \\
Considere uma árvore de busca binária com os elementos $1,2,\dots,1000$. As
seqüências a seguir poderiam ser a seqüência de nós visitados quando estamos
procurando o nó 374? \\
a. 423 -- 118 -- 256 -- 450 -- 354 -- 375 -- 374 \\
b. 423 -- 231 -- 394 -- 300 -- 350 -- 382 -- 374

\item (3+3+3 pontos) \\ 
a. Defina árvore AVL. \\
b. Dê um exemplo de inserção de um elemento em uma árvore AVL que cause
rearranjo da estrutura da árvore. \\
c. Dê um exemplo de remoção de um elemento de uma árvore AVL que cause
rearranjo da estrutura da árvore. 

\end{enumerate}
\end{document}
