Tema4 PC

Tema 4
Programación Científica y HPC
Estructuras de datos
Índice
Esquema 3
Ideas clave 4
4.1. Introducción y objetivos 4
4.2. Arrays y listas 7
4.3. Pilas y colas 13
4.4. Tablas hash 16
4.5. Grafos 18
© Universidad Internacional de La Rioja (UNIR)
4.6. Árboles 21
4.7. Montículos 25
4.8. Referencias bibliográficas 28
4.9. Cuaderno de ejercicios 29
A fondo 36
Test 37
Esquema

3
Tema 4. Esquema
Ideas clave
4.1. Introducción y objetivos
Para el diseño de algoritmos eficientes es fundamental usar estructuras de datos

bien diseñadas y adecuadas para el que se pretende implementar. Las estructuras
de datos definen agrupaciones de estos, que se encuentran organizados de una
determinada manera y cuya manipulación se define mediante unas operaciones
relacionadas con la naturaleza intrínseca de la estructura.
El concepto de estructura de datos es independiente del lenguaje con el que se

implementa, es decir, autónomo de los constructores del lenguaje que se utilizan
para su ejecución. Por ello, es importante determinar las características de una
estructura de datos, el tipo de elementos, las relaciones definidas sobre ellos y las
operaciones que se permite que soporte la estructura. Estas operaciones suelen ser
de consulta y modificación.
El nivel de abstracción de los lenguajes ha permitido soportar nuevas formas de

formalización del concepto de estructura de datos que permiten, no solo definirla,
sino también restringir las operaciones que se pueden realizar sobre ella para evitar
manipulaciones conceptualmente incompatibles con la estructura diseñada.
Estas formas de conceptualización con un nivel de abstracción mayor son los tipos
abstractos de datos (TAD). Se puede decir que un tipo abstracto de datos se necesita
para establecer el tipo de los elementos que lo componen, las operaciones de
manipulación y, algo muy importante, la semántica de sus operaciones. Todo

aplicable al concepto de estructura de datos.
Las formas de definir los TAD son variados. Lo importante es poder separar la
especificación de la implementación, es decir, el uso de un TAD no debe depender

4
Tema 4. Ideas clave
del conocimiento de la estructura del lenguaje usada para la implementación ni de
la implementación de las operaciones, que se supone garantizan su uso de acuerdo
con su semántica.
Por tanto, para usar un TAD es suficiente con conocer su interfaz, esto es, su nombre
y los nombres y parámetros de sus operaciones.
La estructura de un TAD se podría describir de la siguiente forma:
Figura 1. Estructura de un TAD. Fuente: elaboración propia.
En los lenguajes orientados a objetos, la implementación de los TAD se realiza

mediante las clases, que cuentan con todos los elementos necesarios para soportar
su conceptualización. Las propiedades de las clases permiten la ocultación de los
detalles de implementación; el conocimiento del uso del TAD, garantiza que la

manipulación se realiza de acuerdo con la semántica del tipo abstracto de datos y la
encapsulación de los datos y sus operaciones en una única unidad o módulo, es decir,
la clase. Esto redunda en un alto grado de cohesión y un débil acoplamiento con otras
clases.

5
Tema 4. Ideas clave
Todas las operaciones necesarias y nada más que las necesarias se definen en
la clase. Se tiene, por tanto, un TAD completo y utilizable.
En este tema se abordará la manera de usar algunas estructuras y formas de

implementación más avanzadas con el código de las implementaciones.
Características especiales sobre objetos
En Python todos los objetos son manejados con referencias. Por tanto, asignar un
objeto a otro es equivalente a que dos variables de objetos son accesibles mediante
la misma referencia. Esto implica que los cambios que se hagan en un objeto se
realizan también en el otro. La comprobación de si dos objetos son iguales debería,
así mismo, realizarse de forma que se hagan comprobaciones en profundidad, es
decir, se compruebe el contenido no la referencia.
La asignación de variables objeto tiene como efecto que las dos variables
referencian al mismo objeto.
Ejemplo 1. Copia de variables de objeto y sus resultados
Se crean dos listas, l2 como copia de l1. En realidad, la l1 y l2 son el mismo

