B03-T05 Estructura de datos Flashcards
Cuáles son los tipos de datos elemental
Numéricos, Alfabéticos, Especiales (fines aritméticos)
Cuáles son los tipos de datos estructurados
Hay de dos tipos, simples y complejos
Cuáles son los datos estructurados simples
Consituidos por una mínima estructura de datos denominados campos (por ejmplo, una dirección)
Cuáles son los datos estructurados complejos
Listas, grafos, tablas (arrays,matrices), árboles, registros y ficheros
Definición de tabla y array
Un array es una estructura de datos unidimensional, es decir, una colección lineal de elementos del mismo tipo, accesibles por un índice.
Elementos que componen una tabla
- Definición de sus elementos (longitud y tipo de datos)
- Índice: permite el acceso a los elementos
Qué es una matriz
Es un array bidimensional, por lo tanto los índices son accesibles con dos índices.
Por lo general los lenguajes de programación solo permiten dos dimensiones como máximo de matriz
Cuáles son los tipos de tabla
Estáticas y dinámicas. Las dinámicas permiten alterarse durante el tiempo de ejecución
Qué una lista
Conjunto homogéno de de elementos
(nodos) entre los que existe una relación
linéal. Tiene similitudes con una array unidimensional, pero en algunas proframas de programación existen diferencias
¿Qué diferencias se pueden encontrar entre una lista y un array unidimensional en algunos lenguajes de programación?
El tamaño de las lista es homogéneo, puede contener diferentes tipos de datos, contiene métodos avanzados y la gestión de memoria puede ser automática.
En una lista, cuáles son los tres tipos posibles de inserción
En posición intermedia, al principio y al final de la lista
Cuáles son las posibles implementaciones de una lista
- Secuencial: ocupan espacios contiguos de memoria (estática, dinámica)
- Enlazada: cada nodo contiene valor y referencia a otro nodo y no es necesario que ocupen espacios de memoria contiguos (estática, dinámica)
Cuáles son tipos de lista
Pilas, colas y listas doblemente enlzadas
Definición de pilas
- Aplica la filosofía LIFO
- Elimina y añade elementos por el principio
- Vuelta atrás del navegadors
Definición de colas
- Aplica la filosofía FIFO
- Añade elementos por la cola y los elimina del inicio
- Lista de esèra
Definición de listas doblemente enlazadas
- Cada nodo tiene un puntero el anterior y al nodo siguiente
- Son listas bidireccionales
Qué es un grafo
Es una estructura de datos compuesta de vértices o nodos y arcos o aristas
Tipos de conexión entre nodos o vertices en un grafo
- Dirigidos, cuando están compuestos po nodos ordenados (se representa con arcos —>). Estos nodos se dirán que son adyacentes
- No dirigido, compuesto por nodos desordenados (se representa con aristas —)-
En un grafo que es un ciclo
Un camino simple cerrado compuesto de al menos de tres nodos, es decir, que empieza y termina en el mismo nodo, y que no repite ni nodos ni aristas. Son importantes para evitar bucles
En un grafo que un bluque
Es un arco o arista que conecta al nodo consigo mismo
¿Cómo se puede representar un grafo?
Mediante lista de adyacencia (lista o diccionario), matrices o estructuras enlazadas
Cómo se puede recorre un grafo
- En anchura: de izquierda a derecha. Se visitan primero todos los nodos vecinos. Se usa una cola FIFO. Econtrar caminos már corto
- En profundidad, de dentro hacia fuera. Sigue un camino hasta el final antes de retroceder. Se usa una pila (LIFO). Recorrer en profundidad con menos uso de memoria
Definición de árbol
Estructura jerárquica no linéal, de relaciones padre-hijo entre nodos. Se puede considerar un tipo especial de grafo. Un árbol es un grafo, pero no todos los grafos son árboles
Cuál es la raíz de un árbol
El único nodo sin padre
Cuál es el nodo interno de un árbol
El que tiene padres e hijos
Cuál es el nodo hoja de un árbol
El que tiene padre pero no tiene hijos
Árbol: qué es el grado de nodo
El número de hijos directos que tiene ese nodo
Cuál es grado de un árbol
Mayor grado de sus nodos
Definición de árbol binario
Sus nodos tienen como máximo dos nodos. Por ejemplo, los árboles de decisión. Por lo tanto, es un árbol de grado dos
Qué es una lista
Un árbol degenerado de grado uno
Cuál es la notación específica de los árboles
- n: número de nodos
- e: número de hojs
- i: número de nodos internos
- h: altura de un árbol
Cuáles son los tipos de recorrido de profundidad de un árbol
- in-orden: I, E, -H-, A,M
- pre-orden: -H-, I, E, M, A
- post-orden: E, I, A, M, -H-
Características de los áboles binarios de búsqueda (BBB)
- Cada nodo tiene como máximo 2 hijos
- Orden: los valores menores del nodo van la izquierda y los mayores a la derecha
- No puede haber valores duplicados
Cuál es el principal inconveniente de los árboles binarios de búsqueda
Para que sean eficientes han de estar siempre balanceadso
Dónde son últiles los árboles binarios de búsqueda
En bases de datos y sistemas de archivos
Qué es un árbol binario de búsqueda AVN (Adelson-Velsky y Landis)
Es un árbol que se mantiene balanceado automáticamente.
Qué significa que un árbol esté balanceado
Que la diferencia de altura de cualquier subárbol entre el brazo derecho e izquierdo nunca es mayor de 1
¿Qué un árbol multicamino?
Son árboles de búsqueda cuyo grado es mayor de 2.
Formas de implementación de un array multicamino
- Diseñando los hijos como arrays de punteros
[10 20]
Los valores menores que 10 van al primer hijo.
Los valores entre 10 y 20 van al segundo hijo.
Los valores mayores que 20 van al tercer hijo. - Diseñando los hijos con punteros a su hermano y a su hijo
Definición de árbol B
Es una estructura de datos de búsqueda multicamino balanceada, es decir, todas las hojas están al mismo nivel
En un árbol multicamino, qué significa que está balanceado
Todas las hojas estás al mismo nivel
Carácterísticas de un árbol B
- Cada nodo puede contener múltiplesclaves y más de dos hijos
- Está balanceados. Todas las hojas están almismo nivel
- Optimizado para almacenamiento disco
Derviados del arbol B
Árbol * y árbol +
Qué es un árbol B+
Es un derivado del árbol B.
Está formado por dos partes:
- La información se guarda en nodos hoja.
- Los nodos interiores se utilizan como índices
- Secuencia: Páginas hoja enlazadas secuencialmente en las que se repiten las claves interiores
- Mayor eficiencia en las búsquedas
Qué es un árbol B*
Es un derivado del árbol B.
- Un nodo se divide solo si su hermano también está lleno.
- Mejora la eficiencia del acceso directo.
- Reduce la altura del árbol
- La información se guarda en nodos hoja.
- Los nodos interiores se utilizan como índices
¿Cómo se puede medir la eficiencia de un algortimo?
- Empíricamente, ejecutarlos varias veces con distintos datos de entrada
- Teóricamente. Determinación matemática cantidad de recursos
¿Qué es el principio de invarianza en el contexto de eficiencia de un algoritmo?
Dos implementaciones distintas de un algoritmo (por ejemplo, en pcs con distintas capacidades) no diferencia en eficacia en más de una constate multiplicativa
Eficiencia algoritmo: qué es T(n)
Representación unidades de tiempo abstraída –>
unidad de tiempo = tiempo ejecución instrucción simple en un PC idealizado
Eficiencia algoritmo: cuál es el tiempo total de ejecución de un algoritmo
Sumatario tiempo ejecución operaciones que contiene:
- Una lectura de una variable
- Una sentencia condicional
- Un bucle
- El retorno de un valor…
Eficiencia algoritmo: tipos de escenario que hay que definir, y anotación asintóticas
- Caso peor. O(n). Por ejemplo, que un árbol de búsqueda el elemento se encuente el último lugar
- Caso promedio Θ(n) (Caso promedio). Recorre la mitad de la lista
- Caso más favorable Ω(n) (Mejor caso). Ejemplo, se encuentre en primer lugar
Definición de eficiencia de un algoritmo
Hace referencia a la forma en que el tiempo de ejecución
para procesar una entrada de tamaño n crece cuando
se incrementa el valor de n
Solo importa el tamaño del input, es decir del problema
no la máquina en la que se ejecuta
Definición de recursivdad algorítmica
Estrategia que consiste en dividir el problema original en varios más pequeños esto es en subproblemas
Debe hacer una o varias llamadas a sí mismo
Ejemplo de resursividad algorítmica
Es el tipo de comporrtamiento
de la pila, a medida que finalizan los métodos
que se han ejecutado los últimos, van finalizando
los métodos ejecutados anteriormente
Tipos de recursividad algorítmica
- Directa: se hace referencia a sí mismo
- Indirecta: cuando hace referencia a una función que referencia de nuevo al alfortimo
¿Cual es el principal problema de la recursividad algorítmica?
Procesamiento duplicado. Que endiferentes partes de la rutina se procesen dos veces los mismos cálculos
Recursividad vs iteración
La recursividad es menos efectia efectiva y usa una pila de llamadas. Aunque la iteración es buena cuando se conoce el número total de repeticiones necesarias
- La recursividad y la iteración resuelven problemas repetitivos, pero la iteración es más eficiente en memoria y velocidad.
- La recursividad es más intuitiva para estructuras jerárquicas como árboles y problemas matemáticos definidos de forma recursiva.
Tipos de algoritmos de búsqueda
- Búsqueda secuencial
- Búsqueda binaria
- Búsqueda por interpolación
- Mediante árboles binarios de búsqueda
En qué consiste la búsqueda secuencial
En la búsqueda lineal de un elemento. Su complejidad en el peor caso es O(n).
Cuál es el principal problema de la búsqueda secuencial y la manera de solucionarlo
Ineficientes si los elementos más búscados están al final.
Posible solución, alteración del orden:
- Moverse al frente: el elemento encontrado se dispone al frente
- Trasposición: el elemento encontrado se intercambia con el registro que le precede
¿Cuáles son los contextos en los que mejora la eificiencia de una búsqueda secuencial?
- En una tabla ordenada
- En una tabla indexada (se crea una tabla adicional)
En qué consiste la búsqueda binaria
Es el sistema más eficiente en una tabla secuencial sin índices.
Básicamente se compara el argumento con la clave del elemento medio de la tabla.
Ver árboles binarios de búsqueda, procedimiento parecido
¿Dónde no es aplicable la búsqueda binaria?
No es aplicable en situaciones donde se requieren muchas alteraciones de la tabla. Necesitamos un vector ordenado
¿En que consiste la búsqueda por interpolación?
La búsqueda por interpolación es un algoritmo optimizado para buscar en listas ordenadas que mejora la búsqueda binaria cuando los datos están distribuidos de manera uniforme.
A diferencia de la búsqueda binaria que divide siempre por la mitad, en este caso estima la posición del valor buscado mediante una fórmula matemática
Tipos de algoritmos de clasificación u ordenamiento
Eficientes:
- Clasificación rápida (Qicksort)
- Por montículos (heapsort)
- Intercalación (mergesort)
Simples:
- Clasificación por burbuja (bubblesort)
- Clasificación por inserción
- Clasificación por selección
Definición de organización de ficheros
La organización de ficheros se refiere a la forma en que los datos son almacenados y estructurados dentro de archivos en un sistema
de almacenamiento (disco duro, SSD, base de datos, etc.).
¿Cuáles son los modos básicos de organización de ficheros?
- Organización secuencial:
- Organización directa o aleatoria
Características de la organización secuencia de ficheros
- Almacena los registros en posiciones contiguas de memoria
- El acceso se realiza en el mismo orden en que se grabaron
¿Cuál es el principal problema de la organización secuencial de ficheros?
Inserción, modificación o eliminación de registros existentes
No se puede leer y escribir simultáneamente
Por lo tanto si queremos hacer cambios hay que crear un fichero nuevo
con todos los registros anteriores más los cambios
¿Cuándo es apropiado la organización secuencial de ficheros?
Los únicos ficheros apropieados para esta organización
son los que son utilizados con una gran frecuencia
Es útil cuando solo se realizan lecturas secuenciales (ejemplo: reportes o logs).
Características de la organización directa o aleatoria de ficheros
- Se utiliza una clave de identificación
- Los más rápidos para acceder los archivos porque no hay que leerlos todos
- Acceso inmediato a los registros
- No es necesario ordenar el fichero
- No es necesario regenerar el fichero
En la organización directa de ficheros, qué es el identificador
El identificador indica la posición física de almacenamiento. Lo puede hacer de manera directa o mediante un algoritmo de identificación.
Cuando dos registros obtienen la misma dirección de almacenamiento.
Principales problemas de la organización directa (aleatoria) de archivos
- Espacios vacíos en disco por asignaciones desiguales de registros.
- Borrar un registro deja huecos que no se reutilizan fácilmente.
- Si se agregan más registros de los previstos, la reubicación de datos es costosa.
- Las colisiones y la gestión del espacio en disco pueden causar ineficiencia y pérdida de datos si no se manejan correctamente.
¿Cómo puede ser utilizado el identificativo de registros?
- Identificativo de orden: Utilizado para introducir los registros en el fichero
- Identificativo de búsqueda: Utilizado para localizar registros dentro de un fichero
Conceptos fundamentales en los derivados de la organización secuencial (tipos o versiones mejoradas
- Puntero: Registro en memoria que contiene la dirección de una información Es un campo adicional que indica cuál es el anterior
y el siguiente registro de la secuencia lógica - Índice: Tabla con direcciones de datos a los que se puede acceder de modo secuencial
¿Cuáles son las variantes de la organización secuencial?
- Organización secuencial indexada
- Organización secuencial encadenada
- Organización secuencial indexada encadenada
¿En qué consiste la organización secuencial indexada de archivos?
Aprovecha lo mejor de cada uno de los métodos:
- Por un lado el almacenamiento secuencial de datos
- Por otra para almacenar las tablas de índices
Principales problemas de la organización secuencial indexada de archivos
- La inserción de archivos se realiza en una nueva zona overflow donde se almacenan desordenados
- Cuando se borran registros no se produce su borrado como tal, sino que se marca para que sea ignorado. Si se producen varios borrados puede degradar el espacio en memoria
¿En qué consiste la Organización secuencial encadenada de archivos?
- En este sistema de organización se utilizan punteros. Cada registro contiene un puntero al siguiente registro. Por lo tanto facilita la inservición y eliminación de registros
- Los registros se hacen al final por lo tanto su secuencia física y su secuencia lógica no coinciden
¿Cuáles son los principales problemas de la organización secuencial encadenada de archivos?
- Cuando se borran registros no se produce su borrado como tal, sino que se marca para que sea ignorado. Si se producen varios borrados puede degradar el espacio en memoria
¿En qué consiste la organización secuencial indexada encadenada?
Utiliza punteros (para que la secuencia lógica no se pierda) en índices (por su parte permiten el acceso directo) simultáneamente
¿En qué consiste la reorganización fichero secuencial indexado encadenado
- Eliminar el área de desbordamiento
- Eliminar físicamente las bajas lógicas
- Dejar el fichero ordenado por el campo clave
