%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Monday 30 Jun 2008 08:51:44pm BRT yoshi@turan.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

%\usepackage{refcheck}
\usepackage{srcltx}

\usepackage{fullpage}
\usepackage{setspace}

\let\:=\colon
\let\epsilon=\varepsilon
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}

\def\barp{{\bar p}}

\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\def\observacao#1{[\textit{Observação.} #1]}

\begin{document}
\title[MAC0323 Estruturas de dados]{Prova Substitutiva de Estruturas de 
  Dados\\BCC, 1{\tiny o.} semestre de 2008} %\date{Versão de \today}
\maketitle
\footskip=20pt

\vspace{-\medskipamount}
\noindent{\bf Instruções:}
\begin{enumerate}\small
\item Não destaque as folhas do caderno de soluções.
\item A prova pode ser feita a lápis.  Cuidado com a legibilidade.
%\item Há~$3$ questões na prova. Verifique antes de começar a prova
%se o seu caderno de questões está completo.
\item Não é permitido o uso de folhas avulsas para rascunho.
%\item Nas questões que envolvem elaboração de programas, coloque
%comentários suficientes para que o programa seja facilmente
%compreendido.
\item Não é necessário apagar rascunhos no caderno de soluções.
\item Asserções imprecisas valem pouco.  Justifique suas asserções (dentro do
  razoável!). 
\end{enumerate}

\medskip\noindent
\textbf{Faça no máximo 3 questões!}
\medskip

\onehalfspacing

\begin{enumerate}
\thispagestyle{empty}  

\item{}[3~pontos]
  \begin{enumerate}
  \item[(\textit{i})]Suponha que inserimos, nesta ordem, as 11 chaves %
    \verb| Q U E M I T O F A C L | em uma árvore binária de busca (ABB)
    inicialmente vazia.  Desenhe as ABBs que temos ao longo do processo
    (desenhe~11 árvores).
  \item[(\textit{ii})]Suponha agora que removemos \verb|E| da ABB resultante
    em~(\textit{i}).  Mostre como se dá esse processo de remoção. 
  \end{enumerate}
{\small
\begin{verbatim}
        link partR(link h, int k)
          { int t = h->l->N; 
            if (t > k) { h->l = partR(h->l, k); h = rotR(h); }
            if (t < k) { h->r = partR(h->r, k-t-1); h = rotL(h); }
            return h; /* rotR() e rotL() ajustam o campo N dos nós */
          }
        link joinLR(link a, link b)
          { if (b == z) return a;
            b = partR(b, 0); b->l = a; 
            return b;
          }
        link deleteR(link h, Key v)
          { link x; Key t = key(h->item);
            if (h == z) return z; 
            if (less(v, t)) h->l = deleteR(h->l, v);
            if (less(t, v)) h->r = deleteR(h->r, v);
            if (eq(v, t)) { x = h; h = joinLR(h->l, h->r); free(x); }
            return h;
          }
        void STdelete(Key v)
          { head = deleteR(head, v); }
        \end{verbatim}
}\noindent

\item{}[3~pontos] Suponha que inserimos, nesta ordem, as~11 chaves %
  \verb| Q U E M I T O F A C L | em uma ABB aleatória inicialmente
  vazia.  Suponha que a árvore resultante é tal que todas as subároves
  esquerdas são vazias (todos os ponteiros esquerdos apontam para
  \verb|z|).
  \begin{enumerate}
  \item[(\textit{i})]Mostre como se deu essa evolução da ABB vazia até esta
    ABB resultante (desenhe as várias ABBs intermediárias).  
  \item[(\textit{ii})]Qual é a probabilidade de termos essa ABB
    resultante?  Não se esqueça de justificar sua resposta com
    cuidado. 
  \end{enumerate}
  {\small
\begin{verbatim}
        link insertT(link h, Item item)
          { Key v = key(item);
            if (h == z) return NEW(item, z, z, 1); 
            if (less(v, key(h->item))) { h->l = insertT(h->l, item); h = rotR(h); }
                                  else { h->r = insertT(h->r, item); h = rotL(h); }
            /* Lembre que rotR() e rotL() ajustam o campo N dos nós */         
            return h;
          }
        link insertR(link h, Item item)
          { Key v = key(item), t = key(h->item);
            if (h == z) return NEW(item, z, z, 1);
            if (rand()< RAND_MAX/(h->N+1)) return insertT(h, item); 
            if less(v, t) h->l = insertR(h->l, item);
                     else h->r = insertR(h->r, item);
            (h->N)++; return h;
          }
        void STinsert(Item item)
          { head = insertR(head, item); }
\end{verbatim}
  }\noindent
  