objeto (se comprueba con l1 is l2). Cualquier cambio que se realice en una
de las variables tendrá efecto sobre la otra. Observe el siguiente código:
Figura 2. Código del ejemplo 1. Fuente: elaboración propia.

6
Tema 4. Ideas clave
Se debe solucionar este problema haciendo uso de la función copy(), que permite
crear una verdadera copia de una lista, una en profundidad. Se crea l3 vacía, pero
luego se hace una copia del l1, se observa que ahora son objetos distintos y no se
producen efectos colaterales. Observe el siguiente código:
Figura 3. Código con copy(). Fuente: elaboración propia.
Recuerden, es importante definir en las clases, métodos que hagan copias en

profundidad y redefinir el método __eq__, que es el que se ejecuta al
comprobar la igualdad de dos objetos, para que compruebe la igualdad en
profundidad.
4.2. Arrays y listas
Arrays
El array o vector es una estructura que se implementa en la mayoría de los lenguajes

por defecto, ya que se caracteriza porque es una colección ordenada de elementos

7
Tema 4. Ideas clave
del mismo tipo, que tiene tamaño fijo y al que se puede acceder por su índice de tipo
entero.
Algunos lenguajes, como Ada, permiten la indexación mediante tipos discretos como
el tipo carácter.
Implementación de arrays en Python
Aunque las listas en Python se manejan de forma similar a los vectores,

conceptualmente, no se pueden considerar como tales porque, permiten almacenar
elementos de distinto tipo y además no tienen tamaño fijo.
Para trabajar con vectores en Python se cuenta con la biblioteca array o bien con los
del módulo Numpy. Nosotros veremos la primera opción, que presenta algunas
limitaciones.
La clase array de la biblioteca array
Un objeto de esta clase solo puede contener datos del mismo tipo, que deben ser
numéricos o datos primitivos de tamaño fijo. El tipo de datos se debe especificar en
el momento de la creación del array, mediante un código, los cuales se muestran en
la Tabla 1.

8
Tema 4. Ideas clave
Tabla 1. Código de tipo de dato para definir un array. Fuente: elaboración propia.
En la Figura 4 se muestra la creación de un vector de enteros y el uso de algunas

funciones y en la Figura 5 la salida obtenida.
Figura 4. Uso de los arrays de la biblioteca array. Fuente: elaboración propia.

9
Tema 4. Ideas clave
Figura 5. Salida de la ejecución de la Figura 4. Fuente elaboración propia.
Ernesto Rico Schmidt muestra en su página ejemplos del uso de array en Python.
Listas
Una lista es una colección de elementos del mismo tipo dispuestos en un cierto
orden. El número de elementos de la lista no está determinado.
Las operaciones que debe soportar son:
 Creación de la lista. Se construye la estructura que la soporta, se crea vacía.
 Operaciones de consulta:
• Comprobar si la lista está vacía.
• Comprobar si existe un elemento.
• Consultar el primer elemento.
• Consultar el último elemento.
• Obtener el siguiente y el anterior de un elemento.
• Longitud de la lista.
 Operaciones de inserción:
• Se puede insertar al principio o al final.
• Insertar en una posición.
 Operaciones de eliminación:

10
Tema 4. Ideas clave
• Borrar un elemento de la lista.
• Borrar la lista completa.
Implementación en Python
En Python se cuenta con la clase list que por su implementación permite todas las
operaciones indicadas.
Python permite que las listas tengan elementos de distinto tipo, algo que va contra
la filosofía del tipo abstracto que se quiere implementar. Por tanto, en la creación de
las listas se deberá especificar el tipo de los elementos que se van a crear,
impidiendo que se cree una lista heterogénea.
La definición del TAD que se va a realizar va a separar la implementación de la

