Lista de algoritmos e estrutura de dados PDF

Preview

Summary

Lista 1 de CI056 - Professor Elias ...

Description

1. O que é um algoritmo? E um programa? Algoritmo é uma sequência de passos para resolver um problema. Programa é um algoritmo concretizado que implementa as operações de forma que seja útil. 2. O que é um Tipo Abstrato de Dados? São estruturas e operações necessárias para manipular um programa, que não estão embutidos na linguagem. 3. Qual a definição do Tipo Abstrato de Dados Lista? Sequência de zeros ou mais elementos de um determinado tipo. 4. Quantas implementações diferentes da Lista foram vistas em aula? Três: Lista com vetor, lista encadeada e lista circular duplamente encadeada. 5. Uma Lista Circular Duplamente Encadeada é um Tipo Abstrato de Dados? Não. É uma implementação do TAD lista. 6. Quais as vantagens e desvantagens da alocação dinâmica de memória sobre a alocação estática de memória? Alocação estática de memória todas as posições são imediatamente alocadas na memória (em tempo de execução). Alocação dinâmica de memória criamos espaço em tempo de execução e liberamos espaço da memória para o que não for mais necessário. 7. Um apontador ou pointer é uma variável: o que guarda esta variável? Um endereço de memória. 8. O que é um dangling pointer? E o que é um leaking pointer? Dangling pointer: Um ponteiro que aponta para um endereço de memória que não é válido (foi dado free) Leaking pointer: Quando o ponteiro é perdido ou reservou e não está usando 9. Em que situação vista detalhamente em aula precisamos usar um pointer-pointer?

10. Por que a implementação de Filas em Vetor é, em geral, circular? Como a fila caminha pelo vetor e pode “bater” no final dele é usado um vetor circular. 11. 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. 12. 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. 13. Por que se usa o nodo cabeça na implementação de Lista, Filas e Pilhas com apontadores? É obrigatório seu uso? Para facilitar a implementação, porém é possível realizar sem nodo cabeça. 14. (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. Sim, porém deve ser duplamente encadeada (assim garantiríamos a eficiência). 15. 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?

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

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

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

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