7256 Algoritmos e estruturas de dados

Exercícios / Tabelas

1. Considere a adição dos pares chave-valor (124, pedro), (534, joao), (125, maria), (567, carlos), (435, paulo), (444, jorge) em uma tabela de tamanho 7, que utilize a função de hash $h(k) = k \mod 7$. Desenhe a tabela resultante se o método de tratamento de colisões utilizado for a) posição consecutiva livre, b) lista encadeada.

2. Dado uma lista de números, defina uma função que devolva um dicionário que associe cada elemento de uma lista com a primeira posição que ele ocorre na lista. Exemplo

   >>> d = primeira_posicao([3, 2, 4, 2, 4, 4, 3])
   >>> d == {3: 0, 2: 1, 4: 2}
   True

3. Defina uma função semelhante a do exercício anterior, mas que considere a última posição.

4. Dado uma lista de números, defina uma função que devolva um dicionário que associe cada elemento da lista com as posições que ele ocorre na lista. Exemplo

   >>> d = posicoes([3, 2, 4, 2, 4, 4, 3])
   >>> d == {3: [0, 6], 2: [1, 3], 4: [2, 4, 5]}
   True

5. Dado uma lista de números, defina uma função que devolva um dicionário que associe cada elemento da lista com a quantidade de elementos menores que ele na lista. Exemplo

   >>> d = conta_menores([5, 3, 2, 8, 4])
   >>> d == {5: 3, 3: 1, 2: 0, 8: 4, 4: 2}
   True