informatica

ENGENHARIA DA COMPUTAÇÃO
Nota : __________

Lista 02
TAD, Alocação Dinâmica e Complexidade
Nome: _______________________________________ Nº Matr.:___________
Rubrica do Professor

Período: ____ Turma: ______ Turno: _______ Data Entrega: _28_/_10_/_13_
Professor: THIAGO MAGELA

Valor: 4 PONTOS

1) Usando a representação de números racionais apresentada abaixo, escreva rotinas para somar, subtrair e dividir tais números. struct RATIONAL
{
int numerator; int denominator;
};

2) Implemente uma função equal que determine se dois números racionais, r1 e r2, são iguais ou não.
3) Faça um programa que leia um valor n e crie dinamicamente um vetor de n elementos e passe esse vetor para uma função que vai ler os elementos desse vetor. Depois, no programa principal, o vetor preenchido deve ser impresso. Além disso, antes de finalizar o programa, deve-se liberar a área de memória alocada.
4) Criar um tipo abstrato de dados que represente uma pessoa, contendo nome, data de nascimento e CPF.
Crie uma variável que é um ponteiro para este TAD (no programa principal). Depois crie uma função que receba este ponteiro e preencha os dados da estrutura e também uma uma função que receba este ponteiro e imprima os dados da estrutura. Finalmente, faça a chamada a esta função na função principal. 5) O que significa dizer que uma função g(n) é O(f(n))?
6) Indique se as afirmativas a seguir são verdadeiras ou falsas e justifique a sua resposta:
a. 2n+1 = O(2n).
b. 22n = O(2n).
c. É melhor um algoritmo que requer 2n passos do que um que requer 10n5 passos.
d. f(n) = O(u(n)) e g(n) = O(v(n)) => f(n) + g(n) = O(u(n) + v(n))
e. f(n) = O(u(n)) e g(n) = O(v(n)) => f(n) - g(n) = O(u(n) - v(n))
7) Suponha um algoritmo A e um algoritmo B com funções de complexidade de tempo a(n) = n2 – n +
549 e b(n) = 49n + 49, respectivamente. Determine quais são os valores de n pertencentes ao conjunto dos números naturais para os quais A leva menos tempo para executar do