\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}


\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 818 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

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

\begin{center}
Segunda Lista de Exerc\'\i cios (30 pontos) -- Entrega: 27 de março
\end{center}

\begin{enumerate}
\item (5 pontos) \\
Escreva um operador {\tt Elemento AchaKEsimo(int k)} para uma lista ligada, 
que recebe uma lista ligada e devolve uma cópia do $k$-ésimo maior elemento da
lista. 

\item (2+3 pontos) \\
Descreva uma implementação de fila dupla utilizando listas ligadas. Em
particular, escreva o operador {\tt void RemoveDireita()}. 

\item (3+3+3+3 pontos) \\
Considere um conjunto implementado através de listas ligadas. Escreva os
seguintes operadores: 
\begin{itemize}
\item {\tt Conjunto União (Conjunto B)} 
\item {\tt Conjunto Intersecção (Conjunto B)} 
\item {\tt boolean Pertence()}
\item {\tt Conjunto Diferença (Conjunto B)}
\end{itemize}

\item (8 pontos) \\
Considere uma lista ligada em que cada elemento armazena um caractere. Escreva
um método {\tt void TrocaPalavra (ListaLigada P, ListaLigada Q)} que  troca 
todas as ocorrências da palavra $P$ por $Q$ na lista. 

\item (5 pontos) \\
Considere a implementação de polinômios utilizando listas ligadas circulares
com cabeça de lista, vista em sala de aula. Escreva um método 
{\tt boolean Raiz ( double x )} que verifica se $x$ é uma raiz do polinômio. 

\item (6 pontos) \\
Considere o seguinte m\'etodo para criptografar mensagens secretas: 
\begin{itemize}
\item 1. etapa: inverter as seq\"u\^encias de n\~ao vogais, incluindo espa\c cos
e pontua\c c\~ao. 
\item 2. etapa: inverter a mensagem resultante. 
\end{itemize}
Exemplo: \\
Dada a mensagem 
\begin{quote} 
ESTRUTURAS DE DADOS \'E MUITO LEGAL.  
\end{quote}
Ap\'os a primeira etapa, teremos: 
\begin{quote} 
ERTSUTURAD SED ADO S\'EM UITOL EGA.L   
\end{quote}
E depois da segunda etapa teremos: 
\begin{quote} 
L.AGE LOTIU M\'ES ODA DES DARUTUSTRE
\end{quote}
Dada uma lista linear ligada, na qual cada posição contém um caractere da
mensagem codificada, fa\c ca um 
programa que obtenha a mensagem original na mesma lista. 

\end{enumerate}
\end{document}
