Exercícios

Aula prática nº 11


Exercícios

  1. Considere um programa que lê números em vírgula flutuante de precisão simples  até o utilizador escrever o número -1. Este programa deve depois realizar as seguintes funcionalidades (pela mesma ordem por que estão descritas):
    1. Escreve o número de elementos lidos;
    2. Escreve os elementos inseridos pelo utilizador por ordem crescente de valor;
    3. Escreve o maior e o menor dos elementos inseridos pelo utilizador;
    4. Realiza um ciclo onde verifica se um números inserido agora pelo utilizador já tinha sido inserido anteriormente pelo utilizador. Este ciclo termina quando o utilizador escreve o número -1.
Realize este programa utilizando o ADT de 1ª ordem Tabela de Símbolos.
  1. Realize o ADT de 1ª ordem Tabela de Símbolos utilizando árvores binárias de procura (BST).
  2. Acrescente a funcionalidade de devolver o maior e menor elementos a este ADT e concretize estas funcionalidades de forma eficiente no caso de utilizar BST.
  3. Seria eficiente utilizar uma tabela de dispersão para concretizar este ADT?
  4. Realize uma concretização deste ADT utilizando uma tabela de dispersão com resolução por encadeamento externo.
  5. Compare as duas formas de concretização do ADT Tabela de Símbolos utilizando o cliente realizado na primeira alínea.
  6. Usando código disponível nos acetatos da disciplina, concretize o ADT Tabela de Símbolos com a mesma interface do anterior, mas que, internamente, use aleatoriedade para inserir um elemento na raiz de uma árvore com probabilidade 1/(1+N).
  7. Compare o desempenho da BST com a BST aleatorizada quando se inserem números inteiros, entre 0 e N (por ordem), para N=10000 e N=100000.