\item{}[4~pontos]
  \begin{enumerate}
  \item[(\textit{i})]Suponha que inserimos, nesta ordem, as chaves %
    \verb| A S E R C H I N G X | em uma árvore 2-3-4 inicialmente vazia.
    Desenhe as árvores 2-3-4 que temos ao longo do processo.  Desenhe pelo
    menos 10 árvores; para dizer como a árvore evolui, voce pode (deve?)
    desenhar árvores intermediárias/auxiliares.
  \item[(\textit{ii})]Suponha agora que inserimos, nesta ordem, as chaves %
    \verb| A S E R C H I N G X | em uma árvore rubro-negra esquerdista
    (ARNE) inicialmente vazia.  Desenhe as ARNEs correspondentes às
    últimas~$4$ árvores 2-3-4 do item~(\textit{i}) (desenhe as~$4$
    árvores resultantes da inserção de~\verb|I|, \verb|N|, \verb|G|
    e~\verb|X|). 
  \item[(\textit{iii})]Descreva cuidadosamente como ocorre a inserção
    de~\verb|G| na sua ARNE (queremos saber aqui como a 2a.~ARNE que
    você desenhou no item~(\textit{ii}) acima evolui para se tornar a
    3a.~ARNE que você desenhou).  Para responder a este item, desenhe
    várias ARNEs (ou partes de ARNE) para ilustrar a execução do
    algoritmo de inserção em ARNEs.
  \item[(\textit{iv})]Repita~(\textit{iii}) acima com a inserção
    de~\verb|X|: diga como a 3a.~ARNE que você desenhou
    em~(\textit{ii}) evolui para a 4a.~ARNE que você desenhou.
  \end{enumerate}
  {\small
\begin{verbatim}
        link RBinsert(link h, Item item)
        {  Key v = key(item);
           if (h == z) 
              return NEW(item, z, z, 1); /* o 1 indica ponteiro vermelho */
           if (h->l->red && h->r->red)) colorFlip(h);
           if (less(v, key(h->item))) h->l = insert(h->l, item); 
                                 else h->r = insert(h->r, item); 
           if (h->r->red) h = rotL(h);
           if (h->l->red && h->l->l->red) h = rotR(h);
           return h;
        }
        void STinsert(Item item)
        {  head = RBinsert(head, item); head->red = 0; }
\end{verbatim}
  }\noindent

\item{}[3~pontos] Suponha que inserimos, nesta ordem, as~11 chaves %
  \verb| Q U E M I T O F A C L | em uma tabela de hashing inicialmente vazia
  com~$M=12$ entradas.  Suponha que usamos a função de hashing $13k\bmod M$
  para transformar a $k$-ésima letra do alfabeto no endereço da tabela (por
  exemplo, \verb|A|~é levado ao endereço~$1$ e~\verb|S| é levado ao
  endereço~$7$).
  \begin{enumerate}
  \item[(\textit{i})]Calcule o valor da função de hashing para cada uma das~11
    chaves acima.
  \item[(\textit{ii})]Mostre claramente a evolução da tabela nesse processo,
    supondo que usamos resolução de colisões por \textit{linear probing}.
  \item[(\textit{iii})]Suponha agora que removemos \verb|Q| da tabela
    resultante em~(\textit{i}).  Descreva como ocorre essa remoção.
  \end{enumerate}
  {\small
\begin{verbatim}
        void STdelete(Item item)
          { int j, i = hash(key(item), M); Item v;
            while (!null(i))
              if eq(key(item), key(st[i])) break; 
              else i = (i+1) % M;
            if (null(i)) return;
            st[i] = NULLitem; N--;
            for (j = i+1; !null(j); j = (j+1) % M, N--)
              { v = st[j]; st[j] = NULLitem; STinsert(v); }
          }
\end{verbatim}
  }\noindent

\end{enumerate}

\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 

