Curso: SI/CC
Professor: Othon M. N. Batista
Disciplina: Estrutura de Dados
Período: 2011/1
Data: 20/06/2011
3a Avaliação – Gabarito
1. (2,0 pontos) Considerando árvores binárias de pesquisa, apresente a árvore para os valores lidos nesta
ordem: 83, 102, 205, 34, 1, 19, 12, 41, 15, 20, 31, 7, 6, 10 e 44. Após desenhar a árvore, responda aos
itens.
1.1. Qual a altura desta árvore?
Resposta: 7.
1.2. Quantos nós folhas existem na árvore?
Resposta: existem 6 nós folhas na árvore.
1.3. Quantos e quais nós estão no mesmo nível que o nó que tem o número 31, inclusive?
Resposta: 3, eles são: 7, 15 e 31.
1.4. Com estes valores se fosse possível construir uma árvore balanceada, qual seria a altura dela?
Por quê?
Resposta: 4. Porque se a árvore fosse balanceada para 15 valores são necessários 2 4 - 1 nós,
sendo 4 a altura.
2. (2,0 pontos) Considere a árvore que você desenhou na questão 1 desta prova e recupere e liste os
valores com o algoritmo pré-ordem.
Resposta: 83, 34, 1, 19, 12, 7, 6, 10, 15, 20, 31, 41, 44, 102, 205
3. (2,0 pontos) Mostre a diferença em quantidade de nós visitados entre pesquisar o valor 44 utilizando
pesquisa linear e pesquisa binária. Considere os valores na ordem em que foram lidos da questão 1 para
pesquisa linear e os valores inseridos na árvore binária de pesquisa da questão 1 para pesquisa binária.
Resposta: para recuperar o valor 44 usando pesquisa linear são necessárias 15 iterações, enquanto
para recuperar o mesmo valor usando pesquisa binária são necessárias apenas 4 iterações. Isso
mostra que no pior caso, a pesquisa binária é melhor que a pesquisa linear. Além disso, uma árvore
binária de pesquisa pode ser utilizada para que os valores sejam mantidos ordenados.
4. (2,0 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, 4)?
Resposta:
A (2, 3) = A(1, A (2, 2))
A (2, 2) = A(1, A (2, 1))
}
Curso: SI/CC
Professor: Othon M. N. Batista
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
A (1, 9) = A(0, A (1, 8))
A (1, 8) = A(0, A (1, 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
Disciplina: Estrutura de Dados
Período: 2011/1
Data: 20/06/2011
Curso: SI/CC
Professor: Othon M. N. Batista
Disciplina: Estrutura de Dados
Período: 2011/1
Data: 20/06/2011
A (0, 8) = 9
A (0, 9) = 10
A (0, 10) = 11
5. (2 pontos) Faça uma função recursiva que soma os N primeiros termos de uma progressão geométrica. 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). A fórmula para o termo geral de uma progressão geométrica é a n = a * rn-1. sendo a o primeiro
termo, r a razão e an o termo de ordem n.
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 * Eleva (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 * pow (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 * pow (R ,Qtd – 1) + Soma (A0, R, Qtd – 1));
}