Exercicios!!!

[Yoshiharu Kohayakawa <yoshi@ime.usp.br>]

Pus 20 exercicios na pagina, em preparacao para a prova.  Vejam

  http://www.ime.usp.br/~yoshi/mac324/Ps/exx/l1

Estou tambem enviando uma versao texto da lista de exercicios abaixo.  Gerei
esta versao texto automaticamente, e nao tive tempo de debuga-la,
infelizmente.  Assim, espero que todos consultem a pagina acima para pegar uma
versao melhor deste material.

Divirtam-se e ate segunda, Yoshi

===============================================================================
MAC324                            EXERCÍCIOS                            24/4/99



Obs. Nos exercícios com listas ligadas, vamos assumir que temos

     typedef struct node *link;
     struct node { Item item; link next; }



1. Neste exercício, assuma que implementamos listas ligadas sem cabeça e sem
cauda de lista. Escreva uma função de protótipo


     link reverta(link h);


que recebe um ponteiro para o primeito elemento de uma lista (NULL caso esta
lista seja vazia) e devolve um ponteiro para o primeiro elemento da reversão
da lista dada, isto é, uma lista com exatamente os mesmos elementos da lista
original, mas com os elementos em ordem reversa.  Aqui, voc^e deve apenas
alterar os ponteiros dos elementos da lista para conseguir este objetivo; você
não deve alocar mais memória para produzir a lista nova.

