\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 -- 24 de março 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
Quest\~ao 6  & \\
\hline
\hline
TOTAL & \\
\hline
\end{tabular}
\end{center}
\pagebreak

\begin{enumerate}
\item (valor 2.0 pontos) \\
Considere uma expressão aritmética escrita em notação posfixa e armazenada em
uma string. 
\begin{verbatim}
public class PosFixa
{
  private char [] posfixa;  //  expressão em notação posfixa
  private int     nele;     //  número de caracteres na expressão

  .
  .
  .
}
\end{verbatim}

Escreva um método \texttt{public double avalia()} que 
calcula o valor da expressão. 

Exemplo: Para a expressão \begin{verbatim} 4 3 + 8 * \end{verbatim} seu
programa deve dar como resposta $56$. 

Você pode supor que os operandos são números inteiros entre 0 e 9. Para
transformar o caractere \texttt{posfixa[i]} no inteiro correspondente use o
método \texttt{int char2int(char a)}.  
\pagebreak

\item (valor 1.0+1.0+1.0 pontos) \\
Que estrutura de dados (usando as que nós vimos até agora) 
você usaria em cada uma das situações
abaixo? Justifique sua resposta. 
\begin{itemize}
\item Armazenar a lista de livros emprestados de uma biblioteca. As operações
de inserção e remoção serão feitas freqüentemente. Além disso, desejamos saber
rapidamente se um livro está ou não emprestado. 

\item Armazenar a fila de processos em um sistema de multiprocessamento, em
que há duas classes de processos com prioridades diferentes. Se existir um
processo de prioridade maior esse deverá executar, caso contrário qualquer
processo de prioridade mínima pode executar. 

\item Armazenar os valores das variáveis locais e parâmetros de funções em um
compilador. Lembre que algumas funções podem ser recursivas. 
\end{itemize}
\pagebreak
\item (valor 0.5+0.5 ponto) \\
a. Descreva o algoritmo de Ordenação Topológica visto em sala de aula, bem
como a estrutura de dados utilizada na solução do problema. \\

b. Simule o algoritmo para a seguinte entrada: 
\[ 4<3 \; \; \; 2 < 5 \; \; \; 7 < 8 \; \; \; 5 < 7 \; \; \; 3 < 8 \; \; \; 4
< 2\]

\pagebreak
\item (valor 2.0 pontos) \\
Descreva uma implementação de pilha utilizando uma lista ligada circular com
cabeça de lista. Escreva os métodos de pilha utilizando esta implementação. 


\pagebreak
\item (valor 2.0 pontos) \\
Considere uma lista ligada circular conforme declarado abaixo: 

\begin{verbatim}
public class Celula
{
  private int info;
  private Celula prox; 

  public boolean Epar()
  {
    return (info % 2 == 0);
  }
  public Celula LeProx()
  {
    return (prox);
  }
  .
  .
  .
}

public class Lista
{
  Celula fim; 

  .
  .
  .
}
\end{verbatim}

Faça um método \texttt{void TiraPar()} que elimina da lista todas células de
conteúdo par. 

\pagebreak
\item (valor 0.5 pontos) \\
Responda a pelo menos duas das perguntas abaixo: 

a. Qual foi o placar de {\huge São Paulo} x {\tiny Corinthians} no último
confronto entre os times no campeonato paulista?
\vspace{10mm}

b. Qual foi a classificação do IME no voleibol feminino no Bichusp 99?
\vspace{10mm}

c. Cite dois museus situados no campus da USP: 
\vspace{10mm}

d. Qual a profissão do sargento interpretado por Tom Hanks em ``O resgate do
soldado Ryan''?
\vspace{10mm}

\end{enumerate}
\end{document}