Algoritmos e Estruturas de Dados
Lista de Exercícios 1
Data de Distribuição: 08 de abril de 1999
Data de Entrega: 29 de abril de 1999
Orientações:
- Esta lista deve ajuda-lo na preparação para o primeiro exercício escolar.
- Esta lista é individual. Em caso de cópia será atribuída a nota 0 (zero) a todas as listas idênticas.
- Todas as implementações devem ser feitas em C, o executável disponibilizado em disquete, devidamente documentado, que possa ser executado pelos monitores, e devem ter uma interface que permita o teste da solução.
- A solução de cada questão deve ser entregue junto com o código fonte, tudo devidamente organizado e comentado.
- Cada dia de atraso implica em 0,5 ponto a menos na nota desta lista.
- Esta lista contem 6 questões.
- Escolha uma implementação do TDA lista (via
tabelas ou
via ponteiros) e faça um programa para manipular uma lista que inclua as operações INSERIR, LOCALIZAR, ACEDER, SUPRIMIR, SEGUINTE, PRECEDENTE, ZERAR, PRIMEIRO, LISTAR (3,0)
- A partir da implementação escolhida na
questão 1 (via tabelas ou via ponteiros), faça um programa para manipular uma pilha que inclua as operações ZERAR, TOPO, EMPILHAR, DESEMPILHAR, VAZIO. (1,0)
- Escolha uma implementação do TDA arvore (via
tabelas ou via ponteiros) e faça um programa para manipular uma
arvore que inclua as operações PAI, PRIMEIRO_FILHO,
IRMAO_DIREITO, ETIQUETA, RAIZ, ZERAR (3,0)
- A partir da implementação escolhida na
questão 3 (via tabelas ou via ponteiros), faça um programa para efetuar um percurso pósfixado de uma arvore.. (1,0)
- Sejam as funções de n:
f1(n) = n2
f2(n) = n2 + 1000n
f3(n) = n, se n é impar; n3 se n é par
f4(n) = n, se n £
100; n3 se n > 100
Indicar para cada par i e j distintos se fi(n) é em O(fj(n)) e se fi(n) é em W
(fj(n)) (1,0)
- Usando a notação O forneça, em função de n, a complexidade no pior dos casos da função seguinte (1,0):
void misterio (int n)
{
int i, j, x, y;
for(i = 1; i <= n-1; i++)
{
for(j = i + 1; j <= n; j++)
{
for(k = 1; k <= j; k++)
{
intruções em O(1);
}
}
}
}