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

  1. O que é um algoritmo? E um programa?

  2. O que é um Tipo Abstrato de Dados?

  3. Qual a definição do Tipo Abstrato de Dados Lista? Quantas implementações diferentes da Lista foram vistas em aula?

  4. Uma Lista Circular Duplamente Encadeada é um Tipo Abstrato de Dados?

  5. Quais as vantagens e desvantagens da alocação dinâmica de memória sobre a alocação estática de memória?

  6. Um apontador ou pointer é uma variável: o que guarda esta variável?

  7. O que é um dangling pointer? E o que é um leaking pointer?

  8. Em que situação vista detalhamente em aula precisamos usar um pointer-pointer?

  9. Por que a implementação de Filas em Vetor é, em geral, circular?

  10. 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.

  11. 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.

  12. Por que se usa o nodo cabeça na implementação de Lista, Filas e Pilhas com apontadores? É obrigatório seu uso?

  13. (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.

  14. 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?

  15. Uma definição recursiva do fatorial é N! = (N+1)!/(N+1); que tal usar esta definição para implementar uma função no computador?

  16. 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.

  17. Escreva funções recursivas para calcular a soma, subtração, adição e multiplicação de dois números inteiros, positivos maiores que zero.

  18. Escreva um procedimento recursivo para somar todos os elementos de um vetor de N inteiros.