Download Ejercicios sobre estructuras de datos
Document related concepts
no text concepts found
Transcript
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 kesimo 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 kesimo 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