5.15. Preguntas de discusión¶
Utilizando las fórmulas de desempeño de la tabla hash que se dan en el capítulo, calcule el número promedio de comparaciones necesarias cuando la tabla está
10% completa
25% completa
50% completa
75% completa
90% completa
99% completa
¿En qué punto cree usted que la tabla hash es demasiado pequeña? Explique.
Modifique la función hash para que las cadenas utilicen las ponderaciones o pesos de posición.
Utilizamos una función hash para cadenas que ponderaban los caracteres según la posición. Elabore un esquema de ponderación alternativo. ¿Cuáles son los sesgos que existen con estas funciones?
Consulte funciones hash perfectas. Usando una lista de nombres (compañeros de clase, miembros de la familia, etc.), genere los valores hash usando el algoritmo hash perfecto.
Genere una lista aleatoria de números enteros. Muestre cómo es ordenada dicha lista por los siguientes algoritmos:
ordenamiento burbuja
ordenamiento por selección
ordenamiento por inserción
ordenamiento de Shell (usted decide sobre los incrementos)
ordenamiento por mezcla
ordenamiento rápido (usted decide sobre el valor pivote)
Considere la siguiente lista de enteros: [1,2,3,4,5,6,7,8,9,10]. Muestre cómo esta lista es ordenada por los siguientes algoritmos:
ordenamiento burbuja
ordenamiento por selección
ordenamiento por inserción
ordenamiento de Shell (usted decide sobre los incrementos)
ordenamiento por mezcla
ordenamiento rápido (usted decide sobre el valor pivote)
Considere la siguiente lista de enteros: [10,9,8,7,6,5,4,3,2,1]. Muestre cómo esta lista es ordenada por los siguientes algoritmos:
ordenamiento burbuja
ordenamiento por selección
ordenamiento por inserción
ordenamiento de Shell (usted decide sobre los incrementos)
ordenamiento por mezcla
ordenamiento rápido (usted decide sobre el valor pivote)
Considere la lista de caracteres: [
'P','Y','T','H','O','N']. Muestre cómo esta lista es ordenada por los siguientes algoritmos:ordenamiento burbuja
ordenamiento por selección
ordenamiento por inserción
ordenamiento de Shell (usted decide sobre los incrementos)
ordenamiento por mezcla
ordenamiento rápido (usted decide sobre el valor pivote)
Elabore estrategias alternativas para elegir el valor pivote en el ordenamiento rápido. Por ejemplo, elija el ítem central. Re-implemente el algoritmo y luego ejecútelo en conjuntos de datos aleatorios. ¿Bajo qué criterios su nueva estrategia funciona mejor o peor que la estrategia de este capítulo?