especificación, ocultando la estructura subyacente y las funciones definidas para ella
y manejando los datos como se espera de un TAD lista.
Se trata de subir de nivel de abstracción.


11
Tema 4. Ideas clave
Ejemplo 2. Implementar un tipo abstracto de datos Lista
Figura 6. Implementación del TAD Lista. Fuente: elaboración propia.


12
Tema 4. Ideas clave
4.3. Pilas y colas

Pilas
Una pila es una colección de elementos que no se puede recorrer. El número de

elementos de la pila no está determinado. Su comportamiento se describe como:
«último en entrar, primero en salir». Por lo tanto, las operaciones que debe soportar
son muy pocas, estas son:
 Creación de la pila. Se construye la estructura que la soporta, se crea vacía.

• Obtener cima de la pila, el último elemento que entró.
• Comprobar si la pila está vacía.

13
Tema 4. Ideas clave
 Operaciones de modificación:
• Apilar: inserta un elemento en la cima de la pila.
• Desapilar: elimina el elemento de la cima de la pila y, además, obtiene su valor
Nuevamente se va a utilizar una lista para implementar una pila, pero nuevamente
se van a restringir las operaciones de acuerdo con la semántica del tipo.
La definición del TAD que se va a implementar va a separar la implementación de la

Ejemplo 3. Implementar un tipo abstracto de datos Pila

Figura 7. Implementación del TAD Pila. Fuente: elaboración propia.

14
Tema 4. Ideas clave
Colas
Una cola es una colección de elementos que no se recorren. El número de elementos

de la cola no está determinado. El comportamiento de la cola se describe como:
«primero en entrar, primero en salir». Por tanto, las operaciones que debe soportar
son muy pocas:
 Creación de la cola. Se construye la estructura que la soporta, se crea vacía.
• Obtener primer elemento de la cola.
• Comprobar si la cola está vacía.
 Operaciones de modificación:
• Encolar: inserta un elemento al final de la cola.
• Desencolar: elimina el primer elemento de la cola y además obtiene su valor.
Nuevamente se va a utilizar una lista para implementar una cola, pero como en el
caso anterior, se van a restringir las operaciones de acuerdo con la semántica del tipo.
La definición del TAD que se va a implementar, va a separar la implementación de la


15
Tema 4. Ideas clave
Ejemplo 4. Implementar un tipo abstracto de datos Cola
Figura 8. Implementación del TAD Cola. Fuente: elaboración propia.
4.4. Tablas hash
Una tabla hash es una estructura de datos para almacenar un gran número de datos,
un contenedor asociativo tipo diccionario. Estas ofrecen operaciones de búsqueda
muy eficientes.
Se almacenan conjuntos de pares <clave,valor>, de forma que la clave es única para

cada elemento de la tabla o entrada de la tabla. Esta funciona transformando la
clave con una función en su hash que, básicamente, es el número que identifica la
posición donde la tabla localiza el valor deseado.

16
Tema 4. Ideas clave
Figura 9. Estructura tabla hash. Fuente: https://pythondiario.com/2018/06/tabla-hash-en-
python.html
Los diccionarios de Python se comportan como tablas hash y, por ello, los tipos de
datos que pueden usarse como clave tienen que ser tipos de los que se pueda
obtener su código hash, que en definitiva es su representación unívoca.
Los tipos de datos de Python de los que se puede obtener un hash son los datos de
tipo str, float, int o bool.
Las operaciones con las que debe contar, como mínimo, una de estas tablas son las
siguientes:
 Operación de inserción. Se debe proporcionar la clave y el valor.

 Operaciones de búsqueda por clave.
 Operaciones de modificación del valor.
Como ya se ha mencionado, los diccionarios en Python son verdaderas tablas hash.

Sin embargo, siguiendo la filosofía de todo el tema y para ocultar los detalles de
implementación, se podría implementar un TAD Tabla Hash e, incluso, dotarlo de más
funciones.

