Estructuras de Datos y Arrays

Podcast Beta

Play an AI-generated podcast conversation about this lesson

Questions and Answers

¿Cuál de las siguientes operaciones básicas no se realiza sobre un array?

Buscar un elemento concreto

Realizar una compresión de datos (correct)

Crear el array

Ordenar los elementos del array

¿Qué tipo de array utiliza memoria dinámica?

Array multidimensional (correct)

Array estático

Array unidimensional

Array bidimensional

Para acceder a un elemento en una matriz bidimensional, ¿qué índices se utilizan?

Cuatro índices

Un solo índice

Dos índices (correct)

Tres índices

Los registros son estructuraciones de datos que pueden contener diferentes tipos de qué elementos?

Campos Signup and view all the answers

¿Cómo se accede a los campos de un registro?

Usando el operador de acceso '.' Signup and view all the answers

¿Qué característica define a los arrays estáticos?

El tamaño y posición de la memoria están fijados en tiempo de compilación Signup and view all the answers

Un array unidimensional se puede describir como:

Una lista de elementos de un solo tipo Signup and view all the answers

Las matrices pueden ser descritas como:

Arrays bidimensionales que organizan datos en filas y columnas Signup and view all the answers

¿Cuál de las siguientes afirmaciones sobre los arrays es correcta?

Un array está definido por la longitud y el tipo de dato a almacenar. Signup and view all the answers

¿Qué caracteriza a un array unidimensional respecto a otros tipos de arrays?

Es una colección lineal de elementos homogéneos. Signup and view all the answers

¿Cómo se define el índice de un array?

Es una variable numérica entera positiva que comienza en 0. Signup and view all the answers

¿Cuál es una de las características de los arrays dinámicos?

Pueden tener su tamaño variable en tiempo de ejecución. Signup and view all the answers

¿Cuál es la diferencia principal entre arrays y registros?

Los registros solo pueden almacenar un tipo de dato. Signup and view all the answers

¿Cómo se puede describir una matriz bidimensional?

Consiste en filas y columnas organizadas en una única estructura. Signup and view all the answers

¿Cuál de las siguientes afirmaciones sobre los arrays multidimensionales es correcta?

Permiten almacenar más de una dimensión de datos homogéneos. Signup and view all the answers

¿Qué operación básica se puede realizar en un array?

Acceder a un elemento mediante su índice. Signup and view all the answers

¿Cuál es la ventaja principal de realizar un recorrido en Inorden en un ABB?

Acceder a los valores en orden ascendente. Signup and view all the answers

¿Cuál es la característica que debe cumplir un árbol para ser considerado un árbol AVL?

La altura de sus subárboles no puede diferir en más de una unidad. Signup and view all the answers

¿Qué inconveniente puede presentar un árbol binario de búsqueda (ABB)?

Su tendencia a degenerar en una lista. Signup and view all the answers

¿Cuál es la complejidad de búsqueda en un árbol AVL equilibrado?

O(log N) Signup and view all the answers

¿Cómo se pueden implementar los árboles multicamino?

Utilizando arrays de punteros o punteros a hermanos y a hijos. Signup and view all the answers

¿Cuál es la principal ventaja de los árboles multicamino respecto a los árboles binarios?

Proporcionan accesos más rápidos a los nodos. Signup and view all the answers

¿Qué sucede si un árbol AVL tiene una restricción de equilibrio perfecta?

El número de nodos del subárbol izquierdo y derecho no puede diferir en más de una unidad. 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?

Incrementa la complejidad de gestión de memoria. Signup and view all the answers

¿Qué característica distingue a un Tipo de Datos de un Tipo Abstracto de Datos?

El Tipo Abstracto de Datos oculta los detalles de la implementación. Signup and view all the answers

¿Cuál es la clasificación correcta de los tipos de datos elementales?

Numéricos, Alfabéticos y Especiales. Signup and view all the answers

¿Cuál de los siguientes es un ejemplo de Tipo Abstracto de Datos?

Lista. Signup and view all the answers

Qué operación se puede realizar sobre un Tipo Abstracto de Datos sin conocer su implementación?

Acceder. Signup and view all the answers

¿Cuál de las siguientes afirmaciones es cierta respecto a las estructuras de datos?

Las estructuras de datos implementan los Tipos Abstractos de Datos. Signup and view all the answers

¿Qué definición se le da a un Tipo de Datos compuesto?

Consiste en agrupaciones de otros tipos de datos. Signup and view all the answers

¿Cuál de los siguientes tipos de datos es considerado un dato elemental?

Carácter. Signup and view all the answers

¿Por qué es importante entender la diferencia entre un Tipo de Datos y un Tipo Abstracto de Datos?

