Questoes modelo para teste 2

Prévia do material em texto

QUESTÕES TIPO 
PARA O 2º TESTE DE ALGORITMOS E ESTRUTURAS DE DADOS 
 
Informática; Informática (pós-lab); Inf. Saúde; Inf. Saúde (pós-lab) - 1º ano 
 
 
 
1. Estruturas Estáticas 
1. Defina as variáveis/estruturas necessárias para representar uma estrutura FIFO utilizando 
um array estático de N inteiros; 
2. Defina a operação de enqueue, que insere um inteiro na estrutura, assumindo que N é um 
valor limitado e que deve aproveitar todo o espaço livre disponível; faça a passagem de 
parâmetros que entender necessária. 
3. Defina a operação de dequeue, que remove o próximo inteiro da estrutura; 
 
 
2. Listas Ligadas 
1. Defina uma estrutura de dados para representar uma lista ligada de inteiros positivos (uma 
stack). 
2. Sobre a definição da alínea anterior: 
a) Escreva um procedimento push que permita ler e inserir um inteiro na lista ligada; 
b) Escreva um procedimento pop, que escreva e remova um elemento da lista; 
c) Escreva um procedimento conta, que conta o número de inteiros guardados na 
estrutura maiores que X (X é um valor a definir pelo utilizador). 
d) Escreva um procedimento que calcule a média dos números inteiros armazenados 
na lista ligada. 
e) Escreva um algoritmo principal que inicialize a estrutura de dados e, suportado por 
um menu de opções, permita ao utilizador executar selectivamente as operações 
das alíneas a) a d). 
 
TIPO 
apont = ^nodo 
nodo = registo 
 numero: inteiro 
 seguinte: apont 
 
VAR 
topo: apont 
opcao: inteiro 
 
Procedimento Inicializa_stack(var topo: apont) 
 apont � nil 
 
Procedimento Push (var topo: apont) 
Var novo_numero: apont 
 
 New(novo_numero) 
 Ler(novo_numero^.numero) 
 novo_numero^.seguinte � topo 
 topo � novo_numero 
 
 
Procedimento Pop (var topo: apont) 
Var a_remover: apont 
 
 Se topo <> nil Então 
 a_remover � topo 
 escrever(a_remover^.numero) 
 topo � topo^.seguinte 
 dispose(a_remover) 
 Senão 
 Escrever(“ERRO – Stack vazia”) 
 
 
Procedimento Conta(topo: apont) 
Var Aux: apont 
 Contador, X: inteiro 
 
 Escrever(“introduza o valor de X: “) 
 Ler (X) 
 Aux � topo 
 Contador � 0 
 Enquanto aux <> nil Fazer 
 Se aux^.numero > X Então 
 Contador � contador + 1 
 Aux � aux^.seguinte 
 Escrever(“o numero de inteiros superiores a “, X, “é “, contador) 
 
 
Procedimento Media(topo: apont) 
Var soma, N: inteiro 
 media: real 
 aux: apont 
 
 soma � 0 
 N � 0 
 aux � topo 
 Enquanto aux <> nil fazer 
 soma � soma + aux^.numero 
 N � N + 1 
 aux � aux^.seguinte 
 Se N > 0 Então 
 media � soma / N 
 Escrever(“A media é :”, media) 
 Senão 
 Escrever(“Lista vazia”) 
 
 
Função Menu: inteiro 
Var opcao: inteiro 
 
 Escrever(“0 – Para terminar) 
 Escrever(“1 – PUSH – acrescentar um elemento à lista”) 
 Escrever(“2 – POP – remover um elemento da lista”) 
 Escrever(“3 – Contar o número de inteiros superiores a X”) 
 Escrever(“4 – Calcular a média dos números da lista”) 
 Repetir 
 Ler(opcao) 
 Até opcao >= 0 E opcao <= 4 
 Menu � opcao 
 
 
ALGORITMO PRINCIPAL 
 
Inicializa_stack(topo) 
opcao � menu 
Enquanto opcao <> 0 Fazer 
 Caso opcao seja 
 1: push(topo) 
 2: pop(topo) 
 3: conta(topo) 
 4: media(topo) 
 opcao � menu 
 
