5.15. Discussion Questions

  1. Usando as fórmulas de desempenho para tabelas de dispersão dadas no capítulo, compute o número médio de comparações necessárias quando a tabela está

    • 10% cheia

    • 25% cheia

    • 50% cheia

    • 75% cheia

    • 90% cheia

    • 99% cheia

    Em que ponto você acha que a tabela dispersão é muito pequena? Explique.

  2. Modifique a função de espalhamento para strings para usar ponderação por posição.

  3. Usamos a função de espalhamento para strings que ponderava o peso dos caracteres por posição. Pense numa forma alternativa de ponderação. Quais os vieses que existem com essas funções?

  4. Pesquise sobre funções de espalhamento perfeitas. Usando uma lista de nomes (colegas de sala de aula, membros da família, etc.), gere os valores de espalhamento usando o algoritmo de hash perfeito.

  5. Gere uma lista aleatória de inteiros. Mostre como essa lista é ordenada de acordo com os seguintes algoritmos:

    • bubble sort

    • ordenação por seleção

    • ordenação por inserção

    • shell sort (você decide sobre os incrementos)

    • merge sort

    • quick sort (você decide sobre o valor do pivô)

  6. Considere a seguinte lista de inteiros: [1,2,3,4,5,6,7,8,9,10]. Mostre como essa lista é ordenada de acordo com os seguintes algoritmos:

    • bubble sort

    • ordenação por seleção

    • ordenação por inserção

    • shell sort (você decide sobre os incrementos)

    • merge sort

    • quick sort (você decide sobre o valor do pivô)

  7. Considere a seguinte lista de inteiros: [10,9,8,7,6,5,4,3,2,1]. Mostre como essa lista é ordenada de acordo com os seguintes algoritmos:

    • bubble sort

    • ordenação por seleção

    • ordenação por inserção

    • shell sort (você decide sobre os incrementos)

    • merge sort

    • quick sort (você decide sobre o valor do pivô)

  8. Considere a lista de caracteres: ['P','Y','T','H','O','N']. Mostre como essa lista é ordenada de acordo com os seguintes algoritmos:

    • bubble sort

    • ordenação por seleção

    • ordenação por inserção

    • shell sort (você decide sobre os incrementos)

    • merge sort

    • quick sort (você decide sobre o valor do pivô)

  9. Mostre estratégias alternativas para escolher o valor do pivô no quick sort. Por exemplo, “escolha o item do meio”. Implemente a nova versão do algoritmo e execute-a em um conjunto aleatório de dados. Sob qual critério sua nova estratégia se comporta melhor ou pior que a estratégia deste capítulo?

Next Section - 5.16. Exercícios de programação