Porque ayuda a comprender cómo y qué tipo de operaciones se pueden realizar. Signup and view all the answers

¿Cuál de las siguientes afirmaciones sobre estructuras de datos enlazadas es correcta?

Los elementos se relacionan a través de punteros. 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?

Estructuras dinámicas Signup and view all the answers

¿Cuál de las siguientes comparaciones es correcta entre agrupaciones estáticas y dinámicas?

Las agrupaciones estáticas no permiten inserciones ni eliminaciones de elementos. Signup and view all the answers

¿Qué característica define a una estructura de datos homogénea?

Contiene solo un tipo de dato. 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?

Ocupación de memoria generalmente mayor. Signup and view all the answers

En el ámbito de estructuras de datos, ¿qué significa que una estructura sea estática?

Debes definir su tamaño antes de la ejecución. Signup and view all the answers

¿Qué afirma correctamente sobre las estructuras de datos heterogéneas?

Pueden contener diferentes tipos de datos en sus elementos. Signup and view all the answers

¿Cuál es el principal inconveniente de las agrupaciones estáticas en comparación con las dinámicas?

No pueden cambiar su tamaño durante la ejecución. Signup and view all the answers

¿Qué define una lista como una estructura dinámica en comparación con un vector?

Permite cambiar el tamaño en tiempo de ejecución. Signup and view all the answers

¿Cuál es una característica clave de los nodos en una lista?

El primer nodo no tiene predecesor. Signup and view all the answers

¿Cuál de las siguientes operaciones es considerada la de mayor complejidad técnica en listas?

Insertar un nuevo nodo en cualquier posición. Signup and view all the answers

En una lista densa, ¿cómo se determina el siguiente elemento de la lista?

Por medio del orden de almacenamiento en memoria. Signup and view all the answers

¿Qué tipo de lista permite la inclusión de nodos de elementos de diferentes tipos?

Lista heterogénea. 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?

El predecesor ahora debe apuntar al nodo sucesor del nodo eliminado. Signup and view all the answers

¿Cómo se caracteriza a una lista contigua o densa?

Los nodos son adyacentes físicamente en la memoria. Signup and view all the answers

¿Qué sucede con el primer elemento de una lista al ser insertado un nuevo nodo al principio?

El primer elemento se convierte en el predecesor del nuevo nodo. Signup and view all the answers

¿Cuál es la función principal de la clave en una tabla hash?

Identificar unívocamente a una entrada en la tabla. Signup and view all the answers

¿Cuál es el efecto de una colisión en una tabla hash?

Las entradas colisionadas son almacenadas juntas en la misma lista. Signup and view all the answers

En el contexto de tablas hash, ¿qué es el factor de carga?

El promedio de claves por lista en encadenamiento separado. Signup and view all the answers

¿Cómo se define el direccionamiento abierto en tablas hash?

Se reasigna otro valor hash hasta encontrar un espacio vacío. Signup and view all the answers

¿Cuál de los siguientes enunciados describe correctamente un árbol?

Es una estructura jerárquica donde un nodo raíz conecta con otros nodos. Signup and view all the answers

En la estructura de un árbol, ¿qué tipo de nodo no tiene descendientes?

Nodo hoja. Signup and view all the answers

¿Qué característica define a los árboles respecto a su estructura?

No pueden contener relaciones cíclicas ni autoconexiones. 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?

La lista puede crecer conforme se añaden más colisiones. Signup and view all the answers

¿Cuál de las siguientes afirmaciones es correcta sobre los recorridos en profundidad de un árbol?

El recorrido en inorden puede retornar los nodos en orden ascendente para un ABB. 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?

Las claves del subárbol izquierdo deben ser menores que la clave del nodo. Signup and view all the answers

¿Cuál es la principal característica que define a un árbol completo?

Todos los nodos internos tienen 2 descendientes directos. Signup and view all the answers

En el recorrido en anchura de un árbol, ¿cómo se visita cada nodo?

Por niveles y de izquierda a derecha. Signup and view all the answers

¿Cuál de las siguientes opciones representa una aplicación práctica de los árboles?

Expresiones aritméticas y árboles de decisión. Signup and view all the answers

¿Qué se puede decir sobre la estructura de datos de un árbol binario?

Cada nodo contiene un valor, punteros a dos hijos y posiblemente un puntero al padre. Signup and view all the answers

En el contexto de un árbol binario, ¿qué afirmación sobre los nodos hoja es cierta?

Los nodos hoja contienen decisiones en árboles de decisión. Signup and view all the answers

En el recorrido en preorden de un árbol binario, ¿qué orden se sigue?

Nodo raíz, subárbol izquierdo, subárbol derecho. 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, real y string.
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, edad y DNI.
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.
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.
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.

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.