Podcast
Questions and Answers
¿Cuál de las siguientes operaciones básicas no se realiza sobre un array?
¿Cuál de las siguientes operaciones básicas no se realiza sobre un array?
¿Qué tipo de array utiliza memoria dinámica?
¿Qué tipo de array utiliza memoria dinámica?
Para acceder a un elemento en una matriz bidimensional, ¿qué índices se utilizan?
Para acceder a un elemento en una matriz bidimensional, ¿qué índices se utilizan?
Los registros son estructuraciones de datos que pueden contener diferentes tipos de qué elementos?
Los registros son estructuraciones de datos que pueden contener diferentes tipos de qué elementos?
Signup and view all the answers
¿Cómo se accede a los campos de un registro?
¿Cómo se accede a los campos de un registro?
Signup and view all the answers
¿Qué característica define a los arrays estáticos?
¿Qué característica define a los arrays estáticos?
Signup and view all the answers
Un array unidimensional se puede describir como:
Un array unidimensional se puede describir como:
Signup and view all the answers
Las matrices pueden ser descritas como:
Las matrices pueden ser descritas como:
Signup and view all the answers
¿Cuál de las siguientes afirmaciones sobre los arrays es correcta?
¿Cuál de las siguientes afirmaciones sobre los arrays es correcta?
Signup and view all the answers
¿Qué caracteriza a un array unidimensional respecto a otros tipos de arrays?
¿Qué caracteriza a un array unidimensional respecto a otros tipos de arrays?
Signup and view all the answers
¿Cómo se define el índice de un array?
¿Cómo se define el índice de un array?
Signup and view all the answers
¿Cuál es una de las características de los arrays dinámicos?
¿Cuál es una de las características de los arrays dinámicos?
Signup and view all the answers
¿Cuál es la diferencia principal entre arrays y registros?
¿Cuál es la diferencia principal entre arrays y registros?
Signup and view all the answers
¿Cómo se puede describir una matriz bidimensional?
¿Cómo se puede describir una matriz bidimensional?
Signup and view all the answers
¿Cuál de las siguientes afirmaciones sobre los arrays multidimensionales es correcta?
¿Cuál de las siguientes afirmaciones sobre los arrays multidimensionales es correcta?
Signup and view all the answers
¿Qué operación básica se puede realizar en un array?
¿Qué operación básica se puede realizar en un array?
Signup and view all the answers
¿Cuál es la ventaja principal de realizar un recorrido en Inorden en un ABB?
¿Cuál es la ventaja principal de realizar un recorrido en Inorden en un ABB?
Signup and view all the answers
¿Cuál es la característica que debe cumplir un árbol para ser considerado un árbol AVL?
¿Cuál es la característica que debe cumplir un árbol para ser considerado un árbol AVL?
Signup and view all the answers
¿Qué inconveniente puede presentar un árbol binario de búsqueda (ABB)?
¿Qué inconveniente puede presentar un árbol binario de búsqueda (ABB)?
Signup and view all the answers
¿Cuál es la complejidad de búsqueda en un árbol AVL equilibrado?
¿Cuál es la complejidad de búsqueda en un árbol AVL equilibrado?
Signup and view all the answers
¿Cómo se pueden implementar los árboles multicamino?
¿Cómo se pueden implementar los árboles multicamino?
Signup and view all the answers
¿Cuál es la principal ventaja de los árboles multicamino respecto a los árboles binarios?
¿Cuál es la principal ventaja de los árboles multicamino respecto a los árboles binarios?
Signup and view all the answers
¿Qué sucede si un árbol AVL tiene una restricción de equilibrio perfecta?
¿Qué sucede si un árbol AVL tiene una restricción de equilibrio perfecta?
Signup and view all the answers
¿Cuál es la mayor desventaja de utilizar punteros al hermano siguiente en la implementación de árboles multicamino?
¿Cuál es la mayor desventaja de utilizar punteros al hermano siguiente en la implementación de árboles multicamino?
Signup and view all the answers
¿Qué característica distingue a un Tipo de Datos de un Tipo Abstracto de Datos?
¿Qué característica distingue a un Tipo de Datos de un Tipo Abstracto de Datos?
Signup and view all the answers
¿Cuál es la clasificación correcta de los tipos de datos elementales?
¿Cuál es la clasificación correcta de los tipos de datos elementales?
Signup and view all the answers
¿Cuál de los siguientes es un ejemplo de Tipo Abstracto de Datos?
¿Cuál de los siguientes es un ejemplo de Tipo Abstracto de Datos?
Signup and view all the answers
Qué operación se puede realizar sobre un Tipo Abstracto de Datos sin conocer su implementación?
Qué operación se puede realizar sobre un Tipo Abstracto de Datos sin conocer su implementación?
Signup and view all the answers
¿Cuál de las siguientes afirmaciones es cierta respecto a las estructuras de datos?
¿Cuál de las siguientes afirmaciones es cierta respecto a las estructuras de datos?
Signup and view all the answers
¿Qué definición se le da a un Tipo de Datos compuesto?
¿Qué definición se le da a un Tipo de Datos compuesto?
Signup and view all the answers
¿Cuál de los siguientes tipos de datos es considerado un dato elemental?
¿Cuál de los siguientes tipos de datos es considerado un dato elemental?
Signup and view all the answers
¿Por qué es importante entender la diferencia entre un Tipo de Datos y un Tipo Abstracto de Datos?
¿Por qué es importante entender la diferencia entre un Tipo de Datos y un Tipo Abstracto de Datos?
Signup and view all the answers
¿Cuál de las siguientes afirmaciones sobre estructuras de datos enlazadas es correcta?
¿Cuál de las siguientes afirmaciones sobre estructuras de datos enlazadas es correcta?
Signup and view all the answers
¿Qué tipo de estructura de datos permite la modificación de su tamaño durante la ejecución del programa?
¿Qué tipo de estructura de datos permite la modificación de su tamaño durante la ejecución del programa?
Signup and view all the answers
¿Cuál de las siguientes comparaciones es correcta entre agrupaciones estáticas y dinámicas?
¿Cuál de las siguientes comparaciones es correcta entre agrupaciones estáticas y dinámicas?
Signup and view all the answers
¿Qué característica define a una estructura de datos homogénea?
¿Qué característica define a una estructura de datos homogénea?
Signup and view all the answers
¿Cuál es una de las desventajas de usar estructuras dinámicas en comparación con las estáticas?
¿Cuál es una de las desventajas de usar estructuras dinámicas en comparación con las estáticas?
Signup and view all the answers
En el ámbito de estructuras de datos, ¿qué significa que una estructura sea estática?
En el ámbito de estructuras de datos, ¿qué significa que una estructura sea estática?
Signup and view all the answers
¿Qué afirma correctamente sobre las estructuras de datos heterogéneas?
¿Qué afirma correctamente sobre las estructuras de datos heterogéneas?
Signup and view all the answers
¿Cuál es el principal inconveniente de las agrupaciones estáticas en comparación con las dinámicas?
¿Cuál es el principal inconveniente de las agrupaciones estáticas en comparación con las dinámicas?
Signup and view all the answers
¿Qué define una lista como una estructura dinámica en comparación con un vector?
¿Qué define una lista como una estructura dinámica en comparación con un vector?
Signup and view all the answers
¿Cuál es una característica clave de los nodos en una lista?
¿Cuál es una característica clave de los nodos en una lista?
Signup and view all the answers
¿Cuál de las siguientes operaciones es considerada la de mayor complejidad técnica en listas?
¿Cuál de las siguientes operaciones es considerada la de mayor complejidad técnica en listas?
Signup and view all the answers
En una lista densa, ¿cómo se determina el siguiente elemento de la lista?
En una lista densa, ¿cómo se determina el siguiente elemento de la lista?
Signup and view all the answers
¿Qué tipo de lista permite la inclusión de nodos de elementos de diferentes tipos?
¿Qué tipo de lista permite la inclusión de nodos de elementos de diferentes tipos?
Signup and view all the answers
Al eliminar un nodo en una lista, ¿cuál es el impacto inmediato en el predecesor del nodo eliminado?
Al eliminar un nodo en una lista, ¿cuál es el impacto inmediato en el predecesor del nodo eliminado?
Signup and view all the answers
¿Cómo se caracteriza a una lista contigua o densa?
¿Cómo se caracteriza a una lista contigua o densa?
Signup and view all the answers
¿Qué sucede con el primer elemento de una lista al ser insertado un nuevo nodo al principio?
¿Qué sucede con el primer elemento de una lista al ser insertado un nuevo nodo al principio?
Signup and view all the answers
¿Cuál es la función principal de la clave en una tabla hash?
¿Cuál es la función principal de la clave en una tabla hash?
Signup and view all the answers
¿Cuál es el efecto de una colisión en una tabla hash?
¿Cuál es el efecto de una colisión en una tabla hash?
Signup and view all the answers
En el contexto de tablas hash, ¿qué es el factor de carga?
En el contexto de tablas hash, ¿qué es el factor de carga?
Signup and view all the answers
¿Cómo se define el direccionamiento abierto en tablas hash?
¿Cómo se define el direccionamiento abierto en tablas hash?
Signup and view all the answers
¿Cuál de los siguientes enunciados describe correctamente un árbol?
¿Cuál de los siguientes enunciados describe correctamente un árbol?
Signup and view all the answers
En la estructura de un árbol, ¿qué tipo de nodo no tiene descendientes?
En la estructura de un árbol, ¿qué tipo de nodo no tiene descendientes?
Signup and view all the answers
¿Qué característica define a los árboles respecto a su estructura?
¿Qué característica define a los árboles respecto a su estructura?
Signup and view all the answers
¿Cuál es la afirmación correcta sobre la lista en el encadenamiento separado dentro de una tabla hash?
¿Cuál es la afirmación correcta sobre la lista en el encadenamiento separado dentro de una tabla hash?
Signup and view all the answers
¿Cuál de las siguientes afirmaciones es correcta sobre los recorridos en profundidad de un árbol?
¿Cuál de las siguientes afirmaciones es correcta sobre los recorridos en profundidad de un árbol?
Signup and view all the answers
En un árbol binario de búsqueda (ABB), ¿qué relación debe existir entre un nodo y sus subárboles?
En un árbol binario de búsqueda (ABB), ¿qué relación debe existir entre un nodo y sus subárboles?
Signup and view all the answers
¿Cuál es la principal característica que define a un árbol completo?
¿Cuál es la principal característica que define a un árbol completo?
Signup and view all the answers
En el recorrido en anchura de un árbol, ¿cómo se visita cada nodo?
En el recorrido en anchura de un árbol, ¿cómo se visita cada nodo?
Signup and view all the answers
¿Cuál de las siguientes opciones representa una aplicación práctica de los árboles?
¿Cuál de las siguientes opciones representa una aplicación práctica de los árboles?
Signup and view all the answers
¿Qué se puede decir sobre la estructura de datos de un árbol binario?
¿Qué se puede decir sobre la estructura de datos de un árbol binario?
Signup and view all the answers
En el contexto de un árbol binario, ¿qué afirmación sobre los nodos hoja es cierta?
En el contexto de un árbol binario, ¿qué afirmación sobre los nodos hoja es cierta?
Signup and view all the answers
En el recorrido en preorden de un árbol binario, ¿qué orden se sigue?
En el recorrido en preorden de un árbol binario, ¿qué orden se sigue?
Signup and view all the answers
Study Notes
Estructuras de datos
- Las estructuras de datos son formas de organizar y almacenar información en una computadora.
- Pueden ser estáticas (tamaño fijo) o dinámicas (tamaño variable).
- Las estructuras de datos se clasifican como simples (solo un tipo de datos) o compuestas (combinación de tipos).
- Los tipos de datos simples incluyen:
boolean,char,integer,realystring. - Los arrays son estructuras de datos compuestas que contienen elementos homogéneos (mismo tipo y tamaño).
- Los arrays pueden ser unidimensionales (vectores) o bidimensionales (matrices).
- Los arrays se definen con un índice que empieza en 0 y termina en
tamaño-1. - Los arrays pueden ser estáticos (tamaño definido en tiempo de compilación) o dinámicos (tamaño variable en tiempo de ejecución).
Operaciones básicas con arrays
- Crear el array: Definir el tamaño y tipo de datos.
- Insertar/modificar/eliminar elementos: Agregar, cambiar o remover elementos específicos.
- Buscar un elemento: Encontrar un elemento específico dentro del array.
- Ordenar los elementos: Organizar los elementos del array en un orden específico.
- Contar los elementos: Determinar la cantidad de elementos en el array.
Registros
- Los registros son estructuras heterogéneas que agrupan elementos de distintos tipos, conocidos como campos.
- Los campos están relacionados con la información referente a un objeto específico.
- Ejemplo: Un registro de "persona" podría contener los campos
Nombre,edadyDNI. - Se accede a cada campo de un registro usando el operador
.
Árboles binarios de búsqueda (ABB)
- Los ABB son estructuras no lineales, organizados jerárquicamente.
- Cada nodo tiene dos hijos como máximo: izquierdo y derecho.
- Los valores de los nodos son diferentes y se organizan de forma que:
- Los valores del subárbol izquierdo son menores que el nodo padre.
- Los valores del subárbol derecho son mayores que el nodo padre.
- La búsqueda en un ABB se realiza recursivamente desde la raíz hasta las hojas.
- Un recorrido Inorden por un ABB ordena los valores en orden ascendente.
- El ABB se puede degenerar en una lista, lo cual se puede solucionar con un árbol AVL.
Árboles AVL
- Los árboles AVL son ABB equilibrados en altura.
- La diferencia de altura entre los subárboles izquierdo y derecho de un nodo no puede ser mayor a una unidad.
- Esto asegura búsquedas más rápidas, con una complejidad de O(log N).
Árboles multicamino
- Son árboles donde cada nodo puede tener un número arbitrario de hijos (grado mayor que 2).
- Se pueden implementar usando arrays de punteros o punteros al hermano siguiente y al hijo.
- La principal ventaja es que tienen más nodos en cada nivel, lo que acelera las búsquedas.
Tipos de datos y estructuras de datos
- Un Tipo de Datos (TD) es un conjunto de valores que puede tomar una variable.
-
Existen dos tipos de datos:
-
Datos elementales: Se almacenan sin estructuras especiales.
- Numéricos: Compuestos por guarismos (0, 1, 2,…, 9).
- Alfabéticos: Compuestos por caracteres del alfabeto (a, b, c,…, x, y, z).
- Especiales: Usados para fines sintácticos o aritméticos.
- Tipos compuestos: Los más comunes son arrays, listas, árboles, grafos, registros y ficheros.
-
Datos elementales: Se almacenan sin estructuras especiales.
- Un Tipo Abstracto de Datos (TAD) oculta los detalles de la implementación y se centra en la especificación.
- Se define por su interfaz, que expone las operaciones posibles sin importar la implementación.
- Ejemplos: TDA Lista, TDA Árbol, TDA Pila, TDA Cola.
- Una Estructura de Datos (ED) es la representación o implementación de un TAD.
- Organiza un conjunto de datos elementales para facilitar su manipulación.
Clasificación de Estructuras de Datos
-
Según su ubicación en la memoria:
- Contiguas: Los datos se almacenan en áreas adyacentes de memoria. Ejemplos: cadenas, arrays, vectores, registros.
- Enlazadas: Los datos no están contiguos, se relacionan mediante punteros. La localización del dato se encuentra a través de estos punteros.
-
Según la variabilidad de su tamaño:
- Estáticas: El tamaño se define antes de la ejecución y no se puede modificar. Ejemplo: array o matriz.
- Dinámicas: El tamaño puede crecer o decrecer durante la ejecución. Ejemplo: lista o árbol.
- Ventajas de las agrupaciones estáticas: Búsquedas más rápidas en vectores.
- Ventajas de las agrupaciones dinámicas: Mayor facilidad para insertar y eliminar elementos, adecuadas cuando el número de elementos es variable.
-
Según el tipo de datos que contienen:
- Homogéneas: Solo se usa un tipo de datos.
- Heterogéneas: Se permiten distintos tipos de datos. Ejemplo: registros.
- Registros: Permiten anidar estructuras, es decir, un campo de una estructura puede ser otra estructura.
Listas
- Una lista es un TAD que se define como un conjunto lógico de elementos homogéneos (nodos) con una relación lineal.
- Cada elemento es una unidad básica de información dentro de la estructura.
- Permite almacenar datos de forma organizada, como los vectores, pero de manera dinámica.
-
Propiedades de una lista:
- Todos los elementos son del mismo tipo.
- Los componentes se almacenan según un orden.
-
Operaciones sobre una lista:
- Crear, insertar elementos, buscar elementos, eliminar elementos.
- La inserción es la operación más compleja.
-
Tipos de listas según el acceso al siguiente elemento:
- Lista DENSA o CONTIGUA: La propia estructura determina el siguiente elemento (posición), los nodos son adyacentes en memoria.
- Lista ENLAZADA: Cada elemento tiene un puntero al siguiente elemento.
Tablas Hash
-
Tabla Hash: Una estructura de datos que permite acceder eficientemente a los elementos utilizando una clave única para cada elemento.
- Se utiliza para guardar información de forma rápida.
- Comprende un array de entradas y una función de dispersión.
- Función de dispersión: Asocia un elemento con una clave.
- Colisiones en Tablas Hash: Se producen cuando dos elementos distintos tienen la misma clave.
-
Resolución de Colisiones:
- Encadenamiento separado (hashing ABIERTO): Las colisiones se resuelven añadiéndolas en una lista.
- Direccionamiento abierto (hashing CERRADO): Se re-asigna una clave hasta encontrar un hueco en la tabla.
Conjuntos
-
Conjunto: Una colección homogénea y no ordenada de elementos distintos.
- Se implementa con arrays.
Árboles
-
Árbol: Estructura de datos jerárquica no lineal, con relaciones padre-hijo entre nodos.
- Formalmente, un grafo no dirigido, acíclico y conexo.
-
Características de un árbol:
- Existe un único nodo raíz.
- Cada nodo, excepto la raíz, tiene un único padre.
- Existe un camino único desde la raíz a cualquier nodo.
-
Tipos de nodos en un árbol:
- Raíz: El único nodo sin padre.
- Interno: Tiene al menos un hijo.
- Hoja: No tiene descendientes.
- Árbol completo: Todo nodo interno tiene 2 descendientes directos.
-
Recorridos de árbol:
-
En profundidad (dimensional):
- Preorden (R-IZQ-DCHA): Raíz, subárbol izquierdo, subárbol derecho.
- Inorden (IZQ-R-DCHA): Subárbol izquierdo, raíz, subárbol derecho.
- Postorden (IZQ-DCHA-R): Subárbol izquierdo, subárbol derecho, raíz.
- En anchura (dimensional): Se recorre por niveles, de izquierda a derecha.
-
En profundidad (dimensional):
-
Aplicaciones de los árboles:
- Expresiones aritméticas, árboles de decisión.
Árboles Binarios de Búsqueda (ABB)
- Árbol Binario de Búsqueda (ABB): Cada nodo tiene una clave y esta es mayor que las claves de su subárbol izquierdo y menor que las de su subárbol derecho.
-
Propiedad esencial de un ABB:
- Todos los valores del subárbol izquierdo son menores que el valor del nodo.
- Todos los valores del subárbol derecho son mayores que el valor del nodo.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Este cuestionario aborda las estructuras de datos, centrándose en las características de las estáticas y dinámicas. También se explorarán los arrays, tanto unidimensionales como bidimensionales, y las operaciones básicas que se pueden realizar con ellos.
