\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 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: mais ou menos 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}
\pagebreak

\begin{enumerate}
\item (valor 2.0 pontos) \\
Faça um programa que utiliza uma pilha e reconhece se uma palavra sobre um
alfabeto $\Sigma = \{a,b,c\}$ pertence ao seguinte conjunto: 
\[ \{ w \in \Sigma^* : w = xc^+x^r, \mbox{ onde } x \in \{a,b\}^*\}\]
onde, 
\begin{itemize}
\item[] $A^*$ : conjunto de todas as palavras formadas com as letras de $A$;
\item[] $l^+ = \{l, ll, lll, llll, \dots\}$
\item[] $x^r$ é o reverso da palavra $x$, ou seja, $x$ lida de trás para a
frente. 
\end{itemize}
\pagebreak
\item (valor 1.0+1.0 pontos) \\
Considere a lista ligada dada pela declaração abaixo. 
\begin{verbatim}
public class LL
{ 
   Celula inicio; 
   .
   .
   .
}

public class Celula
{
   Elemento info;
   Celula   prox;
   .
   .
   .
}
\end{verbatim}
a. Escreva um método {\tt void OrdenaBubble()} da classe LL 
 que ordena a lista ligada usando o método Bubblesort com aviso de troca. \\
b. Faça uma análise do seu método, dizendo qual o número máximo de comparações
 e trocas feitas em função do número de elementos da lista ($n$). Diga também
 qual é a complexidade de uma operação de troca na sua implementação.
\pagebreak
\item (valor 0.3+0.7+1.0 pontos) \\
a. Descreva (com palavras) o que é uma lista ligada circular com cabeça de
lista (LLCCL). \\
b. Escreva uma descrição da classe LLCCL, mostrando como deve ser implementado
um construtor da classe. \\
c. Faça um método {\tt void InsereInicio (Elemento x)} que recebe um elemento
$x$ e inclui $x$ no início da lista. 
\pagebreak
\item (valor 0.5+0.5+1.0 pontos) \\
a. Escreva uma descrição da classe ArvoreBB, que implementa uma árvore de
busca binária. \\
b. Escreva um método {\tt int ContaNos()} que devolve o número de nós de uma
árvore de busca binária. \\
c. Escreva um método {\tt Elemento AchaKesimo(int k)} que devolve o $k$-ésimo
menor elemento da árvore, sem utilizar um vetor auxiliar. 
\pagebreak
\item (valor 0.5+0.7+0.8 pontos) \\
a. Considere a árvore de busca binária abaixo, e justifique por que a mesma é
AVL. \\
b. Simule detalhadamente o que ocorre ao inserirmos 12 na árvore. \\
c. Simule detalhadamente o que ocorre ao removermos 5 da árvore. 
$$\epsffile{p1f1.eps}$$
\pagebreak
\item (valor 0.5 pontos) \\
Responda a pelo menos duas das perguntas abaixo: 

a. Qual é a final do campeonato paulista de 98:
\underline{\phantom{AHSAJHSAJSASJHASHAJAS}} 

b. Qual foi a classificação do IME no último Intercomp:
\underline{\phantom{AHSAJHSAJSAaaSJJS}}

c. Qual o filme brasileiro ganhador do Festival de Berlin:
\underline{\phantom{AHSAJHSaAJSASJA}} 
 
d. Que área estuda o professor no filme ``O Gênio Indomável'':
\underline{\phantom{AHSAJaaaaHSAJ}} 
\end{enumerate}
\end{document}