Curso: SI/CC Disciplina: Estrutura de Dados Período: 2010/1

Curso: SI/CC
Professor: Othon M. N. Batista
Disciplina: Estrutura de Dados
Período: 2010/1
Data: 17/05/2010
2a Avaliação – Gabarito
1. (2 pontos) Faça uma função recursiva que recebe um número natural como parâmetro e retorna o fatorial
deste número natural.
Resposta:
Em Pascal:
Function Fatorial (N : Integer) : Real;
Begin
If (N = 0) Then Fatorial := 1 Else Fatorial := N * Fatorial (N – 1);
End;
Em C:
double Fatorial (unsigned int N)
{
if (N == 0) return (1); else return (N * Fatorial (N – 1));
}
ou, de forma mais compacta:
double Fatorial (unsigned int N)
{
return (N == 0 ? 1 : N * Fatorial (N – 1));
}
2. (2 pontos) Faça uma versão recursiva para uma função que pesquisa um nome em uma lista
simplesmente encadeada. A função deve ter o cabeçalho descrito e utilizar a estrutura de dados sugerida.
Caso encontre o nome na lista, retorna True; caso não encontre, retorna False.
type
cadeia = string [255];
ap_lista = ^registro;
registro = record
nome : cadeia;
proximo : ap_lista;
end;
Function Pesquisa (Lista : ap_lista; Nome : Cadeia) : Boolean;
Resposta:
Em Pascal:
Function Pesquisa (Lista : ap_lista; Nome : Cadeia) : Boolean;
Begin
If (Lista = Nil) Then Pesquisa := False Else
If (Lista ^. Nome = Nome) Then Pesquisa := True Else Pesquisa := Pesquisa (Lista ^. Proximo,
Nome);
End;
Em C:
unsigned int Pesquisa (ap_lista Lista, char *Nome)
{
if (Lista == NULL) return (0); else
if (strcmp (Lista -> nome, Nome) == 0) return (1); else return (Pesquisa (Lista -> proximo, Nome));
}
ou, de forma mais compacta:
unsigned int Pesquisa (ap_lista Lista, char *Nome)
{
return (lista == NULL ? 0 : strcmp (Lista -> Nome, nome) == 0 ? 1 : Pesquisa (Lista -> proximo,
Nome));
}
Curso: SI/CC
Professor: Othon M. N. Batista
Disciplina: Estrutura de Dados
3. (2 pontos) A função de Ackerman A (m, n) está definida como:
{
n1, se m=0
A m , n= Am−1, 1 , se n=0 e m0
Am−1, Am , n−1 , se m0 e n0
Quanto é Ackerman (2, 3)?
Resposta:
Ackerman (2, 3) = 9, pois
A (2, 3) = A(1, A (2, 2))
A (2, 2) = A(1, A (2, 1))
A (2, 1) = A(1, A (2, 0))
A (2, 0) = A (1, 1)
A (1, 1) = A(0, A (1, 0))
A (1, 0) = A (0, 1)
A (0, 1) = 2
A (0, 2) = 3
A (1, 3) = A(0, A (1, 2))
A (1, 2) = A(0, A (1, 1))
A (1, 1) = A(0, A (1, 0))
A (1, 0) = A (0, 1)
A (0, 1) = 2
A (0, 2) = 3
A (0, 3) = 4
A (0, 4) = 5
A (1, 5) = A(0, A (1, 4))
A (1, 4) = A(0, A (1, 3))
A (1, 3) = A(0, A (1, 2))
A (1, 2) = A(0, A (1, 1))
A (1, 1) = A(0, A (1, 0))
A (1, 0) = A (0, 1)
A (0, 1) = 2
A (0, 2) = 3
A (0, 3) = 4
A (0, 4) = 5
A (0, 5) = 6
A (0, 6) = 7
A (1, 7) = A(0, A (1, 6))
A (1, 6) = A(0, A (1, 5))
A (1, 5) = A(0, A (1, 4))
A (1, 4) = A(0, A (1, 3))
A (1, 3) = A(0, A (1, 2))
A (1, 2) = A(0, A (1, 1))
A (1, 1) = A(0, A (1, 0))
A (1, 0) = A (0, 1)
A (0, 1) = 2
A (0, 2) = 3
A (0, 3) = 4
A (0, 4) = 5
A (0, 5) = 6
A (0, 6) = 7
A (0, 7) = 8
A (0, 8) = 9
}
Período: 2010/1
Data: 17/05/2010
Curso: SI/CC
Professor: Othon M. N. Batista
Disciplina: Estrutura de Dados
Período: 2010/1
Data: 17/05/2010
4. (2 pontos) Faça uma função recursiva que calcula a potência de números naturais. A função deve receber
dois parâmetros: a base, um número natural, e o expoente, um número natural.
Resposta: números naturais não podem ser negativos! Portanto, testar números negativos é
desnecessário.
Em Pascal:
Function Potencia (Base : Integer; Expoente : Integer) : Real;
Begin
If (Expoente = 0) Then Potencia := 1 Else Potencia := Base * Potencia (Base, Expoente – 1);
End;
Em C:
double Potencia (unsigned int Base, unsigned int Expoente)
{
if (Expoente == 0) return (1); else return (Base * Potencia (Base, Expoente – 1));
}
ou, de forma mais compacta:
double Potencia (unsigned int Base, unsigned int Expoente)
{
return (Expoente == 0 ? 1 : Base * Potencia (Base, Expoente – 1));
}
5. (2 pontos) Faça uma função recursiva que soma os N primeiros termos de uma progressão aritmética. A
função deve retornar um número real. São parâmetros para a função: o primeiro termo da progressão
(número real), a razão da progressão (número real) e a quantidade de termos que devem ser somados
(número real).
Resposta:
Em Pascal:
Function Soma (A0 : Real; R : Real; Qtd : Real) : Real;
Begin
If (Qtd = 0) Then Soma := 0; If (Qtd = 1) Then Soma := A0 Else Soma := (A0 + R * (Qtd – 1)) +
Soma (A0, R, Qtd – 1);
End;
Em C:
double Soma (double A0, double R, double Qtd)
{
if (Qtd == 0) return (0); else if (Qtd == 1) return (A0); else return (A0 + R * (Qtd – 1) + Soma (A0, R, Qtd
– 1));
}
ou, de forma mais compacta:
double Soma (double A0, double R, double Qtd)
{
return (Qtd == 0 ? 0 : Qtd == 1 ? A0 : A0 + R * (Qtd – 1) + Soma (A0, R, Qtd – 1));
}