17
Tema 4. Ideas clave
Por tanto, la definición del TAD que se va a implementar va a separar la
implementación de la especificación, ocultando la estructura subyacente y las
funciones definidas para ella y manejando los datos como se espera de un TAD Lista.
Ejemplo 5. Implementar un tipo abstracto de tabla hash
Figura 10. Implementación del TAD Tabla Hash. Fuente: elaboración propia.
4.5. Grafos
De manera informal, se puede decir que un grafo es un conjunto de nodos unidos

por aristas. Los grafos pueden ser dirigidos, si las aristas logran ser representadas por
flechas que indican la dirección del enlace o no dirigidos. Las secuencias de aristas
forman caminos entre nodos con ciclos o no.

18
Tema 4. Ideas clave
Un grafo se considera conexo si, desde cualquier nodo, se puede encontrar un camino
a todos los nodos del grafo.
Un grafo se puede implementar de dos formas:
Grafos con matriz de adyacencia
La estructura del grafo estará formada por una lista de los nodos con su información
y una matriz de adyacencia cuadrada con valores lógicos, en la que cada elemento
[i][j] que tenga valor True representa la arista del nodo i al j.
En esta implementación, la complejidad en tiempo de la función para obtener los

nodos conectados con un nodo es θ (número de nodos).
Ejemplo 6. Implementación de un tipo abstracto de grafo dirigido
Figura 11. Clase grafo dirigido. Implementación I. Fuente: elaboración propia.


19
Tema 4. Ideas clave
Tengan en cuenta que:
 El grafo puede tener peso en las aristas, por lo que la matriz de adyacencia tomaría
otros valores que no sean lógico.
 Si el grafo no fuese dirigido, la función que obtenga los conectados debería buscar
en las filas y las columnas.
 Se deberían implementar las funciones de copia, __eq__ y __str__ como en los
otros ejemplos.
Grafo con información de nodos vecinos.
En este caso, el grafo tendrá la estructura de una matriz en la que cada elemento
contiene el valor y los nodos conectados con él (también se suelen llamar vecinos).
Esta implementación usa menos espacio que la anterior.
Figura 12. Clase grafo. Implementación II. Fuente: elaboración propia.

Se deben tener en cuenta las mismas consideraciones que en la implementación

anterior, que se dejan como ejercicio. Por supuesto, los grafos se podrían
implementar de forma eficiente haciendo uso de los arrays de NumPy.

20
Tema 4. Ideas clave
4.6. Árboles
Los árboles son un tipo de grafos con algunas características especiales.
Los árboles que se van a tratar en este apartado son los que se conocen como árboles
con raíz, es decir, los que tiene un nodo especial, el raíz. Estos presentan una
organización similar a un árbol jerárquico con la siguiente estructura:
 Un nodo superior que no es hijo de nadie, el nodo raíz.

 Nodos hoja, que no tienen hijos.
 Nodos internos, con hijos.
Aunque en la definición no se indica, se considera que las ramas de los árboles con
raíz se encuentran ordenados de izquierda a derecha.
Existen diferentes tipos de árboles con raíz de acuerdo con distintos criterios. Según
el número de hijos que puede tener cada nodo o por las alturas de los subárboles de
cada nodo.
La altura de un nodo es el número de aristas que se encuentra en el camino

más largo desde ese nodo a una hoja. La profundidad de un nodo es el
número de aristas que existen desde el nodo raíz hasta él. El nivel de un nodo
es igual a la altura de la raíz, menos la profundidad de este.
En este apartado se tratará la estructura e implementación de un árbol binario, que

es una de las estructuras más usadas. Más concretamente, se tratarán los árboles
binarios ordenados como el que se muestra en la Figura 13.

21
Tema 4. Ideas clave
Figura 13. Árbol binario de búsqueda. Fuente:
https://es.wikipedia.org/wiki/Árbol_binario_de_búsqueda
Las operaciones que se definen para este tipo de árboles son:
Figura 14. Operaciones que definen a los árboles binarios. Fuente: elaboración propia.
Cabe aclarar que, si solo se permite la inserción ordenada, comprobar si está

