Uma certa função hash, h(x), aplicada à chave, coloca registos com as chaves: 62, 79, 81, 12, 54, 97, 34, numa tabela hash.

As colisões são tratadas por uma função re-hash, r(x), que recebe como argumento o resultado da aplicação da função hash.

Os valores-chave são introduzidos na ordem indicada acima, para produzir a seguinte tabela

Quais são as funções h(x) e r(x), respectivamente?

A eficiência da codificação hash depende de

I.   O número de colisões que ocorre

II.  O tamanho dos dados na lista

III. O método de lidar com as colisões

Uma array contém dados que foram inseridos através da codificação hash.

Como é que um dado item deve ser pesquisado nesta array?

As chaves: 10, 28, 2, 7, 45, 25, 40, 29, são para ser inseridas na seguinte tabela hash

A função hash é key % 11. As colisões são resolvidas pelo método "hash-and-search" (Open Addressing and Linear Probing).

Em que célula irá a chave 29 ocupar, eventualmente?

O fragmento de código seguinte efectua uma pesquisa sequencial para determinar se um dado inteiro, val, está ou não armazenado numa array com elementos \tiny a[0] a a[n-1]

    1 intl i = 0;

    2 while (<expressão>)

    3    i++;

    4 if (i == n)

    5    return -1;      // val não encontrado

    6 else

    7    return i;       // val encontrado na posição i

Qual das seguintes expressões deverá substituir <expressão>, nesse fragmento, para que o referido algorítmo funcione como previsto?

I.   val != a[i]

II.  i < n && val == a[i]

III. val != a[i] && i < n

IV.  i < n && val != a[i]

V.   i < n || val != a[i]

Um algorítmo para pesquisar por um dado valor x em grandes arrays ordenadas, compara x com cada terceiro elemento da array até que um, maior ou igual a x seja encontrado. Quando um valor maior é encontrado, o algorítmo compara x com os dois elementos anteriores.

Se a array estiver ordenada por ordem ascendente, qual das seguintes expressões descreve os casos em que o algorítmo utiliza menos comparações, para encontrar x, que aquelas utilizadas numa pesquisa binária?

É feita uma pesquisa binária numa array com 600 elementos.

No pior caso, qual dos seguintes números representa a melhor aproximação do número de iterações do algorítmo?

Suponha uma classe SomeClass onde está definida uma variável \tiny a[size]

    1 template<int size=10>

    2 class SomeClass {

    3 public:

    4    ...

    5    int binSearch(int key);

    6 private:

    7    int length;

    8    int a[size];

    9 };

Considere o seguinte método binSearch() dessa classe

   12 // Efectua uma pesquisa binária por uma chave numa array.

   13 // Pré-condição:    A array a[0]...a[a.length-1] está ordenada 

   14 //                  por ordem ascendente.

   15 // Pós-condição:    Devolve index tal que a[index] == key.

   16 //                  Se key não está em v, então devolve -1.

   17 

   18 template<int size>

   19 int SomeClass<size>::binSearch(int key)

   20 {

   21    int low = 0;

   22    int high = length - 1;

   23    while (low <= high)

   24    {

   25       int mid = (low + high)/2;

   26       if (a[mid] == key)

   27          return mid;

   28       elseif (a[mid] < key)

   29          low = mid + 1;

   30       else

   31          high = mid - 1;

   32    }

   33    return -1;

   34 }

A pesquisa binária será efectuada na seguinte lista

Na procura pelo elemento 27, o intervalo de pesquisa depois da primeira passagem pelo ciclo while, será

Suponha uma classe SomeClass onde está definida uma variável \tiny a[size]

    1 template<int size=10>

    2 class SomeClass {

    3 public:

    4    ...

    5    int binSearch(int key);

    6 private:

    7    int length;

    8    int a[size];

    9 };

Considere o seguinte método binSearch() dessa classe

   11 // Efectua uma pesquisa binária por uma chave numa array.

   12 // Pré-condição:    A array a[0]...a[a.length-1] está ordenada 

   13 //                  por ordem ascendente.

   14 // Pós-condição:    Devolve index tal que a[index] == key.

   15 //                  Se key não está em v, então devolve -1.

   16 

   17 template<int size>

   18 int SomeClass<size>::binSearch(int key)

   19 {

   20    int low = 0;

   21    int high = length - 1;

   22    while (low <= high)

   23    {

   24       int mid = (low + high)/2;

   25       if (a[mid] == key)

   26          return mid;

   27       elseif (a[mid] < key)

   28          low = mid + 1;

   29       else

   30          high = mid - 1;

   31    }

   32    return -1;

   33 }

A pesquisa binária será efectuada na seguinte lista

O que é que ficará armazenado em y depois de executado o seguinte?

   32 int y = binSearch(4);

Considere uma classe Sorter onde está definida uma variável \tiny a[size]

    1 template<class T, int size=10>

    2 class Sorter {

    3 public:

    4    ...

    5    void insertionSort();

    6 private:

    7    int length;

    8    T a[size];

    9 };

Considere o método insertionSort() dessa classe

   11 // Pré-condição:    a[0]...a[a.length-1] é uma array de elementos

   12 //                  T não ordenada. 

   13 // Pós-condição:    A array a está ordenada por ordem decrescente.

   14 

   15 template<class T, int size>

   16 void Sorter<T,size>::insertionSort()

   17 {

   18    for (int i = 1; i < length; i++) 

   19    {

   20       T temp = a[i];

   21       int j = i - 1;

   22       while (j >= 0 && temp > a[j])

   23       {

   24          a[j+1] = a[j];

   25          j--;

   26       }

   27       a[j+1] = temp;

   28    }

   29 }

Quando ordenada em ordem descendente, utilizando o método insertionSort(), qual das listas seguintes necessita do maior número de mudanças de posição dos seus elementos?