Desenvolvimento de um SGBD - 06/02
10 pontos
- Criação de um programa em C que implemente CRUD
- Mostrar execução do código com as 4 funções implementadas
Questões:
- 1. Qual o custo do algoritmo?
- Um algoritmo deve:
- Funcionar corretamente
- Executar o mais rápido possível
- Utilizar a memória da melhor forma possível
- O que podemos analisar de um algoritmo ? Podemos determinar:
- O tempo de processamento de um programa como função de seus dados de entrada
- O espaço de memória máximo ou total requerido para os dados do programa
- O comprimento total do código do programa
- Se o programa chega corretamente ao resultado desejado
- A complexidade do programa
- Facilidade em ler, entender e modificar
- A robustez do programa
- Exemplo: como ele lida com entradas errôneas ou inesperadas
- Um algoritmo deve:
- 2. Qual foi o percurso utilizado?
- Em nível: Neste tipo de percurso os nós são visitados de cima para baixo e da esquerda para a direita. Em relação ao exemplo, a ordem de visita dos nós seria:
- A B C D E F G H I.
- O algoritmo pode utilizar uma fila. A ideia é colocar a raiz da árvore binária na fila e, a partir daí, visitar o nó do início da fila, ao mesmo tempo em que se colocam seus filhos no final da mesma.
- A B C D E F G H I.
- Pré-ordem: Neste tipo de percurso visita-se prioritariamente a raiz, em seguida a subárvore da esquerda e, depois, a subárvore da direita. Para o exemplo adotado, a ordem de visita seria:
- A B D C E F G H I.
- O algoritmo pode utilizar uma pilha. A ideia é colocar a raiz na pilha e, a partir daí, visitar o nó do topo da pilha, ao mesmo tempo em que se empilham a raiz da subárvore direita e da subárvore esquerda
- A B D C E F G H I.
- Ordem simétrica: Neste tipo de percurso visita-se prioritariamente a subárvore da esquerda, em seguida a raiz e, finalmente, a subárvore da direita. No exemplo, teríamos:
- B D A E C H I G F.
- O algoritmo que será apresentado também utiliza uma pilha. A idéia é colocar, sucessivamente, a raiz da subárvore esquerda na pilha até se chegar a um link nulo, quando então se visita o topo da pilha, repetindo-se o processo para a subárvore da direita.
- B D A E C H I G F.
- Pós-ordem: Neste tipo de percurso visita-se prioritariamente a subárvore da esquerda, em seguida a subárvore da direita e, por fim, a raiz. Para o exemplo adotado, a ordem de visita seria:
- D B E I H G F C A.
- O algoritmo pode utilizar uma pilha e é um algoritmo de difícil entendimento, devendo ser verificado cuidadosamente. Cada nó é colocado na pilha duas vezes. A primeira quando se está empilhando ramos à esquerda da árvore; a segunda quando o empilhamento é pela direita. Um nó só é visitado quando ele é o topo da pilha e foi a segunda vez que entrou na mesma.
- D B E I H G F C A.
- Em nível: Neste tipo de percurso os nós são visitados de cima para baixo e da esquerda para a direita. Em relação ao exemplo, a ordem de visita dos nós seria:
- Referência:
- Paulo Eustáquio Duarte Pinto
- Instituto de Matemática e Estatística
- Departamento de Informática e Ciência da Computação
- Universidade Estadual do Rio de Janeiro
- Agosto de 2002