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

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


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

\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$}}}$}}


\begin{document}

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

BCC -- Segunda Prova -- 16 de junho de 1998

\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. 
\end{enumerate}

{\bf DURA\c C\~AO DA PROVA:  3 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
Quest\~ao 6  & \\
\hline
\hline
TOTAL & \\
\hline
\end{tabular}
\end{center}

{\bf BOLÃO: Brasil \underline{\phantom{50}} x \underline{\phantom{50}}
Marrocos} 
\pagebreak

\begin{enumerate}
\item (valor 1.0+1.0 pontos) \\
Prove ou dê um contra-exemplo: \\
a. Em uma árvore de busca binária, seja $C$ o conjunto de vértices visitados
no caminho ao procurar um elemento $y$. Defina, $E$ como sendo o conjunto de
vértices  à esquerda deste caminho e $D$ os vértices à direita deste caminho
(veja a figura abaixo). Então, para todo $x \in C$, $d \in D$ e $e \in E$, 
$d > x$ e $e < x$. 
$$\epsffile{p2f1.eps}$$

\noindent
b. Uma árvore rubro-negra com $n$ vértices tem altura $O(\log n)$.  

\pagebreak
\item (valor 1.0+1.0 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$)? 
Se puder, dê um
exemplo em que isto acontece. \\
b. O que é a estrutura {\bf union-find}? Dê uma aplicação para esta
estrutura. Quais as operações que podem ser realizadas eficientemente com tal
estrutura? Qual a complexidade de cada operação? Justifique. 

\pagebreak
\item (valor 1.0+1.0 pontos) \\
Considere a B-árvore da figura abaixo. 
$$\epsffile{p2f3.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 1.0+1.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 os métodos abaixo. Se você achar
conveniente, sugira uma implementação diferente da vista em sala de aula.  \\
a. {\tt Celula AncestralComumMaisPróximo(Celula $u$, Celula $v$)} que acha o primeiro ancestral 
comum de $u$ e $v$ \\ 
b. {\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{p2f2.eps} $$

\pagebreak
\item (valor 2.0 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. Neste semestre eu tentei utilizar os recursos da rede como apoio para a
disciplina. O que você achou disso? Quantas vezes você visitou a página da
disciplina para ver algo ou tirar uma dúvida? Quantas vezes suas dúvidas foram
tiradas por e-mails da mailing list? 
\end{enumerate}
\end{document}