2. Suponha neste exercício que as nossas listas estão implementadas com
cabeças de listas (em particular, a lista `vazia' contém exatamente um
elemento, a saber, a cabeça de lista). Ademais, assuma que Item é o tipo
int. Escreva uma função de protótipo


     link acerte_prim_el(link h);


que recebe um ponteiro para o começo de uma lista e reorganiza os elementos
desta lista de forma que o elemento com a menor chave (isto é, com o menor
campo item) é o primeiro elemento da lista nova. A sua função deve devolver um
ponteiro para o começo da nova lista.

3. Escreva uma função de protótipo


     link ordene(link h);


que ordena os elementos de uma lista em ordem crescente das chaves (isto é,
campo item, que assumimos serem inteiros). Use a função do exercício
anterior. Tanto a lista original como a lista resultante devem ter cabeças de
lista.

4. [3.36 do Sedgewick] Escreva uma função que rearranja os elementos de uma
lista dada, pondo todos os elementos que ocorrem nas posições pares antes de
todos os elementos de ocorrem nas posições ímpares.  Você deve preservar a
ordem relativa dos elementos pares entre si, e a ordem relativa dos elementos
ímpares entre si.

5. [3.38 do Sedgewick] Escreva uma função de protótipo


     link copia(link h);


que recebe um ponteiro para o começo de uma lista e devolve um ponteiro para
uma nova lista, que é uma cópia da lista dada. A nova lista deve conter uma
cópia de cada elemento da lista original; estas cópias devem ocorrer `na mesma
ordem' que na lista original.

6. Assuma que pomos


     typedef struct { float Re; float Im; } *Complex;


Escreva uma função de protótipo


     Complex COMPLEXmult(Complex z, Complex w);


que devolve (um ponteiro) para o produto de z e w.

7. Suponha novamente que temos definido o tipo Complex. Suponha também que
temos listas ligadas com Item definido como Complex. Escreva uma função de
protótipo


     Complex COMPLEXsum(link h);


que recebe uma lista ligada representando uma seqüência de números complexos,
e que devolve a soma desta lista de números complexos. Assuma que a lista não
tem nem cabeça nem cauda de lista.

8. [4.6 do Sedgewick] Este é um exercício sobre pilhas. Na seqüência


    E A S * Y * Q U E * * * S T * * * I O * N * * *


uma letra significa empilhe e um asterisco desempilhe.  Qual é a seqüência de
letras devolvida pelos desempilhe?

9.  [4.7 do Sedgewick] Continuemos usando a notação do exercício anterior.
Diga como devemos inserir asteriscos na seqüência E A S Y para que os
desempilhe devolva as seguintes seqüências: (i) E A S Y, (ii) Y S A E, (iii) A
S Y E, (iv) A Y S E, (v) E Y A S. Note que nem sempre podemos obter a saída
desejada; nestes casos, argumente por que a dada saída não pode ser obtida
desta forma.

10. [4.9 do Sedgewick] Converta a expressão


    ( 5 * ( ( 9 * 8 ) + ( 7 * ( 4 + 6 ) ) ) )


para a notação pósfixa e para a notação infixa.

11. [4.31 do Sedgewick] Este é um exercício sobre filas. Na seqüência


    E A S * Y * Q U E * * * S T * * * I O * N * * *


uma letra significa inserção no fim da fila e um asterisco significa remoção
do começo da fila.  Qual é a seqüência de letras devolvida por esta seqüência
de operações em nossa fila?

12. [O problema das panquecas] Suponha que temos, por exemplo, a seqüencia de números


     8 2 3 5 1 4 9 7 6 0


Imagine que esta seqüência indica uma pilha de panquecas de 10 tamanhos
distintos, empilhadas de forma que a menor está no fundo da pilha, a maior é a
quarta panqueca a partir do fundo da pilha, a segunda maior está no topo,
etc. As únicas operações permitidas são inverter um segmento inicial desta
seqüência.  Portanto, existem 9 operações não-triviais para a pilha acima; uma
delas produz, por exemplo,


     5 3 2 8 1 4 9 7 6 0


Podemos chamar esta operação deste exemplo de `operação número 4', já que
invertemos a ordem das 4 panquecas do topo. O problema é o seguinte: dados um
inteiro positivo n e uma permutação dos inteiros não-negativos menores do que
n, determinar uma seqüência de operações (permitidas) que resultam na
seqüência


     0 1 2 ... n - 1


Isto é, com as panquecas em ordem crescente, do topo para o fundo. Escreva uma
função de protótipo


     void imprima_solucao(int n, int panq[]);


para resolver este problema.


13. [5.11 do Sedgewick] Escreva um programa recursivo que converte uma
express"ao em notação infixa em notação pósfixa.


14. [5.14 do Sedgewick] Escreva uma função recursiva que remove o último
elemento de uma lista ligada.


15. [5.17 do Sedgewick] Escreva uma função recursiva de protótipo


     Item max_el(link h);


que recebe um ponteiro para o começo de uma lista ligada (sem cabeça e sem
cauda) e que devolve a maior chave (isto é, campo item) presente na lista,
onde assumimos que Item é o tipo int.


16. [5.48 do Sedgewick] Determine o conteúdo dos vetores maxKnown[] e
itemKnown[] que são determinados pelo programa 5.13 (prog5.13.c da página) na
chamada knap(17), com os itens

            0   1   2   3   4
    item    A   B   C   D   E
    size    3   4   7   8   9
    valor   4   5  10  11  13

17. [5.55 do Sedgewick] Lembre que os coeficientes binomiais satisfazem a
recorrência

                            `   '   `    '   `     '
                              N   =  N - 1 +  N - 1
                              k        k      k - 1

                                           N    N
para todo k >= 1 e todo N. Ademais, temos  0 =  N = 1. Escreva uma função
recursiva de protótipo 


     long binom(long N, long k);

             N
que calcula  k . Use programação dinâmica. Verifique experimentalmente a
diferença de eficiência entre as implementações sem e com programação
dinâmica. 


18. [5.62 do Sedgewick] Existe uma correspondência entre árvores binárias e
certas seqüências de bits. Para uma seqüência de bits corresponder a uma AB,
devemos ter que o número de 0s excede de um o número de 1s e ainda vale que,
lendo a seqüência da esquerda para a direita, o número de 0s nunca excede o
número de 1s. Estas seqüências (que chamaremos de válidas) também podem ser
caracterizadas da seguinte forma: a seqüência com um único bit 0 é valida; se
duas seqüências são válidas então a concatenação delas, antecedida por um bit
1, é válida.  Desenhe a AB que corresponde à seqüência válida


     1 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 0 0

19. [5.63 do Sedgewick, variante] ABs são equivalentes a seqüências
bem-formadas de parênteses. Note que seqüências bem-formadas de parênteses
podem ser definidas desta forma: a seqüência ( ) é bem-formada.  Se duas
seqüências s e t são bem-formadas, então ( s t ) é bem formada.  Desenhe a AB
que corresponde à seqüência


     ( ( ( ( ) ( ( ) ( ) ) ) ( ( ( ) ( ) ) ( ) ) ) ( ) )

20. [5.79 do Sedgewick] Suponha que percorremos as árvores abaixo em
pré-ordem, in-ordem, pós-ordem, e por níveis, imprimindo o conteúdo dos
nós. Quais são as seqüências de caracteres assim obtidas?


    (i) D          (ii) C          (iii  E
          B               B                C
            A               A                B
             N               N                 A
             N               N                   N
            C               N                    N
             N            D                    N
             N              N                D
          F                 E                  N
            E                 N                N
             N                N            H
             N                               F
            G                                  N
             N                                G
             N                                  N
                                                N
                                             I
                                               N
                                               N


Observação. Obtivemos as saídas acima através de algo como


     printnode(h->token); /* assumimos que printnode() acerta a endentacao */
     show(h->l);         /* a subárvore esquerda primeiro, recursivamente */
     show(h->r);         /* depois a direita */


executado recursivamente.
===============================================================================