\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 -- 26 de maio 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 7 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
Quest\~ao 7  & \\
\hline
\hline
TOTAL & \\
\hline
\end{tabular}
\end{center}
\pagebreak

\begin{enumerate}
\item (valor 0.8+0.7+0.5+1.0 pontos) \\
Considere um heap com $n \ge 10$ elementos, em que o elemento é sempre maior
que seus filhos, armazenado em um vetor. \\
a. Que posições do vetor o terceiro maior elemento pode ocupar? 

\vspace{2cm}

b. Que posições do vetor o menor elemento pode ocupar? 

\vspace{2cm}

Considere agora um heap ternário, em que os filhos de um elemento na posição
$i$ estão nas posições $3i + 1$, $3i+2$ e $3i+3$. \\
c. Qual a altura máxima de um heap ternário com $n$ elementos? 

\vspace{2cm}

d. Você vê algum inconveniente em considerar heaps de ordem $m$ (cada elemento
tem $m$ filhos) com valores grandes de $m$? Justifique. 


\pagebreak

\item (valor 0.5+0.5+0.5 pontos) \\
a. Quais são as árvores binárias que quando percorridas em in-ordem e
pré-ordem obtemos a mesma seqüência? 

\vspace{4cm}

b. Quais são as árvores binárias que quando percorridas em in-ordem e
pós-ordem obtemos a mesma seqüência? 

\vspace{4cm}

c. Quais são as árvores binárias que quando percorridas em pré-ordem e
pré-ordem obtemos a mesma seqüência? 


\pagebreak
\item (valor 1.0 ponto) \\
Considere uma árvore de busca binária $T$ e seja $C(x)$ o conjunto de vértices
visitados ao procurar o elemento $x$ em $T$. Defina agora $E(C)$ o conjunto de
vértices de $T$ das subárvores esquerdas dos vértices de $C(x)$ e,
analogamente, $D(C)$ o conjunto de vértices das subárvores direitas dos
vértices de $C(x)$. \\
Prove ou dê um contra-exemplo: para todo vértice $y \in E(C)$ e $z \in D(C)$,
$y < x< z$. 

\pagebreak
\item (valor 1.0 ponto) \\
Simule detalhadamente a execução do algoritmo de inserção em árvores
rubro-negras para obter a árvore correspondente à seqüência: 

\[ 10 \; \; \; 7 \; \; \; 4 \; \; \; 3 \; \; \;  2 \; \; \;  19 \; \; \;  18
\; \; \;  15 \; \; \;  11 \]

\pagebreak
\item (valor 0.7+0.8 pontos) \\
Considere a árvore AVL $T$ abaixo. Mostre todos os passos resultantes de: 
$$ \epsffile{p3f1.eps} $$
a. inserir 32 em $T$. \\
b. remover 50 de $T$. 

\pagebreak
\item (valor 0.8+0.6+0.6 pontos) \\
a. Qual é o número máximo de elementos que uma B-árvore de ordem $m$ e altura
$h$ pode ter? Justifique. 

\vspace{4cm}
b. Qual é o número mínimo de elementos que uma B-árvore de ordem $m$ e altura
$h$ pode ter? Justifique. 

\vspace{4cm}
b. Qual é a altura máxima que uma B-árvore de ordem $m$ e $n$ elementos
pode ter? Justifique. 

\pagebreak
\item (valor 0.5 ponto) \\
Quantas horas por semana você passa usando o computador para os
exercícios do curso? 

\vspace{1cm}

Quanto deste tempo você usa o CEC? 

\vspace{1cm}

Quanto deste tempo você usa a rede linux (126, 258)? 

\vspace{1cm}

Como você avalia a infra-estrutura computacional disponível para os alunos? 

\end{enumerate}
\end{document}