MC600 - Segundo semestre de 1997 - LISTA 2 - Solucoes
-----------------------------------------------------

1.

  a.   (A B C D)

  b.   NIL

  c.   H

  d.   (A (C X))

2.  Ha' duas respostas para esta pergunta.  Se voce considerar
    S-expressoes escritas sempre usando a notacao de par-com-ponto,
    sem a convencao de simplificacao para listas, entao da'

    PP = P = C = A-1.

    Cada caixa (C) e' um par-com-ponto, que inclui um ponto (P) e
    um par de parentesis (PP).  Alem disso, voce pode olhar a
    S-expressao como uma arvore binaria, onde as folhas sao atomos (A)
    e os nos internos sao caixas (C).  Dai' vem C = A-1, pois numa
    arvore binaria ha' sempre exatamente uma folha a mais do que
    nos internos.

    Mas se voce for considerar a convencao de lista, note que ela
    permite que voce "cancele" um ponto com um atomo:

    (A . NIL) = (A)

    e tambem um ponto com um par de parentesis:

    (A . (B C D)) = (A B C D)

    Note que C nao foi perturbado.  Logo, podemos dizer que existem
    novos numeros P', PP', A', sendo que cada ponto a menos
    corresponde ou a um par de parentesis a menos, ou a um atomo a
    menos.  Ou seja,

    C-P' = (C-PP')+(C+1-A')

    Simplificando,

    PP' + A' = C + P' + 1.

3.

  a.   (+ 1 (* 8 5))

  b.   (* (- (* 13 (/ 4 5)) 81) 47)

  c.   (- (- (- 2 2) 2) 2)

4.  Retorna uma mais que o valor de seu argumento.

5.

  a.   3

  b.   10

  c.   erro: xxx nao tem valor como dado

6.   6