Exercícios de Técnicas de Programação
LISTAS LIGADAS
1. Pretende-se desenvolver uma aplicação capaz de armazenar a informação relativa
a todos os sócios de um Clube de Futebol, utilizando para o efeito uma lista ligada
simples.
a) Comece por definir o tipo de nodo a usar na lista, uma estrutura que permita
representar a informação referente a um único sócio, concretamente o nome,
número e valor da quota a pagar. Considere que os nodos da lista devem estar
ordenados pelo nome do sócio.
b) Escreva uma função que lhe permita acrescentar um novo sócio.
c) Escreva uma função que lhe permita listar a informação referente a todos os
sócios.
d) Escreva uma função que lhe permita remover um sócio, a partir do seu nome.
e) Escreva uma função que lhe permita armazenar a lista num ficheiro designado
por “socios.bin”.
2. O Dr. Sampaio, médico de clínica geral, foi destacado para se deslocar às Terças e
Sextas Feiras à freguesia de Outeiro para aí atender a alguns pacientes. Até aqui o
historial de cada paciente tem sido mantido, pelos vários médicos que se deslocam
a Outeiro, em fichas de papel. No entanto esta solução tem levantado alguns
problemas: é que o acesso à informação é lento, as fichas de papel tendem a
deteriorar-se e alguns dos médicos têm uma letra ilegível. Por estes e outros
motivos o Dr. Sampaio pediu à junta de freguesia para ver se seria possível
instalar um computador com um programa de gestão de pacientes, de preferência
nada de muito complicado, bastando que permita guardar o nome, a data de
nascimento e o historial médico de cada paciente. Cabe-lhe a si implementar tal
programa (não se esqueça, são necessárias as rotinas para inserir, remover, alterar,
consultar, salvaguardar/aceder, listar, ...).
LISTAS DUPLAMENTE LIGADAS
3. Pretende-se implementar um programa para gerir a informação referente aos
funcionários de uma Câmara Municipal, utilizando para tal uma lista duplamente
ligada. A informação a reter para cada funcionário consiste no número do bilhete
de identidade, nome e vencimento. Suponha que os funcionários se encontram
ordenados pelo número do bilhete de identidade.
1
a) Comece por definir o tipo de nodo a usar na lista, contendo toda a informação
necessária.
b) Desenvolva uma função que lhe permita inserir um novo funcionário na lista.
c) Desenvolva uma função que lhe permita pesquisar um funcionário pelo seu
número de bilhete de identidade.
d) Desenvolva uma função que lhe permita listar todos os funcionários existentes
na lista.
e) Desenvolva uma função que lhe permita gravar e ler para/do ficheiro.
LISTAS CIRCULARES SIMPLES
4. A Comissão Nacional de Eleições pretende adquirir uma aplicação para gerir a
informação de todos os eleitores existentes em Portugal. A informação a reter para
cada eleitor consiste no número, nome, data de nascimento e residência.
Pretende-se utilizar uma lista circular simples ordenada pelo número de eleitor.
a) Comece por definir o tipo de nodo a usar na lista, contendo toda a informação
necessária.
b) Escreva uma função que lhe permita inserir um novo eleitor na lista.
c) Escreva uma função que lhe permita remover um eleitor da lista.
d) Escreva uma função que lhe permita listar todos os eleitores com idade
superior ou igual a 50 anos.
e) Escreva uma função que lhe permita armazenar a lista num ficheiro designado
por “eleitores.bin”.
STACK’s
5. Pretende-se que desenvolva um programa que transforme uma expressão
matemática em notação infixa para notação sufixa (notação Polaca). Para efectuar
esta transformação deverá ter em atenção as seguintes regras:
− um operador é sempre empilhado;
− um operador no topo é desempilhado quando chega outro operador de menor
ou igual prioridade;
− um parêntesis de abertura é sempre empilhado;
− um parêntesis de fecho faz desempilhar até ao parêntesis de abertura.
Exemplos:
2*(3+4)
→
234+*
(1+5)*(8-(4-1))
→
15+841--*
2+4*5
→
245*+
2
QUEUE’s
6. A oficina de automóveis “A Ribeira” utilizando as novas tecnologias pretende dar
uma resposta cabal ao aumento crescente dos seus clientes. Assim, os clientes ao
chegarem à oficina, dirigem-se à recepção, onde preenchem uma ficha, que para
além de conter a informação pessoal, serve para determinar a ordem de
atendimento.
Pretende-se que implemente um programa com base numa queue estática que
realize as seguintes operações:
a) Escreva uma função que lhe permita inserir um novo cliente na fila.
b) Escreva uma função que lhe permita atender um cliente.
c) Escreva uma função que lhe permita gravar num ficheiro todos os clientes
existentes em fila de espera.
d) Escreva uma função que lhe permita ler do ficheiro criado na alínea anterior
todos os clientes.
7. A secção de consultas sem marcação do Centro de Saúde de Bragança deparava-se
com algumas dificuldades no atendimento dos pacientes, os quais tinham a
tendência natural para "dar o golpe", acumulando-se às portas dos consultórios,
dificultando o trabalho dos médicos, enfermeiros e paramédicos. O director do
centro de saúde decidiu pôr ordem à situação, mandando implementar um sistema
que garantisse o atendimento ordenado dos pacientes. A solução encontrada
consistiu em instalar um leitor de código de barras no qual os pacientes, logo que
chegam ao centro de saúde, passam o cartão de utente ficando imediatamente
inseridos numa fila de espera informatizada, que trata de chamar cada um na sua
vez. Cabe-lhe a si implementar a parte informática de tal sistema sabendo que
através da leitura do cartão é possível saber o nome, data de nascimento, número
de beneficiário e historial médico do paciente (não se esqueça, são necessárias as
rotinas para inserir, remover, salvaguardar/aceder, ...).
TABELAS DE HASH
8. A Câmara Municipal de Bragança pretende manter um registo de todos os
moradores guardando para cada um deles informação sobre a freguesia onde
reside, morada e telefone. Cada morador é identificado pelo número do BI e é
também guardado o seu nome e número de contribuinte. Implemente em C um
programa que permita gerir esta informação (adicionar novo morador, remover
morador, alterar e consultar informações). Após cada utilização devem ser
gravadas as alterações para posterior entrada no sistema.
NOTA: Use tabelas de hash com “listas de colisões”.
3
9. Crie mais duas funções no âmbito do problema do exercício anterior: uma função
em C que determine o número de colisões para cada uma das posições na tabela; e
uma outra que permita pesquisar determinada informação na tabela, tendo como
parâmetro um campo da estrutura que não é chave.
10. Considere que se pretende alterar o programa anterior de forma a que:
•
cada chave representa o n.º BI do chefe de família e portanto deve-lhe estar
associada não apenas a informação do chefe mas de todo o agregado familiar
•
considera-se um agregado familiar um conjunto de pessoas que partilham a
mesma freguesia, morada e telefone.
Altere o exercício anterior usando uma tabela de hash (com “listas de colisões”)
onde cada nodo tem pendurada uma lista do agregado familiar
11. Crie um programa de gestão para o problema dos exercícios anteriores usando
uma tabela de hash com “linear probing”.
12. Hospital Distrital de Bragança mantém um registo de todos os pacientes que já
atendeu. Assim quando alguém dá entrada pela primeira vez é criada uma ficha
com o número do bilhete de identidade e nome do paciente, guarda-se também o
número de contribuinte para emitir os recibos das taxas moderadoras. Sempre que
o paciente dá novamente entrada no hospital é identificado pelo número do bilhete
de identidade.
NOTA: O historial médico é obtido através do sistema central do ministério da
saúde. Pede-se que implemente um programa capaz de informatizar a gestão dos
pacientes do Hospital Distrital de Bragança (não se esqueça, são necessárias as
rotinas para inserir, remover, alterar, consultar, salvaguardar/aceder, ...).
ÁRVORES
13. Defina, em C, as estruturas necessárias para representar uma árvore binária de
pesquisa, em que a chave é constituída por um número inteiro e a restante
informação consiste nesse número escrito por extenso. Para essas estruturas,
construa:
a) uma função que, dado um apontador para a raiz de uma árvore binária de
pesquisa, juntamente com a chave e a informação de um nodo a inserir,
permita inserir esse nodo na árvore, retornando um apontador para a árvore
resultado obtida;
b) uma função que permita fazer a travessia de uma árvore binária de pesquisa
em in-ordem, imprimindo desta forma os nodos por ordem crescente da chave;
c) uma função de inserção de nodos numa árvore binária de pesquisa que receba
um duplo apontador para a raiz da árvore, juntamente com a chave e a
4
informação de um nodo a inserir, e retorne um valor booleano que indique
insucesso sempre que o nodo a inserir já exista na árvore.
14. Escreva uma função que conte o número de nodos de uma árvore binária.
15. Escreva uma função que conte o número de folhas de uma árvore binária.
16. Pretende-se converter um texto numa árvore binária de pesquisa contendo todas as
palavras, mas sem repetições na árvore. Cada nodo deverá conter, além da
palavra, o total de ocorrências da palavra no texto. Construa as funções
necessárias a tal tarefa de forma modular, isto é, funções para inserir nodos na
árvore, para tratar o texto e para visualizar a árvore no final.
17. Escreva uma função que permita “espelhar” uma árvore binária, isto é, para cada
nodo troca os seus filhos esquerdo e direito.
18. Escreva uma função que permita construir uma árvore de execução a partir de
uma expressão matemática parentisada, para depois a imprimir em “notação
polaca” (sufixa ou pós-ordem). Por exemplo:
Expressão matemática parentisada: ((((a + b) * c)-(d / f)) + g)
Árvore de execução:
+
-
g
*
+
a
/
c
d
f
b
Notação polaca: a b + c * d f / - g +
20. Pretende-se gerir, usando estruturas dinâmicas, o sistema de acessos dos
utilizadores a uma máquina Unix. Para isso, projectou-se usar uma árvore binária
de pesquisa que guarde a informação relevante do utilizador (nome, login e
password). Para cada utilizador, pretendem-se guardar ainda as datas e horas de
acesso ao sistema. Implemente as seguintes funcionalidades:
a) inserir utilizadores
b) fazer o login de um utilizador, verificando a sua password
c) eliminar um utilizador do sistema
5
21. A clínica privada SóComSaúde funciona no centro de Bragança e apenas admite
sócios. Estes para darem entrada na clínica apresentam o cartão de sócio e só são
atendidos após a recepcionista confirmar se as cotas estão pagas. Este sistema
guarda o nome, a data de nascimento, o historial médico e a data até à qual as
cotas estão pagas. Pede-se que implemente um programa que permita informatizar
o sistema de gestão de pacientes da clínica SóComSaude (não se esqueça, são
necessárias as rotinas para inserir, remover, alterar, consultar,
salvaguardar/aceder, listar, ...).
GRAFOS
22. Defina, em C, as estruturas necessárias para representar o grafo da seguinte figura,
usando listas de adjacências, sabendo que a informação a reter para cada vértice é
o nome da cidade e o número de habitantes, e para cada ligação é a designação da
estrada e a distância.
23. Construa funções que permitam, para o grafo definido no exercício anterior:
a) visualizar de alguma forma o grafo
b) adicionar vértices
c) remover vértices
d) adicionar ligações
e) remover ligações
24. Construa uma função que permita determinar os sucessores de um dado vértice.
25. Construa uma função que permita determinar os antecessores de um dado vértice.
26. Construa uma função que permita verificar se há caminho entre dois vértices
dados.
6
27. Construa uma função que permita determinar um caminho entre dois vértices
dados.
28. Construa uma função que permita determinar todos os vértices alcançáveis a partir
de um dado vértice.
29. Construa uma função que permita determinar todos os vértices que alcançam um
dado vértice.
30. Construa uma função que permita determinar o fecho transitivo do grafo.
31. Construa uma função que permita determinar o menor caminho (com menor
número de vértices) entre dois vértices dados.
32. Construa uma função que permita determinar o caminho de menor custo entre dois
vértices dados.
ALGORITMOS DE ORDENAÇÃO
33. Crie e inicialize um array de inteiros não ordenado e aplique o processo de
ordenação “Bubble Sort” para posicionar os números por ordem descendente.
34. Crie e inicialize um array de inteiros não ordenado e aplique dois ou três
processos de ordenação (Insert Sort, Selection Sort, Bubble Sort, Merge Sort ou
Quick Sort) e compare-os em termos de número de trocas e número de
comparações.
35. Considere que a pauta de classificações da disciplina de Técnicas de Programação
(Nº Mecanográfico, Nome, Classificação) não aparecerá, este ano, por ordem
alfabética dos nomes dos alunos mas sim por ordem descendente de
classificações. Dentro da mesma classificação deverão aparecer então os nomes
por ordem alfabética. Sugestão: Preencha uma estrutura (array ou lista ligada) com
alguns nomes e classificações para testar o algoritmo.
7