Resolução de Prova de Avaliação:
//pergunta 1, 2a. chamada, 1998/99, JCL
// erros
6 : x(x1), y(y1) { r= r1; }
17 Circulo c2(1.0);
// resultados
28.26 // 3.14 * 3.0 * 3.0
12.56 // 3.14 * 2.0 * 2.0
//pergunta 2, 2a. chamada, 1998/99, JCL
template<class T>
void Queue<T>::Retira(T valor, Queue<T> & f) const
{
T x;
// ver fig 6.5 para calcular o número de elementos
da fila
for (int i= (MaxSize+rear-front)%MaxSize); i>0; i--)
{
Delete(x);
if (x != valor )
f.Add(x);
else Add(x);
}
};
//pergunta 3, 2a. chamada, 1998/99, MTA
template<class T>
int BinaryTree<T>::NoNos(T v)
{
return NoNos(root, v);
}
template<class T>
int BinaryTree<T>::NoNos(BinaryTreeNode<T> *t, T v)
{
int count=0;
if(t)
{
if(t->data > v)
count++;
count += NoNos(t->LeftChild, v)
+ NoNos(t->RightChild, v);
}
return count;
}
//pergunta 4, 2a. chamada, 1998/99, MTA
1. Estruturas de Dados:
uma tabela de Hash, com função fhash(), em que cada
posição da tabela tem um campo numérico inicializado
a zero no arranque do programa, e uma fila (f) para ir guardando os valores
que se pretende preservar na saída.
2. Algoritmo:
enquanto existirem valores de entrada
{
le valor para uma variavel do tipo T;
se fhash(valor)==0
f.Add(valor);
fhash(valor)++;
}
Sempre que se recebe um valor de entrada, esse valor é utilizado
como chave para aceder á tabela de Hash; se o campo numérico
da posição acedida através dessa chave tiver o valor
0, então é porque se trata da 1a. ocorrência do valor
de entrada que se está a analisar e nesse caso este é adicionado
á fila e o campo numérico da posição acedida
da tabela de Hash é colocado a 1; se o campo numérico da
posição acedida já tiver um valor diferente de zero,
então é porque se trata de uma ocorrência duplicada
do valor em análise e nesse caso ele não é colocado
na fila de saída.
3. Nota: Em vez de uma tabela de Hash também se poderia utilizar uma lista ligada para ir armazenando os valores à medida que iam chegando, fazendo nessa mesma altura a detecção de ocorrências duplicadas ou não do valor de entrada em análise e tomando as acções necessárias para passar ou não os valores para a fila ligada de saída. A complexidade temporal do algoritmo que detecta o no. de ocorrências do valor em análise seria diferente. Para cada valor de entrada seria necessario percorrer a lista ligada desde o nó inicial e até se verificar uma das duas seguintes condições: encontrar um nó cujo campo data-valor tivesse um valor igual ao valor de entrada em análise, ou chegar ao fim da lista. Em cada nó da lista ligada, o campo data teria que ser uma estrutura de dados com os seguintes componentes: campo genérico T para guardar o valor de entrada (data-valor) e campo numérico para guardar o número de ocorrências do respectivo valor de entrada (data-NumeroDeOcorrencias).