Escola Secundária de Emídio Navarro
Estrutura, Organização e Tratamento de Dados
Ficha de Exercícios (Estruturas de Dados e Algoritmia)
Grupo I
1. Transcreva, para uma folha, os “termos” adequados ao preenchimento dos espaços
assinalados no algoritmo seguinte (c, d, e, f, g, h).
Este algoritmo determina a taxa de retenção de IRS na fonte, com base na remuneração
mensal do funcionário e no seu número de dependentes. Considera-se a tabela de trabalho
dependente casado único titular do IRS constituída por 31 intervalos de remuneração, para
determinar a respectiva taxa.
O vector INTERVALOS, com 31 elementos, contém os intervalos de remuneração mensal da
tabela. A matriz TAXAS, com 31 linhas e 6 colunas, contém as taxas de retenção aplicáveis
mediante a remuneração auferida e o número de dependentes (0, 1, 2, 3, 4, 5 ou mais).
Consideram-se ambas as estruturas devidamente preenchidas.
1. [ Ler a remuneração mensal e o número de dependentes do funcionário]
Leia(REMUNERAÇÃO)
Leia(N_DEPENDENTES)
2. [Determinar o índice do intervalo de remuneração]
IÅ1
Repita enquanto c ______________________
d __________ Å I + 1
3. [“Corrigir”, se necessário, o número de dependentes]
Se N_DEPENDENTES e _____________
Então J Å f _______________
Senão g ___________________
4. [Imprimir a taxa de retenção adequada ao funcionário]
h _____________________________________________
5. [Terminar]
Saída
Pág. 1
2. Dado dois vectores ordenados A e B contendo N e M elementos, respectivamente, dispostos
por ordem crescente, elabore um algoritmo que faz a fusão destes vectores e produz um
vector C ordenado, contendo todos os elementos pares.
3. Dado dois vectores ordenados A e B, dispostos por ordem crescente, contendo N e M
elementos, respectivamente, e M maior que N, elabore um algoritmo para verificar se A está
contido em B. Nota: Procure tirar partido do ordenamento dos elementos.
4. Elabore uma função que devolve o número de elementos negativos de um vector K não
ordenado de N elementos.
Pág. 2
Grupo II
1. Complete o passo 1 e 2 do algoritmo seguinte, de forma que seja emitida a mensagem “Tem
direito a bónus”, se o funcionário respeitar os seguintes requisitos:
• a totalidade dos dias de falta, desde o início do ano, não for superior a um dia por mês
decorrido, incluindo o mês a que se refere a remuneração (MÊS). Assuma que o vector
FALTAS está preenchido com o número de dias de falta, em cada mês, do funcionário;
• ÍNDICE de produtividade for superior à produtividade média (PRODMÉDIA). Considere que
a produtividade média já foi calculada e atribuída à variável respectiva;
• a CLASSIFICAÇÃO da qualidade do trabalho desenvolvido for “Bom”.
1. [Ler o mês, o Índice e a classificação]
2. [Avaliação dos requisitos de atribuição de bónus]
2. Elabore o passo 2 do algoritmo seguinte, de forma a que seja calculada e impressa a
importância a pagar pelo cliente relativamente ao tempo de aluguer de um vídeo. O valor a
cobrar por dia é calculado da seguinte maneira:
• no primeiro e segundo dia o aluguer do vídeo é pago a 400 Esc.; no terceiro dia o aluguer
do vídeo é pago a 500 Esc.; nos restantes dias o aluguer do vídeo é pago com um
acréscimo de 200 Esc. ao valor do dia anterior, ou seja, no quarto é pago a 700 Esc., no
quinto dia a 900 Esc., etc.
1. [Ler o número de dias de permanência]
Leia(DIAS)
2. [Calcular e imprimir a importância a pagar]
Pág. 3
Grupo III
1. Suponha a adivinha do caracol que se encontra no fundo dum poço de 10 metros, subindo
cada dia 3 metros, mas descendo depois 2. Quantos dias demora o caracol a chegar ao
topo?
Elabora um algoritmo, que através duma pilha, calcule a adivinha. Cada metro deve
representar um elemento da pilha. A pilha deve ser representada usando um vector.
2. Construa um subalgoritmo que insira e remova um elemento de uma lista com dados do tipo
inteiro e elabora os seguintes algoritmos:
• Algoritmo que constrói uma lista ligada com N elementos, gerados aleatoriamente. A
operação de inserção deve ser capaz de inserir um elemento na lista ordenadamente. O
resultado final, é uma lista com elementos ordenados.
• Algoritmo que conta o número de nós de uma lista.
• Algoritmo que elimina todos os nós cuja informação tenha valores entre os dois parâmetros
inclusive.
• Algoritmo que procura um nó com uma determinada informação. Se a informação dada foi
encontrada, devolve a posição do nó, caso contrário devolve NIL. A lista não se encontra
ordenada, obrigando assim a uma pesquisa sequencial.
3. Elabora um algoritmo, que dado uma fila com N elementos do tipo inteiro, inverta a fila
através de uma pilha.
A pilha e a fila devem ser representada usando listas. Os elementos da fila devem ser
gerados aleatoriamente.
Pede-se também a implementação de todas as operações sobre filas e pilhas que achar
necessárias na resolução do problema.
Pág. 4
Grupo IV
1. Transcreva, para a sua folha de prova, os “termos” adequados ao preenchimento dos
espaços assinalados no algoritmo seguinte (c, d, e, f, g).
Este algoritmo, com base na matriz NCLIENTES, determina e imprime a(s) caixa(s) e a(s) hora(s) de
maior movimento no mês (maior número de clientes). Cada elemento da matriz NCLIENTES[I, J]
contém o número total de clientes que, num dado mês, utilizou à hora I a caixa J. Considera-se a
matriz devidamente preenchida para 15 horas de funcionamento e 40 caixas e que diferenças entre
caixas ou horas inferiores ou iguais a 20 clientes não são significativas, assumindo-se, portanto, que
têm igual movimento.
1. [Determina a hora com movimento máximo e o total de clientes por hora]
MAX_HORA Å -1
Repita para I=1,2,...,15
TOT Å 0
Repita para J=1,2,...,40
TOT Å TOT + c _________
Se TOT > MAX_HORA
Então MAX_HORA Å TOT
TOT_HORA[I] Å TOT
2. [Determina a caixa com movimento máximo e o total de clientes por caixa]
MAX_CAIXA Å -1
Repita para J=1,2,...,d______
TOT Å 0
Repita para I=1,2,...,15
TOT Å TOT + e _________
Se TOT > MAX_CAIXA
Então MAX_CAIXA Å TOT
TOT_CAIXA[I] Å TOT
3. [Imprimir a(s) hora(s) com movimento máximo]
Repita para I = 1,2, ...,15
Se MAX_HORA - f______________ ≤ 20
Então Escreva(‘A hora ‘, I, ‘ tem movimento máximo’)
4. [Imprimir a(s) caixa(s) com movimento máximo]
Repita para J = 1,2, ...,40
Se MAX_CAIXA - g______________ ≤ 20
Pág. 5
Então Escreva(‘A caixa ‘, J, ‘ tem movimento máximo’)
5. [Termina]
Saída
2. Elabora o passo 2 do algoritmo seguinte, de forma que sejam emitidas as mensagens
“ganhou um brinde tipo 1” ou “ganhou um brinde tipo 2” ou “ganhou um brinde tipo 3”,
conforme o cliente seja o décimo, o centésimo ou o milésimo cliente a passar, no mês, numa
dada caixa. Assume o seguinte:
à a caixa que o cliente utiliza é dada pela variável CAIXA;
à cada elemento da matriz NCLIENTES[I, J] contém o número total de clientes que, no mês,
utilizou, à hora I, a caixa J;
à a matriz está devidamente preenchida para 15 horas de funcionamento e 40 caixas;
à o número de clientes na matriz NCLIENTES só é incrementado após o passo 2 do
algoritmo.
1. [Ler a caixa utilizada pelo cliente]
Leia(CAIXA)
2. [Emitir a mensagem respectiva, se o cliente tiver direito a brinde]
...
3. Preencha os espaços assinalados (c, d, e, f, g, h, i, j, k), no algoritmo que se segue:
Este algoritmo, produz uma listagem de funcionários ordenada, descendentemente, por minutos de
atraso. Os vectores FUNCIONÁRIO e ATRASOS, contêm, respectivamente, os nomes dos N
funcionários da empresa e os minutos de atraso acumulados no mês por cada funcionário. Após a
execução do algoritmo, ambos os vectores ficam na ordem descrita. O vector ATRASOS não tem
valores iguais.
1. [Executar as N-1 passagens]
Repita até ao passo 4 para
PASS = 1, 2, ..., c _____
2. [Inicializar o índice máximo]
ÍNDICE_MAX Å d ______
3. [Executar uma passagem e obter o elemento com maior valor]
Repita para I = PASS+1, PASS+2, ...,N
Se ATRASOS[I] e________ ATRASOS[ÍNDICE_MAX]
Então f_______________________
Pág. 6
4. [Troca de elementos]
Se ÍNDICE_MAX ≠ PASS
Então TEMP Å ATRASOS[ÍNDICE_MAX]
g____________________________________
ATRASOS[PASS] Å TEMP
h________ Å FUNCIONÁRIOS[ÍNDICE_MAX]
i____________________________________
j____________________________________
5. [Imprimir a listagem ordenada de funcionários por minutos de atraso]
Repita para I=1, 2, ...,N
k____________________________________
6. [Termina]
Saída
4. Elabora o passo 2 do algoritmo seguinte, de forma que seja emitida uma mensagem
correspondente ao desconto a efectuar ao hóspede, caso este seja abrangido por uma ou
mais das condições de redução de preços seguintes:
à se o hóspede tem uma estadia superior a quinze dias, a redução é de 3%;
à se o hóspede tem uma estadia superior ou igual a 30 dias, a redução é de 6%;
à se é um hóspede frequente, a redução é de 8%. Considera-se hóspede frequente, um
hóspede que, nos últimos 3 meses, permaneceu pelo menos 15 dias no hotel (excluindo a
estadia corrente).
A variável NDIAS corresponde ao número de dias da estadia corrente, e o vector MESES,
com 3 elementos, considera-se devidamente preenchido com o número de dias de estadia
relativo aos últimos 3 meses. Quando um determinado hóspede é abrangido por várias
condições de descontos, é-lhe concedido o maior dos descontos. No caso de o hóspede não
ter direito a qualquer desconto, deve ser emitida a mensagem correspondente.
1. [Ler o número de dias da estadia corrente]
Leia(NDIAS)
2.
[Emitir a mensagem relativa à taxa de desconto a aplicar]
Pág. 7
Grupo V
Considere a situação decorrente da marcação de reservas de quartos de um hotel.
1. Sugira uma estrutura de dados (vector, matriz ou ficheiro) que permita guardar, em memória
secundária, o número de quartos ocupados de cada tipo (single, duplo e triplo) nos 7 dias da
semana. Apresente, no caso da estrutura de dados escolhida ser um vector ou matriz, a sua
dimensão; no caso de ser um ficheiro, o nome dos campos constituintes dos seus registos.
2. Preencha os espaços assinalados (c, ..., h), no algoritmo que se segue:
Este algoritmo, com base nas matrizes QUARTOS e TIPOS, pesquisa um quarto vago
mediante o tipo de quarto e andar desejados pelo hóspede. Cada elemento da matriz
QUARTOS[I, J] contém 1 se o quarto J do andar I está ocupado e 0 (zero) se está vago. Da
mesma forma, cada elemento da matriz TIPOS[I,J] contém 1, 2 ou 3, conforme o quarto J do
andar I seja single, duplo ou triplo, respectivamente. Consideram-se as matrizes devidamente
preenchidas para 10 andares e 50 quartos por andar. Para as variáveis TIPO_QUARTO e
ANDAR são lidos, respectivamente, o tipo de quarto e o andar desejado pelo hóspede.
Quando o hóspede não tem preferência quanto ao andar, é introduzido o valor 0 (zero) para
a variável ANDAR. Quando não existem quartos vagos deve ser emitida a mensagem
correspondente.
1.
[Ler o tipo de quarto e andar]
Leia(TIPO_QUARTO)
Leia(ANDAR)
2.
[Pesquisar um quarto vago]
Se c ______________
Então QUARTO_VAGO Å 0
IÅ1
Repita enquanto I ≤ 10 e QUARTO_VAGO = 0
JÅ1
Repita enquanto J ≤ 50 e QUARTO_VAGO = 0
Se QUARTOS[I, J] = d ______ e TIPOS[I, J] = e ______
ANDAR = I
QUARTO_VAGO = J
J Å J+1
IÅI+1
Senão QUARTO_VAGO Å 0
Pág. 8
JÅ1
Repita enquanto J ≤ f _____ e QUARTO_VAGO = 0
Se QUARTOS[ANDAR, J] = 0 e TIPOS[ANDAR, J] = TIPO_QUARTO
QUARTO_VAGO = J
g ______________
3.
[Imprimir o quarto vago]
Se ANDAR ≠ 0
Então Se QUARTO_VAGO = h _________
Então
Escreva(‘Não existe quarto vago do tipo escolhido’)
Senão
Escreva (‘No andar ‘, ANDAR, ‘ está vago o quarto ‘, QUARTO_VAGO, ‘ do
tipo escolhido’)
Senão Escreva(‘Não existe quarto vago do tipo escolhido’)
4.
[Termina]
Saída
3. Elabora o passo 2 do algoritmo seguinte, de forma que seja emitida uma mensagem
correspondente ao desconto a efectuar ao hóspede, caso este seja abrangido por uma ou
mais das condições de redução de preços seguintes:
• se o hóspede tem uma estadia superior ou igual a quinze dias, a redução é de 2%;
• se o hóspede tem uma estadia superior a 30 dias, a redução é de 5%;
• se é um hóspede frequente, a redução é de 7%. Considera-se hóspede frequente, um
hóspede que, nos últimos 4 meses, permaneceu pelo menos 15 dias no hotel (excluindo a
estadia corrente).
A variável NDIAS corresponde ao número de dias da estadia corrente, e o vector MESES,
com 4 elementos, considera-se devidamente preenchido com o número de dias de estadia
relativo aos últimos 4 meses. Quando um determinado hóspede é abrangido por várias
condições de descontos, é-lhe concedido o maior dos descontos. No caso de o hóspede não
ter direito a qualquer desconto, deve ser emitida a mensagem correspondente.
1. [Ler o número de dias da estadia corrente]
Leia(NDIAS)
2. [Emitir a mensagem relativa à taxa de desconto a aplicar]
Pág. 9