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

\setlength{\parindent}{0pt}
\setlength{\parskip}{0.2cm}
\pagestyle{empty}

\def\risonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\smile$}}}$}}
\def\tristonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\frown$}}}$}}

\input{epsf}
\setlength{\textwidth}{17cm}
\setlength{\oddsidemargin}{0cm}


\begin{document}

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

BCC -- Quarta Prova -- 16 de junho de 1999

\begin{tabular}{|lll|}
\multicolumn{1}{c}{\phantom{XXXXXXXXXXXXXX}} & 
\phantom{XXXXXXXXXXXxx} & 
\multicolumn{1}{c}{\phantom{XXXXXXXXXXXXX}} \\
\hline
NOME DO ALUNO : & & \\ & & \\
\hline
ASSINATURA: &  &\\ & & \\
\hline
\end{tabular}

\vspace{0.8cm}
{\bf INSTRU\c C\~OES}

\begin{enumerate}
\item A prova pode ser feita a l\'apis. 
\item A prova consta de 6 quest\~oes. Verifique antes de 
come\c car a resolver a prova se o seu caderno 
de quest\~oes est\'a completo. 
\item Esta prova é substitutiva.  
\end{enumerate}

{\bf DURA\c C\~AO DA PROVA: $2+\epsilon$  horas }

\begin{center} 
{\Large {\bf BOA SORTE!!!!}} 
\end{center} 

\vspace{0.8cm}
\begin{tabular}{|c|c|}
\hline
& \ \ \ Nota \ \ \ \\
\hline
Quest\~ao 1 & \\
\hline
Quest\~ao 2 & \\
\hline
Quest\~ao 3 & \\
\hline
Quest\~ao 4  & \\
\hline
Quest\~ao 5  & \\
\hline
\hline
TOTAL & \\
\hline
\end{tabular}
\end{center}
\pagebreak

\begin{enumerate}

\item (valor 1.5+1.5 pontos) \\
a. Diga o que é uma {\bf árvore de busca binária ótima}. Em que sentido a
árvore é ótima? Uma árvore ótima pode ser desbalanceada (altura $n-1$)? 
Dê um
exemplo em que isto acontece. \\
b. O que é a estrutura {\bf union-find} (manipulação de conjuntos disjuntos)?
Dê uma aplicação para esta 
estrutura. Quais as operações que podem ser realizadas eficientemente com tal
estrutura? Justifique. 


\pagebreak

\item (valor 1.2+1.3 pontos) \\
Considere a B-árvore da figura abaixo. 
$$\epsffile{p4f1.eps}$$
a. Simule {\bf detalhadamente} o que ocorre ao remover o 7. \\
b. Simule {\bf detalhadamente} o que ocorre ao inserir o 29. \\
{\bf Obs.:} Se você não usar o algoritmo dado em sala de aula, explique que
algoritmo de inserção/remoção você está utilizando. 


\pagebreak
\item (valor 2.0 pontos)\\
Dada uma \'arvore bin\'aria $T$, discuta a implementa\c c\~ao mais eficiente 
poss\'\i vel e fa\c ca um algoritmo para o método abaixo. Se você achar
conveniente, sugira uma implementação diferente da vista em sala de aula.  \\
{\tt void Sobe(Elemento $x$)} que recebe um 
elemento $x$ e, se ele estiver na \'arvore e n\~ao for a raiz, sobe o 
n\'o contendo $x$ de um n\'\i vel, mantendo a estrutura de \'arvore 
de busca bin\'aria. Veja o exemplo a seguir. 
$$ \epsffile{p4f2.eps} $$

\pagebreak
\item (valor 2.5 pontos)\\
Dizemos que um grafo $G=(V,E)$ é {\bf bipartido}, se o conjunto de vértices
pode ser particionado em duas partes $V = A \cup B$, com $A \cap B =
\emptyset$ tais que toda aresta do grafo tem exatamente uma ponta em $A$ e uma
ponta em $B$. Faça um método {\tt boolean EBipartido()} que verifica se o
grafo é ou não bipartido. 

\pagebreak
\item (valor 0.25+0.25+0.5 pontos) \\
a. Faça uma crítica à disciplina: conteúdo, trabalhos, listas, EPs, professor,
etc. 

\vspace{6cm}
b. Você lembra de algo que possa ser elogiado? Use o verso se necessário
\risonho 
\vspace{6cm}

c. Seu palpite para o campeão da Libertadores: \hrulefill
\end{enumerate}
\end{document}