Universidade Federal do Paraná
Departamento de Informática
Bacharelado em Ciência da Computação
Prof. Elias P. Duarte Jr.
Lista 1 de Algoritmos II
- O que é um algoritmo? E um programa?
- O que é um Tipo Abstrato de Dados?
- Qual a definição do Tipo Abstrato de Dados Lista? Quantas
implementações diferentes da Lista foram vistas em aula?
- Uma Lista Circular Duplamente Encadeada é um Tipo Abstrato de Dados?
- Quais as vantagens e desvantagens da alocação dinâmica de memória sobre
a alocação estática de memória?
- Um apontador ou pointer é uma variável: o que guarda esta variável?
- O que é um dangling pointer? E o que é um leaking pointer?
- Em que situação vista detalhamente em aula precisamos usar um pointer-pointer?
- Por que a implementação de Filas em Vetor é, em geral, circular?
- Escreva um algoritmo que faça a checagem dos parêntesis de uma expressão
aritmética. Não se esqueça de emitir mensagens adequadas.
- Usando as operações vistas em aula para a Fila e para a Pilha, escreva
um algoritmo para inverter os elementos de uma Fila usando uma Pilha.
- Por que se usa o nodo cabeça na implementação de Lista, Filas e
Pilhas com apontadores? É obrigatório seu uso?
- (Do Ziviani) Duas pilhas podem co-exisitir em um mesmo vetor, uma
crescendo em um sentido, outra no outro. duas filas ou uma pilha e uma fila
também podem ser alocadas no mesmo vetor com o mesmo grau de eficiência?
Explique.
- O fatorial foi o primeiro algoritmo recursivo que estudamos na
disciplina. Escreva dois programas na linguagem C que implementam o
fatorial RECURSIVO e ITERATIVO. Em suas implementações a cada vez que
o fatorial de 1 é calculado uma mensagem é impressa na tela. Edite,
compile e execute seus programas. Quantas mensagens surgem quando você
calcula o fatorial de 8 na versão iterativa? E na versão recursiva?
- Uma definição recursiva do fatorial é N! = (N+1)!/(N+1); que tal
usar esta definição para implementar uma função no computador?
- Escreva os programas iterativo e recursivo que exibem como saída a série
completa de Fibonacci, do zero-ésimo termo ao i-ésimo termo, sendo i dado
como entrada para o programa.
- Escreva funções recursivas para calcular a soma, subtração, adição e
multiplicação de dois números inteiros, positivos maiores que zero.
- Escreva um procedimento recursivo para somar todos os elementos de um
vetor de N inteiros.