Gabarito disponível
Suponha que uma função hash seja escolhida aleatoriamente de uma coleção universal de funções hash e usada para aplicar hash a n chaves em uma tabela T de tamanho m, usando encadeamento para resolver as colisões. Se a chave k não estiver na tabela, o comprimento esperado E [nₕ₍ₖ₎] é no máximo o fator de carga
Resolução comentada
Para chave fora da tabela, o comprimento esperado da lista é no máximo o fator de carga α = n/m.
Com hash universal e encadeamento, a lista T[h(k)] de uma chave k ausente tem comprimento esperado igual ao número esperado de chaves colidindo com k, que é no máximo n/m. Esse valor é o fator de carga α.
Análise das alternativas
B) 1 + α é o limite para uma chave presente na tabela (ou o custo total da busca, incluindo a função hash). C), D) e E) não correspondem a nenhum resultado do teorema.
Referência: Cormen et al., Algoritmos, cap. 11 (tabelas hash, hashing universal).
Resolução comentada do VaiConcursos.