ordenada puede no ser necesaria. Además, en un árbol ordenado los recorridos
preorden y postorden no tienen mucho sentido.
La implementación presentada es una implementación recursiva.

22
Tema 4. Ideas clave
Para entender mejor esta implementación pueden ver el vídeo del campus virtual
Árboles binarios ordenados en Python. Implementación recursiva.
Figura 15. TAD árbol binario ordenado. Fuente: elaboración propia.


23
Tema 4. Ideas clave

24
Tema 4. Ideas clave
4.7. Montículos
El montículo es un tipo especial de árbol con raíz que se puede implementar con
una matriz. Esta estructura es muy usada e incluso existe un método de ordenación
por montículo. También se aplica para la gestión de colas de prioridad.
Un montículo es un árbol binario esencialmente completo. Esto quiere decir que

todos sus nodos internos tienen dos hijos, con una posible excepción de un nodo
especial. Este nodo está situado en el nivel 1 y posee un hijo izquierdo, las hojas están
en el nivel 0 o en el 0 y 1.
Figura 16. Árbol binario esencialmente completo. Fuente:

http://www.udb.edu.sv/udb_files/recursos_guias/informatica-ingenieria/programacion-
iv/2019/ii/guia-7.pdf
Una de las características principales del montículo es que cada uno de sus nodos
tiene un valor que es mayor o igual que los valores de sus hijos. Esta se conoce como
la propiedad del montículo.
La propiedad del montículo de máximos asegura que el valor de todo nodo

interno es mayor o igual que todos los valores de todos los nodos de sus
subárboles. Si el montículo es de mínimos garantiza la propiedad contraria.

25
Tema 4. Ideas clave
Un montículo puede representarte mediante un array según el siguiente
procedimiento:
 Si el árbol tiene una altura k, en esta se encuentra 1 nodo que es, además, la raíz.
 En el nivel k-1, habrá dos nodos.
 Y, de forma sucesiva, se puede decir que hay 2𝑘 − 1 nodos.
 En el nivel 0 habrá al menos uno, pero no más de 2𝑘 .
Por tanto, los nodos de profundidad k, se pondrán en el array de izquierda a derecha,

en las posiciones 2𝑘 , 2𝑘 + 1, 2𝑘+1 − 1.
Otra de las cuestiones que se puede considerar para saber cómo usar el array es que
cada nodo que se encuentre en la posición p, tiene a su hijo izquierdo en la posición
2𝑝 y su hijo derecho en la posición 2𝑝 + 1.
El resultado se muestra en la Figura 17.

Figura 17. Montículo binario de mínimos y su representación en un array. Fuente: elaboración

propia.

26
Tema 4. Ideas clave
Las operaciones del montículo serán:
 Insertar un elemento. Lo más sencillo es insertarlo al final y, posteriormente,

buscar su lugar. Esta acción en el montículo se llama flotar().
 Eliminar el elemento máximo del montículo que es la raíz, esto requerirá
reordenarlo mediante una operación que, en la terminología de los montículos, se
denomina hundir.
 Crear montículo.
En la Figura 18 se verá la implementación en Python mediante listas de un montículo

de mínimos.
Figura 18. Montículo de mínimos. Fuente: elaboración propia.

27
Tema 4. Ideas clave
Figura 18. Montículo de mínimos. Fuente: elaboración propia.
4.8. Referencias bibliográficas
Árbol binario de búsqueda (16 de abril de 2020). En Wikipedia. Árbol binario de

búsqueda - Wikipedia, la enciclopedia libre
Salcedo, L. (2018, junio 23). Ejemplo de Tabla Hash [Imagen]. Tabla Hash en Python -
Mi Diario Python (pythondiario.com)
Universidad Don Bosco (s. f.). Programación IV. Guía No. 7. [Guía]. guia-7.pdf
(udb.edu.sv)

28
Tema 4. Ideas clave
4.9. Cuaderno de ejercicios
Ejercicio 1. Usar una pila para evaluar una expresión aritmética en

