gabarito_P1.rtf

{\rtf1\ansi\ansicpg1252\cocoartf2513
\cocoatextscaling0\cocoaplatform0{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
{\colortbl;\red255\green255\blue255;}
{\*\expandedcolortbl;;}
\paperw11900\paperh16840\margl1440\margr1440\vieww16300\viewh8200\viewkind0
\pard\tx566\tx1133\tx1700\tx2267\tx2834\tx3401\tx3968\tx4535\tx5102\tx5669\tx6236\tx6803\pardirnatural\partightenfactor0

\f0\fs40 \cf0 Q1: \
\
a) F, V, V, V\
\
b) Theta(n^3), \
    Theta(n^2 log n),\
    Theta(n)\
    Theta(n^2.5)\
\
\
Q2: \
 \
a)  2^k \'e9 a maior pot\'eancia de 2\
     que \'e9 menor do que N\
     1 + 2 + 4 + 8 + 16 + \'85 + 2^k =\
    = 2^(k+1) - 1\
    = 2. 2^k - 1 < 2N - 1                                 N = 1       total = 0\
    = O(N)N = 2      total = 1   \
                                                                     N = 3      total = 3\
                                                                     N = 4      total = 3\
                                                                     N = 5      total = 7\
                                                                     N = 6      total = 7\
                                                                     N = 7      total = 7\
                                                                     N = 8      total = 7\
                                                                     N = 9      total = 15\
 \
b) N + N + N + N + \'85                                \
    num total de O(log(N)) parcelas\
    = O(N log N)                                                       \
\
\
Q3: - elementos est\'e3o ordenados na lista\
\pard\tx566\tx1133\tx1700\tx2267\tx2834\tx3401\tx3968\tx4535\tx5102\tx5669\tx6236\tx6803\ri-2540\pardirnatural\partightenfactor0
\cf0        - implementa\'e7\'e3o da lista linear precisa ser sequencial\
          (array!) \
\
Q4: - Criar um atributo inteiro \'93tamanho\'94 que mantenha, \
        sempre atualizado, o tamanho da lista. Esse atributo\
        come\'e7a em zero (lista vazia) e \'e9 incrementado/\
       decrementado a cada inser\'e7\'e3o/remo\'e7\'e3o. No caso de uma \
       concatena\'e7\'e3o com outra lista, precisaremos somar o \
       tamanho da lista que foi concatenada. \
\
Q5:\
\
	a)                                 8\
                                      /       \\\
                                 -14         28\
                                /     \\       /     \\\
                             -24    -4  18     38\
\
                 Resposta: -4\
\
 	b)      -24, -14, -4, 8, 18, 28, 38\
\
\
Q6:   Para cada elemento da fila, eu o empilharia, de forma que, \
        ap\'f3s ter percorrido toda a fila, a sequ\'eancia de        \
        elementos na pilha (do topo para o fundo) corresponda\
        \'e0 sequ\'eancia inversa da fila. Bastaria ent\'e3o comparar os\
        elementos da fila e da pilha, na ordem de remo\'e7\'e3o \
        pr\'f3pria dessas estruturas (removendo sempre o primeiro\
        da fila e o topo da pilha). Se as sequ\'eancias \
       corresponderem, \'e9 pal\'edndromo; sen\'e3o, n\'e3o \'e9.\
        PS.: Quando estiver removendo da fila para empilhar, \
       acrescenta novamente o elemento no fim da fila, para que,\
       no final (ap\'f3s \'93tamanho da fila\'94 itera\'e7\'f5es), tenhamos \
       novamente a fila original.             \
\
	  OU\
\
	Percorremos a primeira metade da fila, empilhando cada\
     elemento. Ao percorrer a segunda metade da fila,\
     comparamos cada elemento com o topo da pilha, \
     desempilhando. Se a compara\'e7\'e3o falhar em algum momento,\
    n\'e3o \'e9 pal\'edndromo; caso contr\'e1rio, \'e9. \
     PS.: Se a quantidade de elementos da fila for \'edmpar,\
    o elemento central n\'e3o deve ser empilhado; n\'f3s apenas\
    o bypassamos.\
\
Q7:\
    a) \
         - p\'f3s ordem\
         - visitar um n\'f3 x corresponderia a\'85\
                x.descendentes = \
                         (x.esq != null ? x.esq.descendentes + 1 : 0) +\
                         (x.dir != null ? x.dir.descendentes + 1 : 0)\
				\
                OU (em linguagem natural)\
            \
           \'85anotar o n\'famero de descendentes do n\'f3 x,\
                que seria igual ao \
                n\'famero de descendentes de seu\
                filho esquerdo mais um (caso haja filho esquerdo)\
                mais\
               o n\'famero de descendentes de seu\
               filho direito mais um (caso haja filho direito)\
\
	b) - pr\'e9-ordem\
         - visitar um n\'f3 x corresponderia a\'85\
                 x.maiorValorAteARaiz = \
                     x.pai == null \
                                ? x.valor \
                                : max(x.valor, x.pai.maiorValorAteARaiz)\
			\
              OU (em linguagem natural)\
           \
        \'85comparar o valor do n\'f3 x com o maior valor entre\
              seu pai e a raiz (j\'e1 devidamente calculado, por ser\
             um percurso em pr\'e9-ordem); caso n\'e3o tenha pai,\
             o maior valor ser\'e1 o valor do pr\'f3prio n\'f3\
             (que \'e9 o caso da raiz, apenas)\
\
\
\
\
\
\
}