MAC 122 - Princípios de Desenvolvimento de Algoritmos

BCC - Segunda Prova - 3 de outubro de 2000

NOME DO ALUNO :
NUSP :
ASSINATURA:

INSTRUÇÕES

1. Preencha o cabeçalho acima.
2. Você preencheu mesmo o cabeçalho acima? Caso o tenha preenchido, verifique se sua prova está completa. Esta prova deve ter 7 folhas (contando esta capa), com o enunciado de 6 questões.

DURAÇÃO DA PROVA: 2 horas

	Nota
Questão 1
Questão 2
Questão 3
Questão 4
Questão 5
Questão 6
TOTAL

B O A P R O V A

1. (valor 1 ponto)
   

   Qual é o valor de $c$ em função de $n$ no final da execução do trecho de programa abaixo? Justifique sua resposta.

   c = 0;
   for( i = 0; i < 2 * n; i++)
     if( i % 2 == 0)
       for( j = i; j > 0; j--)
         c++;
   

2. (valor 1 ponto)
   

   Simule a execução do algoritmo que passa uma expressão aritmética para a notação pósfixa, mostrando a cada caractere lido o estado da pilha como feito em sala de aula.

   A

   *

   B

   +

   (

   C

   -

   D

   *

   E

   -

   (

   F

   +

   (

   G

   *

   Y

   )

   -

   A

   )

   /

   B

   )

   +

   D

   *

   G

   .

3. (valor 2.0 pontos)
   Faça um programa que leia uma seqüência de caracteres sobre o alfabeto $\{ a, b, c, d, e\}$ terminada por '.' e, utilizando pilha, verifica se a seqüência é do tipo
   
   $$xye y^rx^r$$
   
   
   onde, $x$ é uma seqüência de $\{a,b\}$, $y$ uma seqüência de $\{c,d\}$ e $w^r$ é o reverso da seqüência $w$.

4. (valor 2.0 pontos)
   a. Faça um função recursiva Calcula que receba um vetor $v$ com $n$ números reais positivos e calcula
   
   $$1 + \frac{v[0]}{1 + \frac{v[1]}{\begin{array}{c} \vdots \\ 1 + \frac{v[n-2]}{1 + v[n-1]} \end{array}}}$$
   
   

5. (valor 2 pontos)
   

   Mostre uma possível implementação de pilhas usando listas ligadas. Defina o tipo de dados correspondente e escreva as funções para implementar as operações de pilha (inicialização, empilha, desempilha, topo e pilha vazia).

6. (valor 2 pontos)
   

   Considere a implementação de fila vista em sala de aula em um vetor ``circular'' (em que os índices são tomados módulo o tamanho do vetor). Escreva o tipo fila correspondente e os operadores de fila (inicializa, insere, remove, primeiro e fila vazia).