notación infija
Para poder evaluar una expresión en infija primero se pasará la expresión a postfija
y, posteriormente, se evaluará.
Paso a postfija
 Se debe crear una pila para los operadores.

 Se debe crear una lista vacía para almacenar los valores y obtener la nueva
expresión.
 Se lee la expresión de izquierda a derecha.
 Si se encuentra un operando, se introduce en la lista.
 Si se encuentra paréntesis izquierdo, se apila.
 Si se encuentra un operador de menor precedencia que el de la cima de la pila, se
saca la cima de la pila y se introduce en la lista y se apila el nuevo operador.
 Si se encuentra paréntesis derecho, se pasan a la lista todos los operadores que
haya en la pila hasta encontrar el paréntesis izquierdo (si no se encontrase se
debería elevar una excepción porque hay un error en la fórmula). Modifique el
código para contemplarlo.
 Cuando se llega al final de la expresión se pasan todos los operadores de la pila a
la lista

29
Tema 4. Ideas clave
Figura 19. Código de la función de paso de infija a postfija, uso de la función y resultado. Fuente:
elaboración propia.

30
Tema 4. Ideas clave
Evaluar postfija
 Se crea una pila para guardar los operandos y el resultado.

 Se recorre la expresión en postfija.
 Si se encuentra un operando, se apila.
 Si se encuentra un operador, se desapilan dos operandos de la pila, se hace la
operación y se apila el resultado.
 El resultado final queda en la pila.
Figura 20. Código de la función que evalúa una expresión en postfija, uso y resultado. Fuente:

31
Tema 4. Ideas clave
Ejercicio 2. Eliminar un elemento de un árbol binario ordenado
La eliminación de un elemento en un árbol de este tipo es bastante compleja. Se

deben tener en cuenta los siguientes casos:
 El elemento que se elimina no tiene hijos: el nodo se elimina sin problemas y se

debe poner a vacío el hijo al que corresponde al mismo.
 El elemento que se elimina tiene un único hijo: el hijo del padre del nodo
correspondiente al que se va a eliminar pasará a apuntar al hijo único del elemento
eliminado.
 El elemento que se elimina tiene dos hijos:

• Se busca el hijo más a la izquierda del hijo derecho del nodo que se va a
eliminar.
• Se sustituye el valor del nodo que se elimina por el encontrado.
• Se elimina el nodo encontrado de acuerdo con el procedimiento habitual.
La implementación que se presenta usa como árbol el que se ha implementado en el

apartado de árboles.

32
Tema 4. Ideas clave
Figura 21. Código de la función que elimina un elemento de un árbol binario ordenado. Fuente:

33
Tema 4. Ideas clave
Ejercicio 3. Implementación de colas de prioridad
Las colas de prioridad funcionan como una cola para la extracción, dado que se
extraerá siempre el que se encuentra al frente de la misma, pero la ordenación
depende de las prioridades. Por tanto, cada vez que se inserta un elemento en una
cola deberá ser reorganizado para que se coloque en su lugar de acuerdo con su
prioridad. De esta forma, siempre estarán al frente los de máxima prioridad. Esto
recuerda a la forma de trabajarse con un montículo.
El uso de un montículo reduce la complejidad de los algoritmos, dado que la inserción

y la eliminación tendrán complejidad 𝜃(log 𝑛).
Las operaciones que debería tener la cola de prioridades son:
 Insertar un elemento en la cola.

 Obtener el primero.
 Obtener el resto de la cola.
 Comprobar si está vacía.
 Comprobar si es una cola de prioridad válida (cuando se implementa con
montículos siempre es válida, no hace falta implementar esta operación).
Recuerde que el montículo implementado era de mínimos y se deja como ejercicio

implementar un montículo de máximos (cambian algunas condiciones), si las
prioridades se consideran mayor cuanto mayor sea su valor numérico.

34
Tema 4. Ideas clave
Figura 22. TAD cola de prioridad mediante un montículo. Fuente: elaboración propia.

