Download Ejercicios sobre estructuras de datos

ANÁLISIS DE ALGORITMOS
Hoja de ejercicios No.
I. En informática es usual que se tenga una colección de elementos sobre la cual se debe proveer una serie de operaciones.
En los siguientes ejercicios se usa n para referirse al número de elementos de la colección y se supone que los elementos
poseen una llave primaria o clave que los identifica de manera única y que permite ordenarlos. En cada uno de los
siguientes casos, estime el orden de complejidad temporal de cada una de las operaciones, según las alternativas de
representación dadas.
a) Un diccionario es una colección de elementos sobre la cual se pueden efectuar solamente las operaciones de inserción,
eliminación y búsqueda de elementos. Además existe la posibilidad de listar (producir un listado) los elementos de forma
ordenada, de menor a mayor. Complete la tabla siguiente:
REPRESENTACIÓN
OPERACIONES
Inserción Eliminación
Listar
Búsqueda
arreglo desordenado que usa siempre las primeras n casillas
arreglo ordenado que usa siempre las primeras n casillas
Nodos sencillamente encadenados y sin orden
Nodos sencillamente encadenados y ordenados
Nodos organizados en forma de árbol binario ordenado
Nodos organizados en forma de árbol binario ordenado y equilibrado
b) Las listas (o secuencias) se usan para almacenar colecciones en las que los elementos se organizan linealmente de
acuerdo a su posición. Sobre una lista son usuales múltiples operaciones y variadas representaciones. Complete la siguiente
tabla:
REPRESENTACIÓN
Invertir
Hallar el
k­esimo
Igualdad
Lista representada con un arreglo que usa siempre las primeras n casillas, sin
orden
Lista representada con un arreglo que usa siempre las primeras n casillas, con
orden
Lista representada con nodos sencillamente encadenados y sin orden
Lista representada con nodos sencillamente encadenados y con orden
Lista representada con nodos doblemente encadenados y sin orden
Lista representada con nodos doblemente encadenados y con orden
c) Las pilas y las colas son colecciones en las cuales las inserciones y eliminaciones se manejan con política LIFO y FIFO,
respectivamente. Las operaciones permitidas son insertar, eliminar y consultar un elemento distinguido (el tope en la pilas y
la cabeza en las colas). Estime el orden de complejidad de cada una de las operaciones de una pila y una cola según las
siguientes alternativas de representación. Complete la tabla siguiente:
REPRESENTACIÓN
Inserción
OPERACIONES
Eliminación
Consultar
(tope/cabeza)
(tope/cabeza)
Pila representada con un arreglo que usa siempre las primeras n casillas
Pila representada con nodos sencillamente encadenados
Cola representada con un arreglo que usa siempre las primeras n casillas
Cola representada con arreglo administrado de manera circular
Cola representada con nodos sencillamente encadenados
1
d) Los árboles se usan para representar colecciones ordenadas por clave, de forma no lineal sino jerárquica. En los árboles
binarios los elementos se organizan de tal manera que cada elemento puede tener a lo más dos sucesores (hijos). Complete
la siguiente tabla para el caso de los árboles binarios.
REPRESENTACIÓN
Hallar el
k­esimo
OPERACIONES
Insertar
Eliminar
Buscar
Nodos sencillamente encadenados y con orden
Nodos sencillamente encadenados con orden y equilibrados
Memoria estática (tablas)
e) Las colas de prioridad son colecciones, similares a las colas, en las cuales cada elemento tiene asociada una prioridad.
En ellas se pueden efectuar las operaciones de inserción, eliminación y consulta del elemento con menor prioridad (o
mayor, según se quiera) y cambio de prioridad de un elemento existente. Los montones (en inglés, heaps) se usan para
representar eficientemente las colas de prioridad. Un montón es un árbol binario con dos propiedades, una de forma y otra
de orden:
•
La propiedad de forma se ilustra en la siguiente figura. El último nivel del árbol está probablemente incompleto en
su parte derecha:
•
La propiedad de orden establece que todo elemento del árbol es menor (o mayor, si se quiere) que sus hijos.
Complete la siguiente tabla en la cual se debe analizar algunas alternativas para representación de colas de prioridad:
REPRESENTACIÓN
Inserción
OPERACIONES
Consulta del Eliminación
mínimo
del mínimo
Cambio de
prioridad
Arreglo ordenado por prioridad que usa siempre las primeras n
casillas
Arreglo desordenado que usa siempre las primeras n casillas
Montón implementado con nodos sencillamente encadenados
Montón implementado con un arreglo
f) Las tablas de hash o tablas de dispersión se usan para representar colecciones sobre las cuales se efectúan únicamente
las operaciones de inserción, eliminación y búsqueda. Además, en ningún momento se requiere listar los elementos de
acuerdo a su clave. ¿Qué implementación usaría si se quiere que todas las operaciones sobre la tabla tengan complejidad
temporal O(1)?.
2