\documentclass[12pt]{article}
\newcommand{\lastedit}{2001-11-08 21:32:37 by lac}

\usepackage{amssymb}
\usepackage{largepages}
\usepackage[portuges,brazil]{babel}
\usepackage[latin1]{inputenc}

\def\ra{bogus}
\newcounter{chapter}
\input{macros-trig}
\input{macros-captionbox}
\input{macros-psbox}

\newcommand{\ANSBOX}[2]{\framebox[#1cm]{\rule{0mm}{#2cm}{\tiny\em resposta}}}

\begin{document}

\thispagestyle{empty}

\begin{center}
\large\bf MC202 - Estruturas de Dados\\Semestre 2001-2 - Turmas EF\\Prova 2: 6/nov/2001
\end{center}

\begin{center}
${}$%
  \framebox[3.5cm][l]{\rule{0mm}{0.6cm}{\bf RA}}%
  \quad%
  \framebox[8.5cm][l]{\rule{0mm}{0.6cm}{\bf Nome}}\\%
\vspace*{2mm}
${}$%
  \framebox[5.5cm][l]{\rule{0mm}{0.6cm}{\bf Assinatura}}%
  \quad%
  \framebox[6.5cm][l]{\rule{0mm}{0.6cm}{\bf Notas}}
\end{center}

{\bf
\noindent
A prova é individual e sem consulta.\\
Não são permitidos computadores ou calculadoras.\\
Não separe as folhas deste caderno de prova.\\
Não é permitido o uso de outro rascunho além destas folhas.\\
Escreva seu nome completo, e assine a tinta.\\
Valem apenas as respostas nos espaços indicados.
}

\begin{enumerate}

\item ${}$[2.5 pontos]
\label{ex.busca23}
Escreva um procedimento $\v{Busca}(A,{\QAquery}, \k{var} {\QAresult})$ para localizar um elemento com chave
${\QAquery}$ numa árvore de busca 2-3. Cada nó $p$ da árvore tem contador de
chaves $p\up.{\QAnch}\in\set{1,2}$, chaves $p\up.{\QAchave}[0..{\QAnch}-1]$,
dados associados $p\up.{\QAelem}[0..{\QAnch}-1]$ e sub-árvores
$p\up.{\QAsub}[0..{\QAnch}]$.

\vspace*{3mm}
\ANSBOX{15}{9}

\newpage

\item ${}$[2.5 pontos]
\label{ex.heapsort}
Considere um heap binário armazenado nas posições $H[0..n-1]$ de um vetor $H$,
da maneira vista em classe.  Cada elemento $H[j]$ do vetor 
é um ponteiro para um registro que contém, entre outros, 
um campo \emph{prioridade} $H[j]\up .\v{pr}$ (um número real). 
O \emph{heap} está organizado de modo que $H[0]$
é o elemento de \emph{\QBorder} prioridade.

Suponha que na aplicação em questão é necessário às vezes retirar ou
alterar a prioridade de um elemento $d$ que já está no meio do \emph{heap}.
Para que essa operação possa ser implementada sem ter que procurar o elemento 
no \emph{heap} todo, é preciso acrescentar a cada registro de dados $d$ um 
campo de $d\up.{\QBindex}$ que dá a posição corrente do mesmo 
no \emph{heap}.  Ou seja, para todo elemento ocupado $H[i]$ do \emph{heap},
devemos ter $H[i]\up.{\QBindex} = i$.

Para manter esta condição, sempre que as operações de inserção e
remoção movem um elemento de lugar no \emph{heap}, elas precisam
atualizar seu campo ${\QBindex}$ de acordo. Escreva portanto um
procedimento $\v{Insere}(d, \k{var} H, \k{var}n)$ que acrescenta um novo elemento $d$
ao \emph{heap} $H$, atualizando os campos ${\QBindex}$ dos dados
conforme necessário.

\vspace*{3mm}
\ANSBOX{15}{12}

\newpage

\item ${}$[2.5 pontos]
\label{ex.achata}
Considere uma árvore B com campos como na questão~\ref{ex.busca23}, exceto que o
número de chaves de um nó ${\QAnch}$ pode variar de ${\QCmin}$ a
${\QCmax}$, inclusive. Escreva um procedimento $\v{Achata}(p, \k{var} \v{sub},
\k{var} \v{ch}, \k{var} n)$ que, dado um nó interno $p$ da árvore, coloca no vetor
$\v{sub}$ a lista de todas as sub-árvores de todos os filhos de $p$, e
no vetor $\v{ch}$ todas as chaves de $p$ e de seus filhos. O número
total de chaves deve ser devolvido em $n$. A ordem das sub-árvores e
chaves deve ser respeitada; isto é, todo mundo em $\v{sub}[k]$ deve
ter chave menor que $\v{ch}[k]$, que por sua vez deve ser menor que
todo mundo em $\v{sub}[k+1]$, para todo $k\in\set{0..{\QAnch}-1}$.

\newcommand{\pp}{\hbox{:}}
\item ${}$[2.5 pontos]
\label{ex.qqcab}
Your task is to write a program to aid in the assembly of a jigsaw puzle
(``quebra-cabeças'', ``???'') by a robot. 

The puzzle is a a rectangular array of flat four-sided pieces. Except
for the outer borders, each side of each piece is shaped in such a way
that it fits perfectly only the correct side of opposite piece.

When the puzzle is presented to the robot, all the pieces are
scrambled and spread out on a table, face up, in front of the robot's
camera eye. Let's assume that someone already wrote software that does
the image processing part of the problem: namely, find the puzzle
pieces in the image captured by the camera, break the outline of each
piece into its four sides, and find pairs of sides that have the same
shape. Your task is to program the next step --- namely, decide where
in the grid each piece should be placed, and how it should be turned.

The image-processing software assigns, to each piece that the robot
sees on the table, a unique \emph{piece number} between 0 and $N -
1$, in some arbitrary order. It also labels the sides of each piece
with integers 0, 1, 2, and 3, in counterclockwise order, starting from an
arbitrary side:
  $$
    \piece{0}{0}{1}{2}{3}
    \quad
    \piece{1}{0}{1}{2}{3}
    \quad\ldots\quad 
    \piece{N}{0}{1}{2}{3}
  $$
The input to your program begins with two integers $N$ (the number of
pieces) and $K$. Then come $K$ lines, one for each pair of similar
sides that were found among all pieces seen by the robot, in arbitrary
order. Each of these lines contains four integers like this:
  $$
    17\pp 2 \quad 23\pp 1
  $$
This line says that side number $2$ of piece number $17$ fits
side $1$ of piece $23$.  Therefore, in the assembled puzzle,
pieces 17 and 23 should be neighbors, in one of these four positions:
  $$
    \hstack{\piece{17}{1}{2}{3}{0}\piece{23}{2}{3}{0}{1}}
    \quad
    \vstack{\piece{17}{2}{3}{0}{1}\piece{23}{3}{0}{1}{2}}
    \quad
    \hstack{\piece{23}{0}{1}{2}{3}\piece{17}{3}{0}{1}{2}}
    \quad
    \vstack{\piece{23}{1}{2}{3}{0}\piece{17}{0}{1}{2}{3}}
  $$
The output of your program should be a sequence of $N$ lines, one for
each piece, containing four integers
  $$
    6 \quad 9 \quad\quad 17\pp 2
  $$
This line says that piece number $17$ should be placed in row 6
and column 9 of the grid, turned so that its
side number 2 lies at the bottom.  (By convention, rows 
are numbered from top to bottom, and columns from left to right,
starting with 0.)

You can assume that the input data file includes enough information to
assemble the puzzle completely. Note, however, that the input file may
not include all pairs of matching sides, and it may include some
redundant pairs that could be deduced from the previous ones.

Note also that any solution can be rotated by multiples of 90 degrees
to make three other solutions. In order to make the output unique, you
must turn your solution around so that piece number 0 has its side
number 0 at the bottom (turned towards the robot).
In any case, the upper left corner of the assembled puzzle should 
position $[0,0]$.

For example, if the input is 
$$
  \input{trig-3-4-in.tex}
$$
The output should be
$$
  \input{trig-3-4-out.tex}
$$
which represents the solution
\begin{center}
  ${}$
  \input{trig-3-4-pic.tex}
\end{center}

\vspace*{3mm}
\ANSBOX{15}{15}

\newpage

\item ${}$[2.5 pontos]
Suponha que cada nó $p$ de uma árvore de busca binária tem os
apontadores $p\up.\v{chave}$, $p\up.\v{esq}$ e $p\up.\v{dir}$
tradicionais, com nós em ordem crescente da esquerda para a direita.
Suponha que cada nó possui também um campo $p\up.\v{prox}$,
inicialmente indefinido. Escreva um procedimento que, dado um ponteiro
$A$ para a raiz da árvore, atribui todos os apontadores $\v{prox}$ de
modo a formar uma lista linear com todos os nós da árvore, em ordem
\emph{\QDorder} de chave. O procedimento deve devolver o endereço $L$
do primeiro nó da lista. Isto é, $L\up$ deve ser elemento de
{\QDfirst} chave na árvore, $L\up.\v{prox}\up$ deve ser o segundo
{\QDfirst}, e assim por diante.

\vspace*{3mm}
\ANSBOX{15}{15}
   
\end{enumerate}

\end{document}