35
Tema 4. Ideas clave
A fondo
Tipos abstractos de datos en Python
Wachenchauzer, R., Manterola, M., Curia, M., Medrano, M. y Paez. N (s. f.). Tipos
abstractos de datos. En Algoritmos de Programación con Python. Autoedición. 16.2.
Tipos abstractos de datos (Algoritmos de Programación con Python) (uniwebsidad.com)
Para profundizar sobre los TAD y otras formas de implementación.
¿Qué son las estructuras de datos y por qué son tan útiles?
Fuentes, J. (18 de octubre de 2019). ¿Qué son las estructuras de datos y por qué son tan
útiles?. Open Webinars. ¿Qué son las estructuras de datos y por qué son útiles? |
OpenWebinars
Webinar (seminario web) en el que se pone de relieve la importancia de las

estructuras de datos y su utilidad.
Estructuras de datos
Sena, M. (31 de enero de 2019). Estructura de datos. Medium. Estructuras de Datos.

Primera parte — Arrays, Linked lists… | by Marcela Sena | TechWo | Medium
Publicación para profundizar en las estructuras de datos y la comparación entre

algunas de ellas.

36
Tema 4. A fondo
Test
1. Los tipos abstractos de datos:
A. Presentan un nivel de abstracción menor que una estructura de datos
predefinida.
B. Presentan un nivel de abstracción mayor que una estructura de datos
predefinida.
C. No tienen nada que ver con las estructuras de datos.
D. Ninguna de las anteriores es verdadera.
2. Para implementar tipos abstractos de datos en Python:

A. Se suelen utilizar clases.
B. Se implementan solo funciones en módulos independientes que se pueden
aplicar a distintas estructuras de datos.
C. No se pueden implementar tipos abstractos de datos en Python.
3. La copia de un objeto de una clase sobre otro, usando el operador de asignación:

A. Hace referencia al mismo objeto copiado, pero la copia es inmutable.
B. Crea un objeto nuevo a partir del copiado.
C. Hace referencia al mismo objeto copiado.

37
Tema 4. Test
4. Un array de la biblioteca array de Python:
A. Pueden contener datos de distintos tipos.
B. Puede contener datos que sean objetos de clase.
C. Pueden contener datos de tipo lista.
5. En la definición del tipo abstracto de datos lista:

A. Conceptualmente, no se puede permitir que los elementos sean del mismo tipo.
B. Conceptualmente, no se puede permitir que los elementos sean de tipos
distintos.
C. Solo se puede permitir elementos de tipos numérico.
6. Conceptualmente, en el tipo abstracto de datos pila:

A. Se puede extraer un elemento de cualquier parte de la pila e introducir un
elemento en cualquier parte de la pila.
B. Se puede extraer un elemento de cualquier parte de la pila, pero solo introducir
un elemento en el primer lugar.
C. Se extrae e inserta un elemento solo en la cima o último.
7. Conceptualmente, en el tipo abstracto de datos cola:

A. Se puede extraer un elemento de cualquier parte de la cola e introducir un
elemento en cualquier parte de la cola.
B. Se extrae un elemento solo del primer lugar y se inserta un elemento solo en
último lugar.
C. Se puede extraer un elemento de cualquier parte de la cola, pero solo introducir
un elemento en el primer lugar.


38
Tema 4. Test
8. Los tipos de elementos que se pueden usar como clave de una tabla hash en
Python son:
A. Cualquier objeto de clase.
B. Los tipos lista y tupla.
C. Solo los tipos str, int, float.
D. Los tipos str, int, float y bool.
9. Para implementar un tipo abstracto de datos grafo con información de los nodos
vecinos:
A. Se usa una lista de nodos y la matriz de adyacencia.
B. Se usa una matriz en la que cada elemento contiene el valor del nodo y todos
los nodos conectados con él.
C. Se usa una matriz en la que cada elemento contiene el valor del nodo y su nodo
más cercano.
D. Ninguna de las anteriores es verdadera
10. El nivel de un nodo en un tipo abstracto de datos árbol:

