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


\begin{document}

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

BCC -- Primeira Prova -- 28 de abril 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. 
\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 0.5+1.0+1.0 pontos) \\
a. Defina heap. Dê um exemplo de um heap. \\
b. Escreva um método que transforma um vetor em um heap. Simule seu método
para a seguinte entrada: 
\begin{quote}
12 \ \ 25 \ \ 13\ \ 17\ \  19\ \  3\ \  14\ \  5\ \  11
\end{quote}
c. Qual é a complexidade do seu algoritmo? Justifique. \\
Obs.: É possível fazer isso em $O(n)$. 


\pagebreak

\item (valor 1.0+1.0+1.0 pontos) \\
Em uma aplicação queremos utilizar uma árvore de busca binária para armazenar
números inteiros e fazer as
seguintes operações:
\begin{itemize}
\item dados dois inteiros $a$ e $b$, eliminar todos os vértices $v$ da árvore
tais que $a \le v \le b$; 
\item dados dois inteiros $a$ e $b$, verificar se eles estão na árvore, e,
caso estejam, determina o primeiro ancestral comum a eles. 
\end{itemize}

\vspace{5mm}
a. Sugira uma implementação de árvores de busca binária (eventualmente
diferente da vista em sala de aula) em que essas operações são implementadas
eficientemente. \\
b. Escreva métodos para implementar as duas operações descritas acima. \\
c. Analise a complexidade de seus algoritmos. 

\pagebreak
\item (valor 1.0+2.0 pontos) \\
As seqüências abaixo são as obtidas ao percorrermos uma árvore binária em
pós-ordem e in-ordem:
\begin{quote} 
pós-ordem: C I F B K L J H G E D A \\
in-ordem:  A C B I F D G K J L H E \\
\end{quote}
a. Construa a árvore binária correspondente. \\
b. Escreva um método que recebe a seqüência em pós-ordem e in-ordem e constrói
a árvore binária correspondente.  

\pagebreak
\item (valor 0.5+1.0 pontos) \\
a. Defina árvore AVL. Dê exemplos de árvores de busca binária que são e que
não são AVL. \\
b. Simule o algoritmo de inserção em uma árvore AVL para a seqüência abaixo,
mostrando, para cada novo item inserido o estado da árvore: 
\begin{quote}
13 \ \  24 \ \ 18 \ \  7 \ \  1 \ \  4 \ \ 5 \ \  19 \ \ 23 \ \  29
\end{quote} 
\pagebreak
\item (valor 1.0 pontos) \\
Estamos na metade do semestre. Faça uma análise parcial da
disciplina. Como você avalia a quantidade de trabalho (listas, eps, etc) dada
até agora? Que sugestão você faria para tornar o andamento
da disciplina MAC 323 melhor daqui para frente? 

\end{enumerate}
\end{document}