3. Listas Ligadas 
Pretende-se armazenar numa lista ligada simples a informação relativa aos alunos de uma 
disciplina (não existe qualquer ordem entre os registos dos alunos). A lista ligada tem a 
estrutura a seguir apresentada: 
apont_nodo = ^nodo 
nodo = Registo 
 numero: inteiro 
 nome: string[30] 
 nota_final: inteiro 
 seguinte: apont_nodo 
1. Escreva um procedimento que receba um apontador para o início da lista de alunos 
referida, leia a informação de um novo aluno (número, nome e nota_final) e a acrescente à 
lista ligada (no início da lista). 
2. Desenvolva um procedimento que receba um apontador para o início da lista e devolva a 
média das notas dos alunos e o número de alunos da lista 
 
Procedimento media(inicio: apont_nodo, var media:real, N: inteiro) 
Var soma: inteiro 
 aux: apont_nodo 
 
 soma � 0 
 N � 0 
 aux � inicio 
 Enquanto aux <> nil fazer 
 soma � soma + aux^.nota_final 
 N � N + 1 
 aux � aux^.seguinte 
 Se N > 0 Então 
 media � soma / N 
 
4. Listas Ligadas 
Pretende-se implementar uma fila de espera de veículos automóveis, que aguardam 
atendimento num serviço de inspecção, suportada por uma lista ligada simples, com estratégia 
First In First Out (FIFO). A informação a armazenar para cada automóvel consiste na matrícula, 
marca, ano de registo do automóvel e nome do proprietário. À medida que os automóveis vão 
sendo inspeccionados, a informação sai da fila de espera (queue) para uma lista ligada 
simples, de automóveis já inspeccionados. 
1. Defina as estruturas de dados e variáveis necessárias. 
2. Desenvolva procedimentos/funções para: 
2.a) inserir um automóvel na fila de espera (queue). 
2.b) retirar da fila o próximo automóvel a ser atendido, transferindo-o para a lista ligada 
dos automóveis já inspeccionados 
2.c) contar quantos automóveis estão na fila de espera. 
2.d) calcular a idade média dos automóveis na fila de espera (queue). 
2.e) contar o número de automóveis de determinada marca na fila de espera. 
NOTA: deve usar parâmetros de entrada/saída nos procedimentos/funções 
3. Escreva um algoritmo principal que inicialize as estruturas de dados e selectivamente, 
suportado por um menu de opções, permita ao utilizador executar as diversas operações 
oferecidas. 
 
5. Procura e Ordenação 
Considere que um médico registou num array de registos a seguinte informação relativa aos 
seus pacientes – código_paciente, nome, morada, telefone, ano de nascimento. Considerando 
que o array se encontra ordenado pelo campo código_paciente, escreva um procedimento que 
procure a informação de determinado paciente a partir do seu código. 
 
6. Procura e Ordenação 
Considere que um professor que lecciona determinada disciplina a dois cursos registou, para 
cada aluno, a seguinte informação: numero, nome, nota final. Imagine que o professor criou 
dois arrays de registos, INF_SAUDE e SIG, onde armazenou a informação de forma 
desordenada. 
1. Defina as estruturas de dados necessárias (deve usar obrigatoriamente arrays de 
registos). 
2. Desenvolva um procedimento que receba os dois arrays e crie um terceiro array que 
contenha a informação dos dois arrays (INF_SAUDE e SIG), também de forma 
desordenada. 
3. Escreva um procedimento que receba como parâmetro de entrada um dos arrays e o 
devolva ordenado pelo campo número. 
 
7. Procura e Ordenação 
Imagine que tem um array com a informação de 800 alunos, ordenado por ordem crescente do 
número de aluno. 
1. Em que consistem os dois métodos (a) procura sequencial e (b) procura binária 
2. Caso seja necessário localizar a informação relativa a um aluno, a partir do seu número, 
que estratégia de procura lhe parece mais eficiente: (a) aplicar procura binária, ou (b) 
aplicar procura sequencial. Discuta em termos de esforço computacional os dois métodos.