A. Es igual a la altura de la raíz, menos la profundidad del nodo.
B. Es el número de aristas que existen desde el nodo raíz hasta él.
C. Es el número de aristas que se encuentra en el camino más largo desde ese
nodo a una hoja.
11. La propiedad de un montículo de máximos asegura que:

A. El valor de todo nodo interno es menor o igual que todos los valores de todos
los nodos de sus subárboles.
B. El valor de todo nodo interno es mayor o igual que todos los valores de todos
los nodos de sus subárboles.

C. No existe una ordenación.

39
Tema 4. Test

Tema4 PC

Cargado por

Copyright:

Formatos disponibles

Tema4 PC

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Tema4 PC

Cargado por

Copyright:

Formatos disponibles

Tema 4

Programación Científica y HPC

Programación Científica y HPC

4.1. Introducción y objetivos

Para el diseño de algoritmos eficientes es fundamental usar estructuras de datos

El concepto de estructura de datos es independiente del lenguaje con el que se

El nivel de abstracción de los lenguajes ha permitido soportar nuevas formas de

manipulación y, algo muy importante, la semántica de sus operaciones. Todo

Programación Científica y HPC

La estructura de un TAD se podría describir de la siguiente forma:

Figura 1. Estructura de un TAD. Fuente: elaboración propia.

En los lenguajes orientados a objetos, la implementación de los TAD se realiza

detalles de implementación; el conocimiento del uso del TAD, garantiza que la

Programación Científica y HPC

En este tema se abordará la manera de usar algunas estructuras y formas de

Características especiales sobre objetos

Ejemplo 1. Copia de variables de objeto y sus resultados

Se crean dos listas, l2 como copia de l1. En realidad, la l1 y l2 son el mismo

Figura 2. Código del ejemplo 1. Fuente: elaboración propia.

Programación Científica y HPC

Figura 3. Código con copy(). Fuente: elaboración propia.

Recuerden, es importante definir en las clases, métodos que hagan copias en

4.2. Arrays y listas

El array o vector es una estructura que se implementa en la mayoría de los lenguajes

Programación Científica y HPC

Implementación de arrays en Python

Aunque las listas en Python se manejan de forma similar a los vectores,

La clase array de la biblioteca array

Programación Científica y HPC

En la Figura 4 se muestra la creación de un vector de enteros y el uso de algunas

Figura 4. Uso de los arrays de la biblioteca array. Fuente: elaboración propia.

Programación Científica y HPC

Las operaciones que debe soportar son:

 Creación de la lista. Se construye la estructura que la soporta, se crea vacía.

Programación Científica y HPC

La definición del TAD que se va a realizar va a separar la implementación de la

Se trata de subir de nivel de abstracción.

Programación Científica y HPC

Figura 6. Implementación del TAD Lista. Fuente: elaboración propia.

Figura 6. Implementación del TAD Lista. Fuente: elaboración propia.

Programación Científica y HPC

4.3. Pilas y colas

Una pila es una colección de elementos que no se puede recorrer. El número de

 Creación de la pila. Se construye la estructura que la soporta, se crea vacía.

Programación Científica y HPC

La definición del TAD que se va a implementar va a separar la implementación de la

Se trata de subir de nivel de abstracción.

Ejemplo 3. Implementar un tipo abstracto de datos Pila

Figura 7. Implementación del TAD Pila. Fuente: elaboración propia.

Programación Científica y HPC

Una cola es una colección de elementos que no se recorren. El número de elementos

 Creación de la cola. Se construye la estructura que la soporta, se crea vacía.

• Comprobar si la cola está vacía.

Se trata de subir de nivel de abstracción.

Programación Científica y HPC

Figura 8. Implementación del TAD Cola. Fuente: elaboración propia.

4.4. Tablas hash

Se almacenan conjuntos de pares <clave,valor>, de forma que la clave es única para

Programación Científica y HPC