Estructura de Datos - Guía

Informática
Modalidad Abierta y a Distancia
Estructura de Datos
Guía didáctica
5 créditos
Ciclo Carrera
3 ▪ Informática
La Universidad Católica de Loja
Área Técnica
MODALIDAD ABIERTA Y A DISTANCIA
Departamento de Ciencias de la Computación y Electrónica

Sección Inteligencia Artificial
Estructura de Datos
Guía didáctica
5 créditos
Carrera Ciclo
Informática III
Autor:
Franco Olivio Guamán Bastidas
La Universidad Católica de Loja

Asesoría virtual:
www.utpl.edu.ec
ESTRUCTURA DE DATOS
Guía didáctica
Franco Olivio Guamán Bastidas
UNIVERSIDAD TÉCNICA PARTICULAR DE LOJA
4.0, CC BY-NY-SA
Diagramación y diseño digital:

EDILOJA Cía. Ltda.
Telefax: 593-7-2611418
San Cayetano Alto s/n
www.ediloja.com.ec
edilojainfo@ediloja.com.ec
Loja-Ecuador
Primera edición
ISBN digital - 978-9942-25-453-5
La versión digital ha sido acreditada bajo la licencia Creative Commons 4.0, CC BY-NY-SA:
Reconocimiento-No comercial-Compartir igual; la cual permite: copiar, distribuir y comunicar
públicamente la obra, mientras se reconozca la autoría original, no se utilice con fines comerciales
y se permiten obras derivadas, siempre que mantenga la misma licencia al ser divulgada. https://
creativecommons.org/licenses/by-nc-sa/4.0/deed.es
25 de febrero, 2019
2. Índice
2. Índice 4
3. Introducción 6
4. Bibliografía 8
4.1. Básica 8
4.2. Complementaria 8
5. Orientaciones generales para el estudio 10
6. Proceso de enseñanza-aprendizaje para el logro de competencias 14
PRIMER BIMESTRE
UNIDAD 1. ESTRUCTURAS LINEALES ESTÁTICAS 14
1.1. Cadenas (Strings) 15
1.2. Arreglos Unidimensionales 18
1.3. Operaciones con Arreglos 21
1.4. Arreglos Multidimensionales 30
1.5. Registros 33
Autoevaluación 1 37
UNIDAD 2. TIPOS DE DATOS ABSTRACTOS 40
2.1. Pilas y Colas 40
2.2. Conjuntos 43
2.3. Colas de prioridad 46
UNIDAD 3. ESTRUCTURAS LINEALES DINÁMICAS 50
3.1. Apuntadores 50
3.2. Listas Enlazadas 52
3.3. Implementación de pilas y colas con listas enlazadas 57
SEGUNDO BIMESTRE
UNIDAD 4. ESTRUCTURAS JERÁRQUICAS 62
4.1. Árboles 62
4.2. Árboles Binarios 66
4.3. Recorridos en Árboles Binarios 67
4.4. Árboles de Búsqueda Binaria 68
4.5. Árboles AVL 70
4.6. Tablas Hash 74
UNIDAD 5. GRAFOS 80
5.1. Conceptos y definiciones 81
5.2. Representación 83
5.3. Recorridos de grafos 86
7. Solucionario 93
8. Referencias bibliográficas 99
Guía didáctica: Estructura de Datos PRELIMINARES
3. Introducción
“Estructura de Datos” es una asignatura con 5 créditos, forma parte del grupo de
materias troncales de la carrera de Ingeniería en Informática de la Escuela de
Ciencias de la Computación, modalidad Abierta y a Distancia de la UTPL.
Las Estructuras de Datos son un medio para manejar grandes cantidades de

datos, logrando ser un punto clave para el diseño de algoritmos eficientes, así,
en algunos métodos formales de diseño y lenguajes de programación destacan
las estructuras de datos, en lugar de los algoritmos, como el factor clave de
organización en el diseño de software.
Esta asignatura tiene el propósito de estudiar las diferentes y particulares formas

de organizar datos en un medio computacional, con el fin de que puedan ser
utilizados de manera eficiente, debido a que algunos tipos de estructuras de datos
pueden ser adecuados para diferentes tipos de aplicaciones, y otros altamente
especializados para tareas específicas, es imprescindible conocer sus diferentes
formas de trabajo, lo que nos permitirá evaluar según el propósito, la más idónea
para ser adaptada a nuestros proyectos de desarrollo.
El estudio de la asignatura de Estructura de Datos es muy importante en el

área de las Ciencias de la Computación, puesto que permite conocer los
requerimientos y procesos necesarios para la creación, almacenamiento y
administración de información, permitiéndonos escoger los métodos adecuados
que brinden un correcto orden e interrelación a la información según su
naturaleza, optimizando así procesos de rendimiento, velocidad y redundancia de
la misma.
La asignatura se desarrolla en cinco unidades distribuidas en tres para el primer

bimestre y dos para el segundo bimestre. La primera unidad está dedicada
al estudio de las estructuras de datos estáticas como cadenas, arreglos
unidimensionales, arreglos bidimensionales y registros; la segunda unidad aborda
6 MODALIDAD ABIERTA Y A DISTANCIA

algunos de los más importantes tipos de datos abstractos como las pilas, colas,
conjuntos y colas de prioridad; la tercera unidad nos introduce en el estudio
de las estructuras de datos dinámicas, para lo cual empieza con la revisión de
los tipos de datos punteros y su utilización en las listas enlazadas, así como la
implementación de algunos TDA con este tipo de estructura de datos.
Para el segundo bimestre la unidad cuatro nos lleva al estudio de las estructuras
jerárquicas como los árboles y sus diferentes variaciones, así como al estudio
de las tablas hash y la resolución de colisiones, finalmente la quinta unidad está
completamente dedicada al estudio de los grafos.
Felicitaciones por su decisión de participar en este proceso de formación, le

deseamos el mejor de los éxitos. Recuerde que el premio al esfuerzo es el triunfo.

4. Bibliografía
4.1. Básica
Allen, M. (2013). Estructuras de datos en Java. (Cuarta edición). España:

Pearson.
Este texto proporciona una introducción práctica a las estructuras de

datos y algoritmos desde el punto de vista del pensamiento abstracto y
de la resolución de problemas. Ofrece flexibilidad a los profesores en el
tratamiento de los temas, minimizando la dependencia entre los distintos
capítulos.
Guamán, F. (2018). Guía didáctica de Estructuras de Datos. Loja – Ecuador:

Editorial Universidad Técnica Particular de Loja.
Esta guía didáctica es un instrumento complementario del texto básico,

permite al estudiante abordar de mejor manera el texto, haciendo
aclaraciones, proponiendo actividades para reforzar conceptos, ampliando
información, complementando temas no tratados en el texto básico
y reafirmando conocimientos, utilizando las técnicas y orientaciones
adecuadas para el caso.
4.2. Complementaria
Guardati, S. (2015). Estructuras de Datos Básicas (Primera edición). México:

Alfaomega.
En esta obra se presentan los principales conceptos de la programación

orientada a objetos (POO) y de las estructuras de datos lineales
implementadas. Permite aplicar el paradigma orientado a objetos en el

diseño implementación de soluciones basadas en la programación y a la

aplicación de estructuras de datos lineales en la solución de problemas.
Joyanes, L. Martinez, I. (2005): Metodología, Algoritmos y Estructuras de Datos,

Programación en C, España, Editorial Mc Graw Hill.
Este libro presenta de forma clara los algoritmos utilizados para manipular
la información de las estructuras compuestas, particularmente de arreglos
y matrices, adicionalmente al final de cada capítulo se presentan ejercicios
para desarrollar, además de problemas resueltos.

5. Orientaciones generales para el estudio
El reto de estudiar a distancia requiere de mucho esfuerzo, entrega, dedicación

y ante todo de organización, por ello debe hacer de esta actividad un trabajo
continuo y sistemático; organice su tiempo de manera que pueda verdaderamente
aprovechar los contenidos contemplados por la asignatura y el aporte que le dan
a su formación profesional.
Para el estudio de la presente asignatura le damos a conocer algunos materiales

y recursos didácticos que le servirán en su proceso de aprendizaje:
▪▪ El texto básico: ha sido seleccionado cuidadosamente del mercado,

considerando criterios de actualidad, rigor científico, didáctico - metodológico
y congruente con los componentes académicos.
▪▪ La guía didáctica: diseñada para orientar al estudiante sobre temas y textos

claves que le permitan saber el contexto del que se habla en esta asignatura,
ayudándole a obtener una mejor comprensión de los contenidos y aclarando
interrogantes que se presentaren; contiene ejercicios de autoevaluación que
le permitirán medir su grado de comprensión y la necesidad de tutoría por
parte del docente.
▪▪ El Entorno Virtual de Aprendizaje: donde podrá interactuar con sus

profesores a través de una orientación del trabajo semanal, usar la
mensajería electrónica para resolver inquietudes que se le presenten, foros,
desarrollo de ejercicios prácticos, publicación de recursos.
▪▪ La tutoría personal: para reforzar el proceso de aprendizaje usted dispone

de un profesor-tutor que le guiará, al cual podrá hacer las consultas que
requiera en un horario que a tiempo será publicado. Las tutorías las puede
hacer mediante el EVA, correo electrónico o directamente a través de la

línea telefónica, así que aproveche esta alternativa que la UTPL pone a su
disposición.
▪▪ La tarea: es una actividad teórica y práctica que acompaña a la guía

didáctica de cada una de las asignaturas, le permiten aplicar y reforzar
los conocimientos adquiridos mediante su desarrollo, y debe ser subida
al Entorno Virtual de Aprendizaje en las fechas para ello previamente
publicadas. La tarea tiene una valoración de seis puntos que, sumados a la
calificación de cuatro puntos por participación en las actividades síncronas
y asíncronas y diez puntos de evaluación presencial, darán un total de 20
puntos.
Damos algunos lineamientos que le ayudarán a aprovechar su tiempo y lograr

mejores resultados:
▪▪ Disponga de un lugar limpio y ordenado. Cuide de las condiciones

ambientales en cuanto a iluminación, temperatura y objetos que le rodeen
para que no lo distraigan. Pida que no le interrumpan mientras trabaja y
aléjese del teléfono y de la televisión.
▪▪ El tiempo que dedique a la lectura y desarrollo de los ejercicios es

fundamental, por lo tanto, deberá dedicar al menos 6 horas semanales,
recomendablemente en período de no menos de 2 horas. Puede ayudarse
con técnicas como el subrayado de los apartados más destacables,
esquemas, diagramas, cuadros sinópticos, resúmenes, mapas conceptuales,
que le ayudarán a comprender mejor el tema tratado.
▪▪ Hay que trabajar conjuntamente con el texto básico y la guía didáctica,

consultar en el diccionario las palabras cuyo significado no se conozca y
utilizarlas durante las conversaciones con otras personas.
▪▪ No siempre vamos a realizar nuestras tareas de la mejor forma, por eso no

hay que desesperarse si no se logra el éxito total en algún trabajo. Tenemos
que sacar enseñanzas de nuestros errores y falencias. Pero lo que debemos

observar es no dejar para los últimos días el estudio y preparación para el

examen.
▪▪ Recuerde que usted podrá recibir valiosa ayuda por parte de su profesor
tutor para la comprensión de los diferentes temas, por lo cual la correcta
comunicación con el mismo será fundamental, es por esto que debe
familiarizarse con las diferentes formas de comunicación implementadas
para su uso, ya sea por teléfono (consultar horario de tutoría en el EVA),
email, chat, y otras herramientas tecnológicas. Recuerde además que
existe una variada información en internet, bibliotecas digitales y también la
documentación que su profesor le proporciona a través del EVA.
▪▪ El plan docente contiene diferentes actividades sugeridas para cada unidad,

distribuidas en el tiempo, por lo tanto, trate de cumplir con estas según se lo
indica.
▪▪ Las autoevaluaciones que se presentan al final de cada unidad, así como

las que constan en el texto básico le ayudarán a asimilar de mejor manera
cada uno de los temas, por lo que su realización es de suma importancia
para afianzar el proceso de enseñanza aprendizaje. Una vez resueltas las
autoevaluaciones de la guía didáctica, puede comparar sus respuestas
con el solucionario al final de la guía. En caso de que su resultado no sea
satisfactorio le sugerimos volver a revisar los temas y acudir a su tutor para
aclarar sus dudas.

Con estas recomendaciones esperamos contribuir con el aprendizaje exitoso de la

asignatura. Como ayuda a la presente se utilizarán los siguientes focalizadores:
ICONO DESCRIPCIÓN
Se utilizará para aspectos importantes en los que se deba prestar
especial atención.
Se aplicará para solicitarle la lectura de una sección del texto

básico. Recuerde que debe centrarse en las partes indicadas en los
lugares donde encuentre este ícono.
Para realizar los ejercicios y actividades recomendadas, no

son ejercicios obligatorios pero se sugiere realizarlos ya que le
ayudarán a medir su nivel de asimilación de los contenidos de la
asignatura.
Se utilizará cuando se requiera ampliar la información con material
en línea o que no es del texto básico.

Guía didáctica: Estructura de Datos PRIMER BIMESTRE
6. Proceso de enseñanza-aprendizaje para el logro de competencias
PRIMER BIMESTRE
UNIDAD 1. ESTRUCTURAS LINEALES ESTÁTICAS
“Cada vez que decimos; «No sé», nos cerramos

la puerta de nuestra propia fuente de sabiduría,
que es infinita”
Louise L. Hay
Es recomendable realizar la descarga de un entorno de desarrollo de

Java, de libre utilización como NetBeans, el cual permita ejecutar los
ejemplos que se plantean en la presente guía didáctica.
Como usted recordará de la asignatura de Fundamentos de la Programación,

el tipo de datos es la propiedad que indica o determina el rango de valores que
puede adoptar una variable, también conocido como su dominio; del tipo de datos
se determina las operaciones que se pueden aplicar y cómo esta información es
representada internamente por el computador.
Es indispensable conocer los diferentes tipos de datos, así como el manejo

de las diferentes estructuras de control de flujo de programas, recursividad y
conocimientos básicos de programación.
Como recordatorio de lo mencionado observe a continuación la figura 1, en la

cual se resume los diferentes tipos de estructuras de datos con los que se cuenta
actualmente.

Figura 1. Estructuras de datos estáticas y dinámicas.
Como puede observar, entre estas estructuras tenemos los tipos de datos
estáticos, que son aquellos en los que el tamaño en memoria es definido antes de
la ejecución del programa y no puede ser modificado durante su ejecución.
Durante esta unidad abordaremos el estudio de los tipos de datos estáticos

compuestos conocidos como “Cadenas o Strings” y “Arreglos”.
Si no cuenta con los conocimientos básicos mencionados, se sugiere

revisar los contenidos impartidos en la asignatura de “Fundamentos
de la Programación”.
1.1. Cadenas (Strings)
Una cadena es definida como una secuencia de caracteres interpretados como un

único dato. Su longitud puede ser fija o variable por lo que, además de saber que
están constituidas por caracteres alfanuméricos, debemos conocer su longitud.
Una variable de tipo string puede almacenar una palabra, o una frase; un
nombre o una dirección con espacios y números incluidos; su longitud puede ser
determinada indicando el máximo número de caracteres alfanuméricos que podría
contener.

Revise el apartado “Cadenas” del texto básico. Note la forma en la

que el lenguaje JAVA realiza la declaración de este tipo de variables,
así como las diferentes variaciones existentes para la concatenación
de cadenas.
Una cadena de caracteres, sin importar el lenguaje que se utilice (o

en su gran mayoría), siempre se escribe entre comillas simples o
dobles, ejem.: “¡Hola mundo!” u ‘¡Hola mundo!’. La diferencia entre
ellas puede variar dependiendo del lenguaje.
Entre las operaciones que se pueden realizar sobre datos de tipo cadena
tenemos:
• Asignación: Almacena una cadena de caracteres en una variable de

tipo cadena; la información a guardar puede ser una constante, una
variable o una expresión que produzca un dato tipo cadena.
• Extracción (sub cadena): Permite extraer una cadena (sub cadena)

a partir de otra, tomando un tramo consecutivo de la cadena inicial.
Ejemplo:
Extracto de código 1. Asignación de un valor a una variable de tipo cadena.
Denotamos por (n:m) la extracción de metacaracteres tomados a partir

del lugar n, entonces:
Extracto de código 2. Extracción de metacaracteres.
Es una sub cadena que contiene la palabra “Técnica”, teniendo en

cuenta el caracter de vacío.

• Concatenación: Formar una nueva cadena a partir de dos previamente

existentes. Ejemplo:
Extracto de código 3. Variables de tipo cadena.
La concatenación se realiza usando el signo de suma (+) así:
Extracto de código 4. Concatenación de cadenas.
El resultado quedaría: “Juan Carlos López”
Nótese que se ha agregado un espacio en la concatenación para que

haya una separación entre el nombre y el apellido.
• Obtención de longitud: La longitud de una cadena es un dato de tipo

entero, cuyo valor es el número de caracteres que esta contiene.
Normalmente existe en la mayoría de lenguajes de programación
de alto nivel una función específica para calcular la longitud de una
cadena.
• Comparación de cadenas: Ya mencionado en el apartado

“Comparación de cadenas” del texto básico.
Note que en JAVA existen algunas diferencias especiales en cuanto

al tratamiento de cadenas en comparación con otros lenguajes de
programación. Especialmente con operaciones como concatenación,
conversión y comparación.

Actividades recomendadas
Como estrategia de aprendizaje, a continuación le propongo la

realización de los siguientes ejercicios.
1. Realice un cuadro comparativo entre JAVA y otros tres

lenguajes de programación, con respecto al tratamiento de
estructuras de tipo STRING.
¿Qué le pareció el ejercicio? Interesante verdad.
1.2. Arreglos Unidimensionales
Una vez revisados los conocimientos previos, es hora de empezar con el estudio
de los arreglos unidimensionales, mismos que podrán ser utilizados en ejercicios
comunes de tratamiento de información a nivel de listas.
En algunos textos a los arreglos se los denomina también matrices o

vectores, pero debemos tener presente que nos estamos refiriendo a
la misma estructura.
Revise el apartado “Declaración, asignación y métodos” del tema

“Matrices” del texto básico. Preste atención a la forma de declarar,
definir el tamaño, subíndices y almacenamiento. Utilice técnicas como
subrayado, para lograr una mejor comprensión del tema.
Teniendo claro el concepto de arreglos o matrices, podemos decir que en términos

generales un arreglo puede ser utilizado en casos en los que se desea trabajar
con un conjunto de elementos de un mismo tipo, así como que, el acceso a estos
elementos del arreglo se realizará a través de un subíndice pre establecido.

Para complementar la información, y en medida de las posibilidades,

puede consultar el apartado “Componentes de un arreglo” de la
bibliografía complementaria de Guardati. Caso contrario, realice una
búsqueda online con el tema “Componentes de un arreglo AND
Estructuras de datos”. Existe muy buena información disponible.
En resumen, las principales características de los arreglos son:
• Finitos: se determina previamente el número de elementos que lo

formarán.
• Homogéneos: Todos los elementos deben ser del mismo tipo.
• Ordenados: de acuerdo a un subíndice preestablecido.
• Varias dimensiones: pueden ser unidimensionales o
multidimensionales.
La mayoría de los lenguajes de programación utilizan la indexación

basada en cero, que consiste en que el subíndice de inicio del arreglo
es el cero. Por tanto si hablamos de un arreglo con 10 elementos,
sus subíndices serán desde 0 a 9.
La figura 2 representa un arreglo unidimensional de diez elementos con valores

aleatorios representando edades de personas.
Figura 2. Representación gráfica de un arreglo unidimensional.
En este arreglo es importante resaltar lo siguiente:
• Tiene un único identificador: edades.

• Su tamaño es de: 10 elementos.
• Cada elemento es identificado por un subíndice. Ej: en el subíndice 3
del arreglo “edades” se encuentra el elemento 29, que sería el cuarto
elemento.
De acuerdo a lo revisado previamente en el texto básico, una de las definiciones

del arreglo de la figura 2 en Java podría ser:
Extracto de código 5. Definición de un arreglo de tipo entero.
El ingreso de datos en un arreglo puede ser de varias formas, dependiendo

de la necesidad y las circunstancias, a veces puede ser necesario realizarlo al
momento de definir el arreglo y en otras ocasiones ingresar datos desde una
fuente externa (a la aplicación), que puede ser desde la consola o de algún medio
de almacenamiento e incluso desde alguna librería o programa.
Finalizado el presente apartado se plantean ejercicios que permiten afianzar

los conocimientos, por lo que deberá realizar el respectivo análisis y desarrollo
basándose en los contenidos anteriormente tratados.

1. Si tuviera un arreglo de caracteres con las letras del texto

“ESTRUCTURA” ¿cuál sería el índice de la letra “C”?.
2. Un curso de computación tiene 50 alumnos matriculados y

usted debe diseñar un arreglo para registrar las notas de los
alumnos; responda las preguntas y programe en Java las
sentencias requeridas a continuación.
a. ¿De qué tipo de dato lo definiría?

b. ¿Qué tamaño tendría el arreglo?
c. ¿Cuáles son los índices inferior y superior del arreglo?
d. Realice la definición del arreglo en Java.

3. Realice un programa en Java que permita ingresar un

arreglo de enteros de 5 elementos, y realizar las siguientes
operaciones:
a. Mostrar o leer cada uno de los elementos ingresados.

b. Lea el elemento que se encuentra en la posición 3.
¿Cómo resultaron los ejercicios?, espero que muy bien. En el siguiente apartado
continuamos con el estudio de los arreglos.
1.3. Operaciones con Arreglos
Una vez estudiados los aspectos fundamentales de los arreglos, centraremos

nuestra atención en revisar algunos algoritmos y técnicas para la manipulación
de datos de este tipo de estructuras, es importante que ponga especial atención
en ellos ya que son la base para desarrollar y resolver aplicaciones específicas
utilizando cualquier lenguaje de programación.
Entre las operaciones que pueden aplicarse a arreglos tenemos: lectura, escritura,
asignación, búsqueda, inserción, eliminación, actualización y ordenación; además
de las estudiadas en el apartado anterior como: declaración entre otras.
Dado que el texto básico no cuenta con una sección dedicada a las
operaciones con arreglos, iré desarrollando resumidamente cada una
de ellas en la guía didáctica.
Para complementar la información sobre operaciones con arreglos a

continuación expuesta, usted puede consultar desde el apartado
“Lectura, impresión y asignación” hasta el apartado “Otras
operaciones” del texto complementario de Guardati. También puede
consultar el REA “REA Arrays y ArrayList.pdf” publicado en el EVA que se refiere a
este tipo de información.

1.3.1. Lectura
Este proceso consiste en insertar un valor en cada uno de los componentes

del arreglo, proceso que debe realizarse elemento por elemento mediante la
utilización de subíndices. Generalmente el proceso más recomendable para
la realización de esta operación es a través de un ciclo for que me permita ir
leyendo y ubicando los valores en el lugar correspondiente.
Observe el extracto de código 6, tomada de Guardati (2015); en la cual se realiza

el ingreso de datos del arreglo de la figura 2, previamente observada.
Extracto de código 6. Ingreso de información en un arreglo.
Debemos tener claro que aunque previamente hayamos declarado

un arreglo de n celdas o casillas como en el extracto de código 5, no
necesariamente se deberán leer todas ellas. En el ejemplo propuesto
se leerán totalEdades celdas, variable que necesariamente deberá
tener un valor entre >=1 y <=n.
1.3.2. Impresión
En el caso de contar con un arreglo con información previamente ingresada y que

esté ocupando posiciones consecutivas, se puede recurrir también a la utilización
de un ciclo for que nos permita posicionarnos en cada una de las celdas para
imprimir su contenido, como se puede observar en el extracto de código 7 citada
desde Guardati (2015).
Extracto de código 7. Impresión de información desde un arreglo.

En este caso se imprimirá primeramente el título “Edades” y luego de un salto de

línea se imprimirán los elementos contenidos en cada celda del arreglo, seguido
de un espacio en blanco.
1.3.3. Asignación
Podemos citar algunos casos de asignación como:
• Asignación a una determinada casilla,

• asignación a las primeras n casillas,
• asignar los valores de todo el arreglo a otra variable de tipo arreglo,
• asignación a posiciones arbitrarias bajo un criterio determinado.
Así, analizando estos casos tendríamos los siguientes extractos de código:
Ejemplo 1. Asignación del valor 27 en la quinta posición del arreglo edades.
Extracto de código 8. Asignación de información a una celda determinada.
Ejemplo 2. Asignación de un valor 0 a todas las celdas del arreglo edades.
Extracto de código 9. Inicialización de un arreglo con un valor 0.
Ejemplo 3. Asignación de un arreglo a otra variable de tipo arreglo; para que este
procedimiento pueda ser ejecutado, ambos arreglos deberán ser del mismo tipo,
así como la variable destino no requiere ser instanciada, solo creada.
Extracto de código 10. Copia de información entre variables de tipo arreglo.

Ejemplo 4. Asignación del resultado de la expresión 2i, con valores de i=0, 2, 4 …,

hasta totalEdades -1 en las celdas correspondientes a los índices pares.
Extracto de código 11. Almacenamiento de información proveniente de una expresión.
La figura 3 muestra el resultado de la ejecución de esta porción de código.
Figura 3. Resultado ejecución de código.
1.3.4. Búsqueda
Permite la recuperación de un dato almacenado. Existen diversos algoritmos que

varían en complejidad y eficiencia; para nuestro estudio nos centraremos en dos
de los más conocidos como son las búsquedas secuencial y binaria.
Búsqueda secuencial. Para esta búsqueda no es necesario que el arreglo esté

ordenado; compara el elemento buscado con cada uno de los elementos, hasta
encontrarlo o hasta llegar al fin del mismo. Véase el extracto de código 12.
Extracto de código 12. Algoritmo de búsqueda secuencial.
En este subprograma se seguirá buscando el elemento mientras no se llegue al

final del arreglo o mientras no se encuentre el elemento buscado.

El tipo de respuesta del subprograma puede adaptarse a la utilidad

que se le dé a la misma, en este caso se obtendrá la posición en
donde se encuentra el elemento buscado, pero el programa puede
ser adaptado para dar solamente una respuesta de tipo boolean.
Para ampliar el tema, revise el apartado “Búsqueda secuencial” del

texto básico.
Búsqueda binaria. Para este tipo de búsqueda debemos necesariamente contar

con un arreglo previamente ordenado. Este algoritmo realiza comparaciones
para determinar si el valor buscado está ubicado en el punto medio del arreglo o
estaría en su mitad superior o inferior. De no encontrarse en el primer paso y una
vez determinada la posible ubicación, se subdivide nuevamente el arreglo, y así
sucesivamente hasta encontrar el valor o determinar su inexistencia.
A continuación se presenta el subprograma que implementa el algoritmo de

búsqueda binaria sobre un arreglo ordenado de números enteros.
Extracto de código 13. Algoritmo de búsqueda binaria.
Al igual que en el caso de la búsqueda secuencial, este algoritmo nos devolverá la

posición del elemento buscado, o un valor de -1 en el caso de que tal elemento no
se encuentre en el arreglo.

Es importante que usted revise el apartado “Búsqueda binaria” del

texto básico, dado que este método es mucho más óptimo, debemos
conocer a fondo cuáles son sus verdaderas ventajas ante otros
métodos conocidos.
1.3.5. Inserción
Esta operación permite agregar nuevos elementos a un arreglo existente en el

caso de que aún cuente con espacios disponibles.
Es importante conocer si el arreglo está previamente ordenado o no, ya que

se deberá respetar las condiciones previamente establecidas. Así mismo es
importante conocer si entre los requerimientos previos se permite o no el ingreso
de datos repetidos, puesto que de ello dependerá en gran medida la variación del
algoritmo.
A continuación veremos algunos subprogramas que abordan los requerimientos

antes mencionados.
En el primer caso, inserción de un elemento nuevo en un arreglo desordenado

sin importar si se repiten o no, quedaría como en el extracto de código 14 a
continuación expuesto.
Extracto de código 14. Inserción de un nuevo elemento en un arreglo desordenado.
En este caso, n representa el número de elementos existentes en el

arreglo, y si este es menor a su tamaño, nos indica que aún hay
espacios disponibles. Así mismo, y debido a que los subíndices
empiezan en 0, n sería el número del primer subíndice libre.

En el caso de que se deba insertar un nuevo elemento en un arreglo

desordenado, pero haya que controlar que no existan elementos repetidos,
previamente se deberá solicitar una búsqueda secuencial que me indique que
dicho elemento no se encuentra en el arreglo, caso contrario no se realizaría el
nuevo ingreso, así:
Extracto de código 15. Inserción de elemento con control de repetidos.
Según este código, una vez constatada la disponibilidad de espacio,

se procede a realizar una búsqueda mediante el programa realizado
en el apartado anterior para verificar la inexistencia del elemento.
Para ingresar un nuevo elemento sin importar si se repite o no, se debe seguir la
siguiente secuencia de pasos: verificar si existe espacio disponible, encontrar la
posición a insertar, se recorre todos los elementos una posición a la derecha para
hacer espacio e insertar el nuevo elemento.
Observe el código para este propósito diseñado.
Extracto de código 16. Inserción en una posición determinada.

Usted debe diseñar las funciones necesarias para obtener la posición

en donde se debe insertar el nuevo elemento y realizar el
desplazamiento de los elementos una posición a la derecha.
Una variación de este programa sería la verificación de que no existan elementos

repetidos, lo cual se realizaría de la siguiente manera:
Extracto de código 17. Inserción sin elementos repetidos.
Qué le han parecido los temas revisados hasta ahora, si les ponemos
la suficiente atención a ellos, no son difíciles de entender. Vamos a
revisar otras operaciones que podemos realizar con arreglos.
1.3.6. Eliminación
La eliminación de un elemento implica primeramente la búsqueda de dicho

elemento en el arreglo, una vez determinada su existencia, se realizará una
eliminación lógica del mismo, al hacer que todos los elementos de su derecha
recorran una casilla hacia la izquierda y reduciendo en una unidad el número
de elementos existentes en el arreglo. Este procedimiento es indiferente de si
se encuentre o no ordenado o si tiene elementos repetidos, lo cual implicará se
elimine el primero encontrado. El siguiente código resuelve este problema.

Extracto de código 18. Eliminación de un elemento.
En este código utilizamos el método secuencial previamente

realizado. Usted debe diseñar el método necesario para realizar el
desplazamiento de los elementos una posición a la izquierda.
1.3.7. Ordenación
Existen algunos algoritmos que difieren tanto en su complejidad como en

rendimiento; a continuación revisaremos los algoritmos más conocidos y sus
codificaciones, para ello le recomiendo realizar la siguiente actividad:
Realice una completa revisión del archivo “REA_Algoritmos de

Ordenamiento.pdf” que podrá descargarlo desde el Entorno Virtual de
Aprendizaje.
Como usted habrá podido observar en el archivo antes mencionado, los

procedimientos iterativos son fáciles de implementar y comprender, pero pueden
requerir un número mayor de iteraciones que aquellos procedimientos recursivos
para poder lograr el objetivo deseado. Así mismo, aunque los procedimientos
recursivos utilizan menos iteraciones, pueden consumir una mayor cantidad de
recursos de nuestro ordenador, por la misma naturaleza de la recursividad.
Es recomendable que usted realice la programación de cada uno de

los ejemplos sobre ordenación de arreglos expuestos en el texto
básico para comprobar su funcionamiento.


1. Realice la programación del método “obtenerPosición” que se

utiliza en el ejemplo para la inserción de un nuevo elemento.
2. Realice la programación del método “desplazarDerecha” que se

utiliza en el ejemplo para la inserción de un nuevo elemento.
3. Realice la programación del método “desplazarIzquierda” que

se utiliza en el ejemplo para la eliminación de un elemento.
4. Realice un programa completo que permita realizar todas las

operaciones con arreglos estudiadas, de acuerdo a una opción
leída por teclado.
5. Implemente el algoritmo QuickSort en el programa antes

diseñado.
¿Cómo resultaron los ejercicios?, espero que muy bien. Ahora avanzaremos con
el estudio de los arreglos.
1.4. Arreglos Multidimensionales
Una vez abordados los arreglos unidimensionales, ampliaremos estos conceptos

aplicándolos sobre arreglos de dos o más dimensiones. Su lógica no difiere en
gran medida de las ya revisadas, pero se debe tener en cuenta que se aumentará
un índice más por cada nueva dimensión del arreglo y en consecuencia para su
recorrido se utilizará un proceso o sentencia de control repetitiva más por cada
nueva dimensión.

Revise el apartado “Matrices multidimencionales” del texto básico.

Preste atención al código mostrado en la figura 2.9, la forma de
declarar y acceder a matrices bidimensionales, así como el aumento
de sentencias de control for para el acceso, en comparación con los
programas utilizados para arreglos unidimensionales.
Gráficamente, un arreglo bidimensional es representado como se muestra en la

figura 4:
Figura 4. Estructura gráfica de una matriz
“Los arreglos, independientemente de la cantidad de dimensiones que tengan,

tienen las características ya mencionadas para arreglos de una dimensión. Es
decir, son estructuras estáticas, finitas, homogéneas y ordenadas de datos”
(Guardati, 2015)
Como habrá podido leer en la documentación recomendada, en Java un arreglo

bidimensional es tratado como un arreglo de arreglos, por lo cual debemos
tener un especial cuidado cuando nos referimos a una determinada columna,
especialmente para conocer su tamaño.
En la matriz de la figura 4 por ejemplo, si deseamos conocer su tamaño (cuántas

filas y cuántas columnas), y suponiendo que el nombre del arreglo sea “matriz1”,
deberíamos proceder de la siguiente forma.
Extracto de código 19. Obtención de tamaño de filas y columnas.

Como se ha mencionado previamente, el realizar un recorrido de un arreglo

bidimensional requiere la utilización de dos ciclos repetitivos anidados, los cuales
representarán a las filas y columnas respectivamente. Este procedimiento es muy
utilizado para un gran número de ejercicios que se puedan realizar con arreglos
como lo veremos en el siguiente ejemplo:
Ejemplo 5. Asignación de elementos numéricos desde teclado en un arreglo

bidimensional.
Extracto de código 20. Inserción de elementos en arreglo bidimensional.
Para finalizar el presente apartado se plantea los siguientes ejercicios que le

permitirán afianzar sus conocimientos, por lo que deberá realizar el respectivo
análisis y desarrollo basándose en los contenidos anteriormente tratados.

1. Realice la programación de un método que permita presentar

los elementos de un arreglo bidimensional.
2. Realice la programación de un método que permita obtener la

matriz traspuesta de una matriz previamente leída por teclado.
3. Realice la programación del método que permita contar el

número de elementos pares dentro de una matriz de n X m
elementos.

1.5. Registros
Como lo hemos mencionado, las variables simples pueden almacenar un solo

dato mientras que los arreglos pueden almacenar un conjunto de datos del mismo
tipo, pero a menudo necesitaremos trabajar sobre datos de diversos tipos, en los
cuales ni las variables simples ni los arreglos son adecuados.
Este tipo de problema es resuelto por los lenguajes de programación mediante

los registros, que son un conjunto de datos de diferentes tipos, lógicamente
relacionados y agrupados bajo un nombre común. Cada uno de estos elementos
del registro es conocido con el nombre de campo. Un ejemplo de este tipo de
estructura lo podemos ver en la figura 5.
Figura 5. Ejemplo de registro.
1.5.1. Declaración de registros
Básicamente la declaración de registros se realiza enumerando cada uno de los

campos que lo forman como se puede observar en la figura 6.
Figura 6. Declaración básica de un registro.

La definición del registro de la figura 5 en C++, sería:
Extracto de código 21. Definición de un registro en C++.
Aunque este sistema es utilizado por algunos lenguajes de programación, JAVA

al ser un lenguaje orientado a objetos lo realiza de forma diferente, debiendo
necesariamente crearse una clase con la estructura deseada, como se muestra a
continuación.
Extracto de código 22. Definición de un registro en JAVA.
1.5.2. Acceso a registros
Debemos tener presente que el lenguaje JAVA también tiene sus propios métodos
para el ingreso y acceso a la información, por lo cual en la clase mencionada en
el extracto de código 22, se debe crear el o los respectivos constructores y los
correspondientes métodos GET y SET, como se muestra en los ejemplos.
Extracto de código 23. Constructores para la definición de registros.

Extracto de código 24. Métodos Get y Set.
Así mismo, debemos tener presente que al ser los registros un tipo de datos,
podemos con ellos realizar la creación de arreglos de registros como se puede
apreciar en la figura 7, cuyo comportamiento sería similar a los arreglos antes
estudiados.
Figura 7. Arreglo de registros
Es recomendable que haga una revisión de los métodos de acceso a

tipos de datos compuestos en JAVA, existen muchos recursos
didácticos disponibles online.

1. Realice un programa que permita crear un arreglo en el que se

almacenen los datos de cinco estudiantes (Cédula, nombre,
dirección, edad, teléfono, sexo). Debe poder ingresar y
presentar los datos del arreglo.

Esperamos que esta unidad haya cumplido las expectativas de adquirir

conocimientos básicos y destrezas en el ámbito de las estructuras de datos
estáticas, recuerde que si existe algún tema que aún no está claro se puede
comunicar con sus profesores / tutores a través del EVA, correo electrónico, línea
telefónica.
Hemos culminado el estudio de la primera unidad y es hora de realizar una

autoevaluación para identificar el avance progresivo de su aprendizaje, le
invitamos a desarrollarla y le deseamos éxitos, recuerde que usted puede
comprobar sus respuestas con el solucionario ubicado al final de la guía didáctica.

Autoevaluación 1
Lea detenidamente cada una de las siguientes preguntas planteadas y determine

la alternativa correcta.
1. Una de las características de los tipos de datos estáticos es:
a. Su tamaño en memoria puede variar dependiendo de la necesidad del

programa.
b. Dependiendo del programa, pueden tener un tamaño fijo o variable.
c. Su tamaño en memoria debe ser definido antes de la ejecución del
programa y no puede ser modificado durante su ejecución.
2. Entre las características de los datos de tipo String o cadenas tenemos:
a. Permite realizar operaciones con números enteros.

b. Pueden representar variables con los valores Verdadero o Falso
c. Permiten la manipulación de su contenido a través de la extracción de
parte de ella.
3. Al decir que los arreglos deben ser homogéneos, nos referimos a que:
a. Todos los datos deben estar ordenados de acuerdo a un subíndice

preestablecido.
b. Pueden ser unidimensionales o multidimensionales.
c. Que todos los elementos deben ser del mismo tipo de datos.

4. Los arreglos:
a. Permiten el almacenamiento solamente de datos simples.

b. No permiten el almacenamiento de datos de tipo compuesto.
(Registros)
c. Pueden ser utilizados tanto para el almacenamiento de datos simples
como compuestos.
5. El ingreso de datos en un arreglo:
a. Se debe hacer exclusivamente en el momento de su definición.

b. No puede ser realizada por métodos fuera de la clase main.
c. Puede ser realizada al momento de su definición o mediante una fuente
externa.
6. Entre las principales operaciones que pueden aplicarse a arreglos tenemos:
a. Presentación, multiplicación, diferencia, eliminación.

b. Modificación, búsqueda, ordenación, eliminación.
c. Lectura, suma, resta, inserción,
7. La operación de Búsqueda Binaria en arreglos:
a. Puede ser ejecutada sobre cualquier tipo de arreglos (ordenados o

desordenados).
b. Necesita que sus datos sean de tipo entero.
c. Puede ser implementada sobre arreglos previamente ordenados.
8. Cuál de las siguientes afirmaciones no corresponde a una inicialización de

un arreglo bidimensional:
a. int[ ][ ] A = new int[n][m];

b. int A = new int[ ][ ];
c. int A[ ][ ] = {{7,14,8,3},{6,19,7,2},{3,13,4,1}};

9. Al referirse a arreglos bidimensionales, generalmente se nombra sus

componentes en el siguiente orden:
a. Filas, columnas.
b. Columnas, filas.
c. El orden es indiferente.
10. Para conocer el número de columnas de un arreglo en Java, debemos

utilizar la siguiente expresión:
a. columnas = A.length;
b. columnas = A.length.length;
c. columnas = A[0].length

UNIDAD 2. TIPOS DE DATOS ABSTRACTOS
El problema con el mundo es que la gente

inteligente está llena de dudas, mientras que la
gente estúpida está llena de certezas.
Charles Bukowski
Un TDA, Tipo de Dato Abstracto, es un conjunto de datos u objetos asociados a

un grupo de operaciones; se provee de una interfaz para permitir la realización de
operaciones, abstrayéndose de su implementación; puede ser realizado utilizando
distintas estructuras de datos y proveer la misma funcionalidad.
En esta unidad revisaremos algunos TDA básicos como pilas y colas, conjuntos,
mapas y colas de prioridad.
2.1. Pilas y Colas
2.1.1. Pilas
Una pila es una lista que permite almacenar y recuperar datos, el modo de acceso
a los elementos que la componen es conocido como estructura de tipo LIFO (Last
In First Out, o “último en entrar, primero en salir”).
El manejo de los datos en este tipo de estructura se da mediante dos operaciones

básicas: apilar (Push), que consiste en colocar un objeto en la cima de la pila,
y su operación inversa: retirar (Pop), que retira el último elemento apilado. Se
tiene acceso solamente al elemento ubicado en la parte superior de la pila
(generalmente denominado TOS, Top of Stack). La operación POP permite la
obtención de este elemento, que es retirado de la pila permitiendo el acceso al
anterior a él, que pasa a ser el último, el nuevo TOS.

Ubíquese en el capítulo “La API de Colecciones” del texto básico y

revise el apartado “Pilas y colas”.
Entre algunas de las aplicaciones que se suele implementar con pilas tenemos:
evaluación de expresiones en notación postfija, reconocedores sintácticos de
lenguajes independientes del contexto, implementación de recursividad.
En un sistema operativo cada proceso tiene un espacio de memoria (pila) para

almacenar valores y llamadas a funciones.
Un ejemplo de pila es el “portapapeles” en Word, en donde se

almacenan las acciones realizadas (push), y mediante la acción
Ctrl+Z (pop), deshacemos la última acción realizada y así la siguiente
y la siguiente.
Las pilas pueden ser implementadas mediante estructuras estáticas como

arreglos o con estructuras dinámicas como listas enlazadas.
Ubíquese en el capítulo “Pilas y colas” del texto básico, revise el

primer apartado dedicado a “Pilas”.
La implementación de una pila con arreglos, involucra tomar consideraciones

como el límite de elementos del arreglo, posiciones de variables (TOS), etc.
Este tipo de estructura también se puede implementar mediante la utilización de

listas enlazadas, lo cual analizaremos más adelante.
2.1.2. Colas
Esta estructura de datos se caracteriza por ser una secuencia de elementos en

la que la operación de inserción push se realiza por un extremo y la operación de
extracción pop por el otro. Es conocida como estructura FIFO (First In First Out),
debido a que el primer elemento en entrar será también el primero en salir.

Son utilizadas en sistemas informáticos, transportes y operaciones de

investigación, donde los objetos, personas o eventos son tomados como datos
almacenados para su posterior procesamiento. Una analogía del concepto
sería, aquella que se forma para ser atendida en la ventanilla de alguna
institución, atendiéndose en primer lugar a la persona del frente de la cola y así
sucesivamente hasta atender al último en llegar.
Las colas pueden ser implementadas mediante estructuras estáticas como

arreglos (ver figura 8) o con estructuras dinámicas como listas enlazadas.
Figura 8. Cola implementada con arreglos
Ubíquese en el capítulo “La API de Colecciones” del texto básico,

revise el apartado “Colas”. Para complementar esta información,
ubíquese en el capítulo “Pilas y colas” del texto básico, revise los
apartados “Colas”. Note como se complementa la información.
Como puede usted ver, la implementación de una cola mediante arreglos resulta
un poco cara computacionalmente hablando, ya que debido a que el elemento
que sale de la cola con el procedimiento Pop, siempre deberá ser el primero que
ingresó a ella, lo cual implica que todo el resto de elementos presentes en la cola,
sin importar su número, deberán recorrer un puesto hacia la izquierda por cada
Pop realizado.

La implementación de un mecanismo matricial de cola con encadenamiento

circular, resulta un poco difícil de controlar, especialmente cuando el número de
elementos a ingresar a la cola es mayor al número de celdas disponibles.

1. Realice la implementación en Java de un programa que nos

permita realizar las tareas de Push y Pop en una Pila, mediante
arreglos.
2. Realice la implementación en Java de un programa que

nos permita realizar las tareas de Push y Pop en una Cola,
mediante arreglos.
2.2. Conjuntos
Revise en el apartado “Conjuntos” del texto básico y las clases de

Java vinculadas a la utilización de conjuntos
Como lo habrá leído, un conjunto es un grupo de elementos sin orden concreto ni

valores repetidos, y pueden ser implementados mediante diversas estructuras de
datos.
Entre las principales operaciones que pueden ser implementadas con conjuntos
tenemos: unión, intersección, diferencia, complemento, entre otras. Así, a
continuación podrá observar breves ejemplos de cómo podría implementarse
cada una de ellas.
Unión, representa a un nuevo conjunto C, el cual contiene todos los elementos,

que pertenecen por lo menos a uno de los conjuntos A o B dados.

Extracto de código 25. Unión de conjuntos
Intersección, representa a un nuevo conjunto C, el cual contiene los elementos

comunes a los conjuntos de partida.

Extracto de código 26. Intersección de conjuntos.
Diferencia, es una operación que resulta en otro conjunto, cuyos elementos

son todos aquellos en el primero de los conjuntos iniciales que no estén en el
segundo.
Extracto de código 27. Diferencia de conjuntos.

Diferencia simétrica, es una operación que resulta en otro conjunto cuyos

elementos son aquellos que pertenecen a alguno de los conjuntos iniciales, sin
pertenecer a ambos a la vez.
Extracto de código 28. Diferencia simétrica de conjuntos.
2.3. Colas de prioridad
Como ya lo habíamos visto con anterioridad, una Cola es una estructura FIFO
en la cual los primeros elementos que fueron ingresados en la cola, serán los
primeros en ser removidos o atendidos; así como los nuevos elementos a ingresar
a la cola serán colocados al final de la misma.

Sin embargo, pueden existir casos en los cuales debido a la importancia de

ciertos procesos, deban estos ser atendidos con mayor prioridad sin importar su
orden de llegada; esto implica que se deban implementar ciertos algoritmos que
evalúen este tipo de casos, sin por ello negar la atención al resto.
Las colas de prioridad permiten por medio de la evaluación de un determinado

criterio, dar solución a este tipo de problemas.
Revise en el apartado “Colas de prioridad” del texto básico y los

ejemplos de aplicación de esta estructura ahí citados.
Como usted ha podido observar, JAVA implementa ciertas librerías adecuadas

para la utilización de colas de prioridad.
Hemos concluido con la segunda unidad de nuestro plan académico, es el

momento adecuado para autoevaluar sus avances, para lo cual lo invito a resolver
la segunda autoevaluación.

Autoevaluación 2
Lea detenidamente cada una de las siguientes afirmaciones y determine si son

verdaderas o falsas.
1. ( ) Un Tipo Abstracto de Datos es un grupo de datos que cumplen

determinadas características, son asociados a ciertas operaciones
y pueden ser implementados mediante distintas estructuras de
datos.
2. ( ) El TAD “Pila”, también es conocido como una estructura FIFO
3. ( ) Una operación “Push”, sin importar el tipo de datos, refiere al

procedimiento que permite la inserción de un nuevo elemento.
4. ( ) Mediante la implementación de los métodos correctos, se puede

extraer datos desde una pila, sin importar si haya sido o no el
último en ingresar.
5. ( ) Una operación “Pop”, es el nombre que se le da a aquella que me

permite obtener el primer objeto ingresado en una cola.
6. ( ) Las operaciones FIFO (First In First Out), son características del
TAD Cola.
7. ( ) Un conjunto es definido como un grupo de elementos sin un orden

concreto ni valores repetidos.
8. ( ) La operación de Unión de conjuntos, permite crear un nuevo

conjunto con los elementos que son comunes en los conjuntos
iniciales.

9. ( ) La diferencia de conjuntos nos da como resultado un conjunto

cuyos elementos pertenecen a alguno de los conjuntos iniciales,
sin pertenecer a ambos a la vez.
10. ( ) Las colas de prioridad, permiten mediante la implementación de

un nuevo parámetro, tener un nuevo criterio de evaluación para la
atención de los elementos de una cola.

UNIDAD 3. ESTRUCTURAS LINEALES DINÁMICAS
“Un experto es aquel que sabe cada vez

más sobre menos cosas, hasta que sabe
absolutamente todo sobre nada.. es la persona
que evita los errores pequeños mientras sigue su
avance inexorable hacia la gran falacia”
Definición de Webwer - Corolario de

Weinberger (Leyes de Murphy)
Las estructuras dinámicas son de gran utilidad para almacenar datos del mundo
real que estén en constante cambio. A diferencia de las estructuras de datos
estáticas, para las estructuras de datos dinámicas no existen limitaciones en
cuanto a asignación de memoria, ya que esta se define durante la ejecución del
programa y puede crecer o disminuir durante este proceso, están formadas por
una colección de elementos llamados nodos, que se crearán o eliminarán de
acuerdo a los requerimientos.
Antes de abordar este tipo de estructuras, debemos revisar el tema

de los “Punteros o apuntadores”, que nos serán de gran utilidad para
el estudio de estructuras dinámicas.
3.1. Apuntadores
Podríamos decir que un puntero es una variable capaz de almacenar direcciones

de memoria y mediante operadores adecuados nos permite acceder a la
información que contiene la dirección de memoria a la que «apunta» en cada
momento.
Ahora bien, no es sencillo entender el funcionamiento de los puteros y más aún

cuando tenemos que utilizarlos con operadores, pero tampoco es algo por lo
cual debamos agobiarnos, solamente debemos tener claro que existen ciertas

diferencias en su utilización, dependiendo del lenguaje de programación en el cual

vamos a trabajar.
A continuación vamos a revisar un documento que he descargado de internet y

que resume de manera muy didáctica la utilización de punteros en Java.
Revise el documento “REA_Transparencias_Tema6_punteros.pdf”

que lo puede descargar desde el EVA, preste especial atención a la
utilización de los caracteres “*” y “&” para el tratamiento de variables
de tipo puntero.
Teniendo claro el funcionamiento de los punteros, vamos a recalcar algunos

temas que considero debemos tenerlos presentes siempre, ya que de no
hacerlo se pueden presentar importantes fallas en nuestros programas que son
muy difíciles de ser detectados, por cuanto no son reportados en la etapa de
compilación.
A partir de la página 4 del REA estudiado se habla acerca de los problemas más
comunes que podemos encontrar al trabajar con punteros.
En primer lugar, usted debe considerar que todo puntero necesita ser inicializado,
pero como se muestra el documento indicado, si este proceso no se realiza de la
manera correcta, puede ocasionar que se arroje resultados incorrectos.
En segundo lugar, como puede ver en la página 5 de nuestro REA, el hacer que
un puntero declarado de un tipo específico, apunte hacia una información de otro
tipo de dato, ocasiona se arroje información que no es verdadera.
Por último, les invito a revisar el siguiente REA, el mismo que nos permitirá
establecer diferencias en el tratamiento de punteros en Java y en C++.
Revise el documento “REA_Punteros_Diferencias_Java_C++.pdf”

que lo puede descargar desde el EVA, establezca las principales
diferencias entre los lenguajes citados.

Para finalizar el presente apartado se plantea el siguiente ejercicio que permitirá

afianzar sus conocimientos, por lo que deberá realizar el respectivo análisis y
desarrollo basándose en los contenidos anteriormente tratados.

1. Complete el cuadro con lo que significa cada definición.

Suponiendo que se ha declarado una variable y se ha
almacenado en la dirección de memoria 2E600.
int a = 27;
int *P P es un puntero a un tipo de dato entero.
P = &a El valor de P es _______________________________
*P Es igual a _______________________________
*P+=2 El valor de a es _______________________________
¿Está claro qué es un puntero? y ¿cómo se representan en memoria?, les invito a

continuar el estudio de las estructuras dinámicas en el siguiente apartado.
3.2. Listas Enlazadas
Son una colección o secuencia de elementos dispuestos uno tras otro, en las que
cada elemento se conecta con el siguiente por medio de un enlace o puntero.
Para iniciar el tema, revise por favor el apartado “La clase LinkedList”
del texto básico.

De acuerdo a lo revisado, las listas enlazadas están formadas por nodos, los
cuales se irán creando o desechándose según la conveniencia de la aplicación.
Estos nodos en sí, podríamos considerarlos como un tipo de datos compuestos,
ya que como habrá podido usted apreciar en la sección antes mencionada,
la clase ListNode, está formada por dos campos: data que es en donde se
almacenará la información y next que sería el puntero de enlace hacia el siguiente
nodo.
Con fines didácticos se ha representado a un nodo con un solo

campo para la información, pero en la práctica podría ser un registro
y uno o más campos de enlace. Considere por ejemplo que la
información a guardar sean los datos de estudiantes de un curso
determinado, los clientes de una empresa, etc.
La implementación de listas enlazadas permite optimizar el uso de memoria, pero

también implica el que se deba tener cuidado con el manejo de los punteros.
Ubíquese en el capítulo “Listas enlazadas” del texto básico y revise el

apartado “Ideas básicas”. Observe la lógica que se utiliza para la
inserción y eliminación de un elemento determinado.
Cuando trabajamos con listas enlazadas debemos tener presente que debe haber
un puntero que guarde la dirección del primer elemento de la lista, ya que esta es
la puerta de entrada para localizar cualquier elemento en ella.
Los enlaces se realizan en una sola dirección, lo que quiere decir que el puntero
del nodo anterior siempre guardará la dirección del siguiente, pero no en la
dirección contraria, por lo cual el recorrido (en este caso) se realizará en una sola
dirección, “no tenemos acceso a un nodo desde su nodo sucesor”.
Como otra consideración importante, si un nodo no tiene un nodo sucesor, este

siempre deberá estar apuntando a null, como se puede observar en el nodo “d”
de la figura 17.1 del texto básico.

En el apartado que se ha solicitado revisar, preste especial atención

a las tres formas diferentes de programar la inserción de un nuevo
elemento en la lista. Es una buena forma de poner en práctica
nuestras habilidades en programación.
Como habrá podido ver, los procesos realizados mediante listas enlazadas
pueden ser mucho más óptimos que con arreglos, ya que por ejemplo si usted
realiza la inserción o eliminación de un elemento, solamente debe localizar el
lugar correspondiente y actualizar los enlaces, mas no tener que realizar ningún
otro tipo de recorridos hacia derecha o izquierda como se vio en la unidad
anterior.
Durante la programación pueden surgir algunos casos especiales que no se

apegan a la lógica utilizada para el resto de elementos, es por esto que se debe
recurrir a ciertos procedimientos que nos permitan dar solución a todos los casos
que se nos puedan presentar. Vamos a ver el más común a utilizar con listas
enlazadas.
Ubíquese en el apartado “Nodos de cabecera” del texto básico.

Observe como el autor describe la utilización de un nodo de cabecera
para dar solución a los casos especiales.
¿Cómo le ha parecido el tema hasta ahora? Si prestamos la suficiente atención,

realmente no es un tema muy difícil, ¿no le perece?
Es recomendable que usted realice la programación de lo estudiado

hasta el momento, de acuerdo a como está indicado en el texto
básico. Debe analizar cada uno de los métodos utilizados por el
autor.

Continuaremos el estudio de las listas enlazadas analizando sus variantes.
3.2.1. Clasificación de las listas enlazadas
Dependiendo de los datos a representar y la forma en la que se va a interactuar

se puede considerar uno de los cuatro tipos de categorías de listas enlazadas a
implementar. A continuación se indican gráficamente estas categorías.
Figura 9. Lista simplemente enlazada
Figura 10. Lista doblemente enlazada
Figura 11. Lista circular simplemente enlazada
Figura 12. Lista circular doblemente enlazada
Para ampliar estos conceptos, revise el apartado “Listas doblemente

enlazadas y listas circularmente enlazadas” del texto básico, preste
atención al establecimiento de enlaces de este tipo de listas.

Es recomendable que usted realice la programación de una lista

doblemente enlazada y haga la presentación de los elementos de
izquierda a derecha y viceversa.
3.2.2. Operaciones con listas enlazadas
De igual forma que cuando revisamos la temática de arreglos, al trabajar con

listas enlazadas podemos realizar las operaciones de: creación, eliminación,
lectura, inserción, actualización, entre otras.
Es oportuno ahora que revise el REA “REA_Listas Enlazadas y sus

operaciones.pdf” que lo podrá descargar desde el EVA.
Es importante que analice la lógica que se utiliza en cada una de las

operaciones descritas en este documento y de ser posible se realice
su correspondiente programación.
Es el momento adecuado para llevar el control de sus avances, para ello les invito
a desarrollar los siguientes ejercicios.

1. Proponga ejemplos de listas enlazadas que usted pueda

identificar en la vida diaria.
a. Vagones de un tren
b. ________________________________________________
c. ________________________________________________
d. ________________________________________________
e. ________________________________________________

2. Realice la declaración en Java de un nodo que almacenaría los

datos siguientes de una lista de clientes.
a. Nombre
b. Dirección
c. Edad
d. Identificación
e. Género
3. Realice la programación de una lista simple enlazada de

números enteros, ingrese 10 valores y haga un recorrido de
ella.
4. En la lista anteriormente realizada, inserte el número 100

después del primer número múltiplo de 5 que encuentre.
¿Qué le parecieron los ejercicios?, ¿sencillos verdad? Pues continuemos

revisando las estructuras dinámicas.
3.3. Implementación de pilas y colas con listas enlazadas
3.3.1. Pilas
Como se mencionó en la unidad anterior, una pila puede también ser

implementada con listas enlazadas, brindando ciertas ventajas con respecto a su
implementación mediante arreglos.
Ubíquese y revise el apartado “Implementaciones con lista enlazada”

del texto básico; ahora estudie el apartado “Pilas” del texto básico,
analice la implementación de los procedimientos Push y Pop y su
implementación en código Java.

Como usted habrá podido ver, la implementación de pilas mediante listas

enlazadas es mucho más sencilla de manejar, además que optimiza la utilización
de memoria.
Vamos ahora a revisar la siguiente estructura de esta unidad.
3.3.2. Colas
Como se lo había mencionado, las colas también pueden ser implementadas

con estructuras dinámicas como listas enlazadas, las cuales como podrá ver a
continuación, nos ofrecen una mejor funcionalidad.
Ubíquese y revise el apartado “Colas” del texto básico, note como se

describen los procesos de Push y Pop, los que se hacen de una
manera mucho más simple y no presentan problemas de espacio
para nuevos elementos.
En conclusión, aunque estos dos tipos de estructuras pueden ser implementadas

tanto con arreglos como con listas enlazadas, las estructuras dinámicas nos
permiten una forma mucho más sencilla de implementarlas y controlarlas, además
de la optimización de la memoria requerida.
¿Cómo le han parecido las estructuras dinámicas lineales? Espero no haya tenido
ningún inconveniente para su entendimiento. Y en caso de requerirlo recuerde
que siempre puede respaldarse con las indicaciones que puede solicitar al
docente tutor. Ahora vamos a finalizar este tema con unos sencillos ejercicios.


1. Realice la implementación en Java de un programa que nos

permita realizar las tareas de Push y Pop en una Pila, mediante
arreglos.
2. Realice la implementación en Java de un programa que

nos permita realizar las tareas de Push y Pop en una Cola,
mediante listas enlazadas.

Autoevaluación 3
Lea detenidamente cada una de las siguientes afirmaciones y determine si es

verdadero o falso.
1. ( ) Las estructuras dinámicas, requieren la creación de elementos

llamados nodos, los mismos que deberán crearse o eliminarse de
acuerdo a los requerimientos del programa.
2. ( ) Las variables de tipo puntero o apuntador, son una alternativa

a los índices para acceso a datos almacenados en arreglos
unidimensionales.
3. ( ) Durante la definición de los nodos que forman parte de las listas
enlazadas, debemos incluir por lo menos un campo de tipo
puntero que nos permita el acceso hacia un siguiente nodo.
4. ( ) Para utilizar listas enlazadas, se debe previamente especificar la

cantidad de elementos que la conformarán.
5. ( ) Una lista doblemente enlazada, permite el almacenamiento de

dos diferentes datos a la vez.
6. ( ) Al realizar operaciones con listas enlazadas, siempre debemos

tener presente el no perder la dirección del nodo raíz o cabeza, ya
que es nuestra puerta de entrada o inicio de la lista.
7. ( ) La implementación de pilas mediante listas enlazadas nos permite

optimizar el uso de la memoria, ya que no se cuenta con espacios
no ocupados y puede crecer según sean los requerimientos.

8. ( ) En la implementación del TAD Cola mediante listas enlazadas

y de acuerdo a la programación, puede permitirse el ingreso de
nuevos datos al inicio de la cola.
9. ( ) Si durante la ejecución de un programa con listas enlazadas,

perdemos la dirección de un siguiente nodo, será imposible su
redireccionamiento y recuperar la continuidad del programa.
10. ( ) Al trabajar con listas enlazadas no circulares, el campo next del

nodo cola o último, siempre deberá estar apuntando hacia NULL.

Guía didáctica: Estructura de Datos SEGUNDO BIMESTRE
SEGUNDO BIMESTRE
UNIDAD 4. ESTRUCTURAS JERÁRQUICAS
“Somos lo que hacemos de forma repetida. La

excelencia, entonces, no es un acto, sino un
hábito”
Aristóteles
En la unidad anterior estudiamos las estructuras dinámicas lineales conocidas

como listas enlazadas; tal como nos pudimos dar cuenta tienen algunas
ventajas frente a las estructuras estáticas, como de que por medio de punteros
se pueden crear nodos en tiempo de ejecución, de acuerdo a la necesidad de
almacenamiento de información; por otra parte esta es una estructura lineal,
puesto que existe un solo camino para recorrer sus elementos desde el primer
hasta el último elemento.
En la presente unidad, el tema central de estudio son las estructuras jerárquicas,

las cuales nos brindan una mejor forma de realizar el almacenamiento de
información, están organizadas en niveles y como veremos más adelante existen
varios caminos para recorrer la estructura desde el primer elemento o raíz, hasta
los elementos de los niveles más avanzados.
Estas estructuras también conocidas como árboles (por sus ramificaciones) están
formadas por nodos al igual que las listas enlazadas, pero cada nodo debe contar
con dos o más campos que puedan apuntar hacia otros nodos.
4.1. Árboles
En términos computacionales, un árbol es un tipo abstracto de datos (TAD) que

imita la estructura jerárquica de un árbol, con un valor en la raíz y sub árboles con

un nodo padre, representado como un conjunto de nodos enlazados. Puede ser

definido de forma recursiva como una colección de nodos, donde cada uno de
ellos es una estructura de datos con un valor, junto con una lista de referencias
a otros nodos hijos, con la condición de que ninguna referencia esté duplicada ni
que ningún nodo apunte a la raíz.
El número de ramas asociadas con un nodo es el grado del nodo. Si un árbol no

está vacío, entonces el primer nodo se llama raíz.
Vamos a ampliar los conceptos de esta estructura.
Ubíquese en el capítulo “Árboles” del texto básico. Revise las

definiciones dadas en el apartado “Árboles generales” y todos sus
sub ítems. Centrémonos en la definición, dejando por el momento el
código para después.
4.1.1. Características y propiedades
Entre las características y propiedades más importantes de los árboles en general

tenemos: (Gonzalez, 2012)
a. Todo árbol que no es vacío, tiene un único nodo raíz.

b. Un nodo X es descendiente directo de un nodo Y, si el nodo X es
apuntado por el nodo Y. En este caso es común utilizar la expresión X
es hijo de Y.
c. Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al
nodo Y. En este caso es común utilizar la expresión X es padre de Y.
d. Se dice que todos los nodos que son descendientes directos (hijos) de
un mismo nodo (padre), son hermanos.
e. Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre
de nodo terminal u hoja.
f. Todo nodo que no es raíz, ni terminal u hoja es conocido como nodo
interior.

g. Grado es el número de descendientes directos de un determinado

nodo.
h. Grado del árbol es el máximo grado de todos los nodos del árbol, es
decir, el grado más alto entre todos los nodos.
i. Nivel es el número de arcos que deben ser recorridos para llegar a un
determinado nodo. Por definición la raíz tiene nivel 0.
j. Altura del árbol es el máximo número de niveles de todos los nodos del
árbol.
Como se podrá dar cuenta, el estudio de los árboles es muy simple puesto que
esta estructura está muy relacionada con objetos de nuestro entorno físico.
Los árboles pueden representarse de varias maneras, aunque la forma más

común es mediante grafos, su representación básica requiere que se utilice la
terminología apropiada, por lo que vamos a revisar lo descrito en la figura 13.
Figura 13. Terminología de un árbol
Con base a la figura 13, en la siguiente tabla 1 se determina que los componentes
de un árbol pueden tomar algunas denominaciones, así:
Tabla 1. Nomenclatura de componentes de un árbol.

Nomenclatura de componentes de un árbol
Nodos Padres A, B, F
Nodos hijos B, E, F, C, D, G, H, I.
Descendientes de A B, C, D, E, F, G, H, I.
Ascendientes de C B, A.

Nomenclatura de componentes de un árbol

Nodos Hermanos {B, E, F}; {C, D}; {G, H, I}
Nodos hojas C, D, E, G, H, I.
Profundidad 0 A
Profundidad 1 B, E, F.
Profundidad 2 C, D, G, H, I.
4.1.2. Aplicaciones
Pensemos que las Estructuras de Datos existen para solucionar problemas

de nuestro entorno, caso contrario no tendría razón su estudio y aplicación en
nuestros programas; así, entre las diferentes aplicaciones en las que este tipo de
estructuras se pueden utilizar tenemos:
• Representación de fórmulas matemáticas.

• Organización adecuada de la información.
• Registrar la historia de un campeonato deportivo.
• Construir un árbol genealógico.
• Análisis de circuitos eléctricos.
• Numeración de los capítulos de un libro.

1. Describa la definición de los conceptos que se indican a

continuación:
a. Nodo raíz: _______________________________________

b. Nodo interno: _____________________________________
c. Nodo no terminal: __________________________________
d. Nivel: ___________________________________________
e. Ramas: __________________________________________

f. Camino: _________________________________________
g. Altura: ___________________________________________
h. Sub árbol: ________________________________________
i. Árbol equilibrado: __________________________________
2. Investigue cinco aplicaciones fuera de las citadas previamente

que podrían ser implementadas con árboles.
4.2. Árboles Binarios
Este tipo de árbol tiene la particularidad de que ningún nodo puede tener más
de dos sub árboles, es decir cada nodo puede tener cero, uno o dos hijos (sub
árboles), los cuales serán conocidos como hijo izquierdo e hijo derecho, como se
puede apreciar en la figura14.
Figura 14. Árbol binario
Un árbol binario es una estructura recursiva, donde cada nodo es la raíz de su

propio sub árbol y tiene hijos, que son raíces de otros árboles llamados sub
árboles derecho e izquierdo del nodo, respectivamente.
Es momento de revisar el apartado “Árboles binarios” del texto

básico. Enfóquese en la información proporcionada al inicio de este
apartado.

Como puede ver, un árbol binario tiene ciertas restricciones (máximo dos sub
árboles), lo cual lo hace más práctico a la hora de programar esta estructura.
Una de las tareas principales cuando desarrollamos aplicaciones con árboles

binarios es el recorrido, el mismo que lo estudiaremos a continuación.
4.3. Recorridos en Árboles Binarios
Una de las tareas básicas que se realiza en un árbol binario es la de recorrido,

lo cual significa visitar los nodos del árbol en forma sistemática. Un recorrido
requiere que cada nodo sea procesado una sola vez, en una secuencia
determinada.
Existen tres formas de efectuar el recorrido y todas ellas de naturaleza recursiva.
Revise en el apartado “Recorrido del árbol” del texto básico, desde el

apartado “Recorrido en postorden” hasta el apartado “Recorrido en
preorden”, se explican los tres tipos de recorridos de un árbol.
Como habrá podido ver, estos recorridos difieren entre sí por el orden en el cual
se procesan los datos, los cuales resumimos a continuación en la tabla 2:
Tabla 2. Recorridos de árboles binarios

Recorridos de nodos de un árbol binario
Preorden (NID) En orden (IND) Postorden (IDN)
a. Visitar la raíz (N). a. Recorrer el sub árbol a. Recorrer el sub árbol
b. Recorrer el sub árbol izquierdo (I). izquierdo (I).
izquierdo (I). b. Visitar la raíz (N). b. Recorrer el sub árbol
c. Recorrer el sub árbol c. Recorrer el sub árbol derecho (D).
derecho (D). derecho (D). c. Visitar la raíz (N).

Así, cada uno de estos recorridos nos permite un orden diferente de

procesamiento de la información. A continuación y utilizando de ejemplo la figura
11 previamente expuesta, observaremos el resultado de la aplicación de cada uno
de estos recorridos sobre ella.
1. Preorden : L, D, B, H, G, J, Q, X, T, S, W, Y
2. En orden : B, D, G, H, J, L, Q, S, T, W, X, Y
3. Postorden : B, G, J, H, D, S, W, T, Y, X, Q, L

1. Realice la codificación en Java de estos tres tipos de recorridos

para sus programas:
2. Indique un posible caso en donde se utilizaría cada uno de
estos recorridos.
4.4. Árboles de Búsqueda Binaria
Este tipo especial de estructura, tiene la particularidad de permitir una realización

eficiente de las operaciones de búsqueda, inserción y eliminación.
Formalmente se define un árbol binario de búsqueda de la siguiente manera:
Sea A un árbol binario de raíz R e hijos izquierdo y derecho

(posiblemente nulos) HI y HD, respectivamente.
Decimos que A es un árbol binario de búsqueda (ABB) si y solo si

se satisfacen las dos condiciones al mismo tiempo:
▪▪ “HI es vacío” Ѵ (“R es mayor que todo elemento de HI” Ʌ “HI

es un ABB”).

▪▪ “HD es vacío” Ѵ (“R es menor que todo elemento de HD” Ʌ

“HD es un ABB”).
Donde “ Ʌ “ es la conjunción lógica “y”, y “ Ѵ “ es la disyunción

lógica “o”.
Así, un árbol binario de búsqueda se construye con base en una lista de números
dados (claves), en el cual el primer número de dicha lista será la raíz del árbol, y
los siguientes valores se ubicarán de acuerdo al criterio antes indicado.
Revise en el capítulo “Árboles de búsqueda binaria” del texto básico,

y su apartado “Ideas básicas”. Nos permitirá ampliar los conceptos
mencionados con respecto a este tema.
Las principales operaciones que se realizan con este tipo de estructura son las de
inserción y eliminación de elementos.
Revise en el apartado “Las operaciones” del texto básico, preste

especial atención a la explicación mediante las figuras que se hace
de cada uno de los casos de estas operaciones.
Como se menciona en el texto básico, no siempre vamos a obtener el mismo

árbol de un grupo de elementos que se ingresen. Esto depende del orden en el
cual ingresemos o extraigamos los elementos en el árbol.
Los ABB son la base para nuevas estructuras como los Árboles
binarios equilibrados (AVL), su principal característica es la facilidad
en cuanto a los algoritmos para trabajar con la información.


1. Elabore gráficos de árboles de búsqueda binaria, con cada

uno de los grupos de datos mostrados a continuación. Preste
atención a las figuras resultantes.
a. 65, 75, 30, 4, 41, 85.

b. 65, 85, 41, 75, 30, 4.
c. 4, 30, 41, 65, 75, 85.
2. Elabore un programa que permita realizar el almacenamiento

de elementos en un árbol de búsqueda binaria.
4.5. Árboles AVL
De los ejercicios realizados con árboles de búsqueda binaria nos pudimos dar
cuenta, que de acuerdo al orden de ingreso de los elementos, dependerá el
incremento o no de cualquiera de las ramas del árbol, ver figura 15.
Figura 15. Árbol binario de búsqueda desbalanceado

Aunque las operaciones de búsqueda e inserción de elementos se realizan de una

manera eficiente en los árboles de búsqueda binaria, estos resultan ineficientes
cuando el árbol crece o decrece descontroladamente, aún más cuando los
elementos que ingresamos en el árbol están ordenados como se muestra en la
figura 15, lo que causa un aumento considerable en el número de comparaciones
que se deben realizar cuando se desea ubicar un determinado elemento.
Para evitar este problema es necesario la utilización de árboles balanceados,

los cuales tienen como objetivo mantener al árbol lo más equilibrado posible,
recurriendo a métodos de ordenamiento de sus nodos, ubicándolos de forma que
no afecte el balanceo del árbol. El objetivo del balanceo de árboles es minimizar
el número de comparaciones para lograr un mejor tiempo de acceso a sus datos.
Revise los conceptos expuestos en los puntos “Árboles AVL” y

“Propiedades” del texto básico. No se detenga a analizar las fórmulas
utilizadas, sino enfóquese en la descripción de los casos de
alteración de equilibrio.
Como pudo observar en la descripción de las propiedades de estos árboles, se

detecta un desequilibrio en un árbol cuando la diferencia de altura entre un sub
árbol izquierdo y un sub árbol derecho difieren en más de una unidad.
Para controlar esta diferencia en altura, se debe agregar un campo de tipo

entero a la estructura de los nodos, en algunos textos se lo denomina “factor de
equilibrio”, y debe mantenerse con valores entre -1 y 1, caso contrario indicaría
que se está cometiendo uno de los cuatro casos de desequilibrios a resolver;
estos casos como lo podrá usted observar en la sección “Árboles AVL” del texto
básico, se dan cuando al insertar un nuevo elemento el factor de equilibrio cambia
a 2 o a -2.
Es tiempo de revisar los procedimientos descritos en los ítems

“Rotación simple”, al “Resumen de la inserción AVL” del texto básico.
Estudie las imágenes de los ejemplos según la descripción de los
movimientos descritos.

Estos casos de desequilibrio y según el caso pueden ser resueltos por uno de los
procedimientos de rotación llamados: rotación simple a la izquierda o a la derecha
y rotación doble izquierda – derecha y rotación doble derecha – izquierda. Estas
rotaciones podríamos representarlas como se muestra en la figura 16.
Figura 16. Rotaciones en árbol AVL
Algo muy importante a tener en cuenta es que al realizar cualquier tipo de rotación
para corregir un desequilibrio en un sub árbol, se podría causar otro desequilibrio
al actualizar valores del factor de equilibrio en un nodo superior, por lo cual estos
procedimientos deben ser recursivos y se ejecutarían desde los sub árboles de
mayor altura hasta llegar al nodo raíz, verificando este factor en cada uno a su
paso.
La programación del método de rotación simple a la derecha es simétrica al de

rotación simple a la izquierda, de igual manera que la de rotación doble derecha-
izquierda lo es con la de la derecha, como lo verá a continuación.
Para facilitar su entendimiento, analice las siguientes imágenes que

muestran los pseudocódigos de los métodos para la realización de
las diferentes rotaciones (Titiosky, 2008).

Figura 17. Método de rotación simple AVL
Figura 18. Método de rotación doble AVL

1. En su libreta de anotaciones grafique ejemplos de árboles

desbalanceados y aplique los métodos descritos para
solucionar el problema.

4.6. Tablas Hash
Esta estructura de datos asocia llaves o claves con valores, soporta de manera
eficiente la operación de búsqueda, permitiendo el acceso a datos almacenados
a partir de una clave generada. Transforma la clave con una función hash, a un
número que identifica la posición donde la tabla hash localiza el valor deseado.
Suelen implementarse sobre vectores unidimensionales, aunque se pueden

hacer implementaciones multi-dimensionales basadas en varias claves. Como
en el caso de los arrays, proveen tiempo constante de búsqueda promedio
O(1), 1 sin importar el número de elementos en la tabla. Sin embargo, en casos
particularmente malos el tiempo de búsqueda puede llegar a O(n), es decir,
en función del número de elementos. Comparada con otras estructuras de
arrays asociadas, las tablas hash son más útiles cuando se almacenan grandes
cantidades de información.
Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así

que el acceso ordenado a su contenido es bastante lento, a diferenica de otras
estructuras como árboles binarios auto-balanceables los que tienen un tiempo
promedio de búsqueda mayor (tiempo de búsqueda O (log n)), pero la información
está ordenada en todo momento.
Ubíquese en el apartado “Función hash” del texto básico, lea los

conceptos relacionados con este tipo de estructura.
4.6.1. Resolución de colisiones
Cuando la función hash genera una misma dirección para dos diferentes claves
enfrenta una colisión. La correcta resolución de estas colisiones implica la
elección de un método adecuado, lo cual es tan importante como la elección
de una buena función hash. Entre los métodos más utilizados tenemos los de
reasignación, arreglos anidados y métodos mediante áreas de desborde.

Revise el vídeo sobre Tablas Hash publicado en el EVA, le ayudará a

entender de mejor manera estos conceptos.
Vamos a revisar los más conocidos para la resolución de colisiones:
Sondeo lineal
Ubíquese en el apartado “Sondeo lineal” de nuestro texto básico,

observe la forma de utilización de este método.
Durante la búsqueda de un elemento con este sistema, una vez detectada la

colisión se debe de recorrer el arreglo secuencialmente a partir del punto de
colisión. El proceso de búsqueda concluye cuando el elemento es hallado,
o cuando se encuentra una posición vacía. El arreglo es tratado como a una
estructura circular, regresando al primer elemento una vez que se ha llegado al
último.
La principal desventaja de este método es que puede haber un fuerte

agrupamiento alrededor de ciertas claves, mientras que otras zonas del arreglo
permanecerían vacías. Si las concentraciones de claves son muy frecuentes, la
búsqueda será principalmente secuencial perdiéndose así las ventajas del método
hash.
Sondeo cuadrático
Realice una revisión completa del apartado “Sondeo cuadrático” del

texto básico. Establezca las diferencias encontradas con el sondeo
lineal.
Este método es algo similar al sondeo lineal. La diferencia consiste en que en el

cuadrático las direcciones alternativas se generan como D+1, D+4, D+9,..., D+i²
en lugar de D+1, D+2,...,D+i. Esta variación permite una mejor distribución de las
claves colisionadas.

La principal desventaja de este método es que pueden quedar casillas del arreglo
sin visitar.
Encadenamiento separado
Revise el apartado “Hash con encadenamiento separado” del texto

básico.
Como usted ha podido ver y como se ilustra en la figura 19, este sistema consiste
en que cada elemento del arreglo tenga un apuntador a una lista ligada, la cual
se irá generando e irá almacenando los valores colisionados a medida que sean
requeridos por la aplicación.
Le recomiendo observe la figura 19 y vaya insertando cada elemento en el lugar

correspondiente, con el fin de ver el funcionamiento del algoritmo.
Figura 19. Manejo de colisiones por encadenamiento separado.
Hemos concluido la presente unidad, espero no haya tenido ningún

inconveniente con su estudio, recuerde que tiene varias opciones
para contactarse con el docente en caso de alguna duda.
Ahora bien, revise su evolución en el estudio de las estructuras jerárquicas. Lo
invito a desarrollar la siguiente autoevaluación.

Autoevaluación 4
Lea detenidamente cada una de las siguientes preguntas planteadas y determine

cuál de las afirmaciones es correcta.
1. En términos computacionales, un árbol:
a. Puede tener varios nodos raíz, siempre y cuando no exista un nodo hijo
común.
b. Podrá generar tantos nodos raíz como sean necesarios en la
aplicación.
c. Debe tener un solo nodo raíz, del cual se desprenderán todos los sub
árboles.
2. Aquellos nodos que no tienen descendientes son conocidos como:
a. Nodo raíz.
b. Nodo hermano.
c. Nodo hoja.
3. Conocemos como “grado del árbol” a:
a. El máximo grado de todos los nodos del árbol.

b. El máximo número de niveles encontrado en el árbol
c. La sumatoria de todos los grados de los nodos del árbol.
4. Se conoce como nivel de un nodo a:
a. El número de arcos que deben ser recorridos para llegar a él.

b. El número de nodos hermanos que un nodo pueda tener.
c. El número de nodos por los cuales hay que pasar para llegar a él.

5. La altura del árbol es:
a. El máximo número de niveles de todos los nodos del árbol.

b. Igual al promedio de las diferentes alturas de sus sub árboles.
c. El máximo número de nodos hijos que un nodo pueda tener.
6. Entre los recorridos de los árboles binarios, tenemos:
a. Anchura y profundidad
b. Preorden y posorden,
c. Ascendente y descendente.
7. El recorrido que sigue el orden de visita “izquierda, derecha, raíz”, es

conocido con el nombre:
a. Anchura,
b. profundidad o
c. posorden.
8. Un árbol de búsqueda binaria:
a. Puede permitir a un nodo tener más de dos hijos solo si se constituyen

como nodos terminales u hojas.
b. No permite a ningún nodo tener más de dos hijos o sub árboles.
c. Es aquel que solamente guarda información como “unos” o “ceros”.
9. La estructura final de un árbol de búsqueda binaria:
a. Cambia de acuerdo al orden de inserción de elementos,

b. Siempre será igual, sin importar el orden de inserción de elementos.
c. Siempre mantendrá la misma imagen sin importar el ingreso de
elementos.

10. La estructura final de un árbol AVL:
a. Cambia de acuerdo al orden de inserción de elementos,

b. Adaptan su forma de acuerdo al orden de inserción de elementos.
c. Siempre será igual, sin importar el orden de inserción de elementos.

UNIDAD 5. GRAFOS
“Si piensas que puedes, tú puedes, y si piensas

que no puedes, tienes razón”
Mary Kay Ash
En el área de la informática, existen conceptos que definidos mediante

herramientas o estructuras de datos, permiten modelar implícitamente conceptos
computacionales, como relaciones entre objetos que mantienen relaciones
arbitrarias entre sí, es decir, no están sujetos a relaciones de tipo jerárquico, un
caso particular de esto son los grafos.
Pensemos que cuando queremos movilizarnos de una ciudad a otra en nuestro

vehículo o en líneas preestablecidas de metro o tren, normalmente empezamos
trazando la mejor ruta a seguir, definimos algunos puntos o ciudades por
las cuales pasaremos; por otra parte pensemos también en las compañías
aéreas internacionales, normalmente hacen sus itinerarios de vuelo teniendo
en cuenta algunas ciudades en las cuales se hará escala; desde el punto de
vista informático el camino que estamos trazando es un grafo, y tal como lo
hemos visto tiene una gran cantidad de aplicaciones en áreas como: geografía,
ingenierías, en el campo industrial, sistemas de información geográfica, en las
compañías de distribución de productos, etc.
Consecuentemente en el contexto informático, esta estructura tiene un amplio

rango de aplicaciones, así por ejemplo en el modelado de cambio de estados de
un sistema, etc. A continuación propongo el siguiente ejercicio que tiene relación
con los grafos y sus aplicaciones.

Como estrategia de aprendizaje, a continuación le propongo la realización de los

siguientes ejercicios.
1. Describa ejemplos en los cuales se pueda utilizar los grafos

como estructuras de datos.
a. ________________________________________________
b. ________________________________________________
c. ________________________________________________
d. ________________________________________________
5.1. Conceptos y definiciones
Ubíquese en el texto básico y revise el apartado “Definiciones” del

capítulo “Grafos y Rutas”. Una vez revisado refuerce lo aprendido
con la siguiente explicación.
Un grafo en el ámbito de las ciencias de la computación es un tipo abstracto de

datos (TAD), que consiste en un conjunto de nodos (también llamados vértices)
y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El
concepto de grafo TAD desciende directamente del concepto matemático de
grafo.
Formalmente, un grafo se define como G = (V, E), siendo V un conjunto cuyos

elementos son los vértices del grafo y, E un conjunto cuyos elementos son las
aristas, las cuales son pares (ordenados si el grafo es dirigido) de elementos en V.
Adicionalmente a los componentes existen otros términos más específicos, es

decir en algunos casos son conceptos que se aplican a determinados grafos
dependiendo de su naturaleza, contenido y tipo de información que proporcionan.
Así, entre las principales definiciones básicas relacionadas a grafos tenemos:

Grafo no dirigido: Gráficamente este tipo de grafo no contiene un direccionamiento

específico o no tiene flechas; de manera formal podríamos decir que el arco que
une los dos nodos se puede representar de dos formas (n1, n2) o (n2, n1), ver
figura 20.a.
Grafo dirigido. contiene un direccionamiento o flechas que indican la relación

existente entre sus nodos; como puede ver en la figura 20.b la relación de los
arcos (D, E) no puede ser representada de la forma (E, D).
• Grafo valorado. Aquel en el cual sus arcos tienen un peso o valor.

• Grado de entrada. Es el número de ejes (arcos) que inciden sobre el
nodo.
• Grado de salida. Es el número de arcos que salen del nodo.
• Camino: Es la secuencia de arcos y vértices necesarios para alcanzar
un nodo de destino.
• Longitud de un camino: Es la cantidad de nodos incluidos en un
camino, incluyendo el primero y el último nodo.
• Orden de un grafo: es el número de nodos (vértices) del grafo.
• Grafo conexo: es un grafo no dirigido tal que para cualquier par de
nodos existe al menos un camino que los une.
• Grafo fuertemente conexo: es un grafo dirigido tal que para cualquier
par de nodos existe un camino que los une.
• Punto de articulación: es un nodo que si desaparece provoca que se
cree un grafo no conexo.
Figura 20. a. Grafo no dirigido. b. Grafo dirigido

La mejor manera de entender los conceptos de un grafo es aplicarlos en un

modelo especifico, para lo cual sírvase desarrollar el siguiente ejercicio.

1. Elabore un grafo y obtenga los valores correspondientes a los

conceptos antes mencionados.
Una vez que hemos estudiado la parte relacionada con los conceptos, veamos
cómo se almacena la información de esta estructura; veremos que se usan
estructuras de datos ya conocidas como: arreglos y listas enlazadas.
5.2. Representación
La estructura Grafo debe ser representada utilizando estructuras propias de

los lenguajes de programación, con base en esto veremos que existen algunas
formas de representar esta estructura, mismas que presentan ciertas ventajas e
inconvenientes respecto a las demás.
En el capítulo “Grafos y rutas” del texto básico, remítase al apartado

“Representación”, revise las diferentes formas de representación de
grafos, podrá obtener una introducción a lo que veremos a
continuación.
Un grafo es un par compuesto por dos conjuntos: un conjunto de nodos y un

conjunto de relaciones entre los nodos. La representación tendrá que ser capaz
de guardar esta información en memoria.

5.2.1. Matriz de adyacencia
La forma más fácil de guardar la información de los nodos es mediante la

utilización de un vector que indexe los nodos, de manera que los arcos entre
los nodos se pueden ver como relaciones entre los índices. Esta relación entre
índices se puede guardar en una matriz, que llamaremos de adyacencia.
Esta representación implica tener que reservar al menos el orden de n2 espacios

de memoria para la información de los arcos, y las operaciones relacionadas con
el grafo implicarán habitualmente, recorrer toda la matriz, con lo que el orden de
las operaciones será en general, cuadrático, aunque tengamos un número de
relaciones entre los nodos mucho menor que n2.
Mediante esta representación es muy fácil determinar, a partir de dos nodos, si

están o no relacionados, sólo hay que acceder al elemento adecuado de la matriz
y comprobar el valor que guarda.
Como ejemplo veremos la figura 21 y cómo sería representada mediante este

método:
Figura 21. Representación mediante Matriz de adyacencia.
5.2.2. Listas de adyacencia
En las listas de adyacencia se intenta evitar justamente el reservar espacio para

aquellos arcos que no contienen ningún tipo de información. El sustituto obvio a
los vectores con espacios vacíos, son las listas.

Las listas de adyacencia guardan por cada nodo, además de la información propia
del nodo, una lista dinámica con los nodos a los que se puede acceder desde él,
ver figura 22. La información de los nodos se puede guardar en un vector, al igual
que antes, o en otra lista dinámica.
Figura 22. Lista de adyacencia.
En general se está guardando menor cantidad de elementos, solo se reservará

memoria para aquellos arcos que efectivamente existan, pero como contrapartida
estamos guardando más espacio para cada uno de los arcos (estamos añadiendo
el índice destino del arco y el puntero al siguiente elemento de la lista de arcos).
Las tareas relacionadas con el recorrido del grafo supondrán solamente trabajar
con los vértices existentes en el grafo, que pueden ser mucho menor que n2. Pero
comprobar las relaciones entre nodos no es tan directo como lo era en la matriz,
sino que supone recorrer la lista de elementos adyacentes perteneciente al nodo
analizado.
5.2.3. Matrices dispersas
Para evitar uno de los problemas existentes en las listas de adyacencia, que
es la dificultad de obtener las relaciones inversas, podemos utilizar las matrices
dispersas, que contienen tanta información como las matrices de adyacencia,
pero, en principio, no ocupan tanta memoria como estas, ya que al igual que en
las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el
grafo.

Entre los diferentes formatos de almacenamiento para matrices dispersas

podemos citar por ejemplo el “Comprimido por filas”, que como puede observar
en la figura 23, almacena solamente los datos que son de relevancia de las
relaciones del grafo.
Figura 23. Almacenamiento de matrices dispersas, método de compresión por

filas.
Para el almacenamiento del ejemplo planteado anteriormente, se utilizan tres

arreglos, los cuales almacenarán la siguiente información.
Arreglo V. Almacena los valores numéricos de la relación, ordenados por filas.
Arreglo J. Se almacenarán los índices correspondientes de columnas.
Arreglo I. Punteros a inicios de fila, en este caso I[k] indicará en qué posición del
arreglo empieza la fila k.
Es necesario se agregue un elemento más que indicará en donde termina el

arreglo.
5.3. Recorridos de grafos
Recorrer un grafo supone intentar alcanzar todos los nodos que estén
relacionados con uno dado que tomaremos como nodo de salida.
Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura,

y el recorrido en profundidad.

5.3.1. Recorrido en anchura o BFS (Breadth First Search)
El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado por

niveles, es decir, primero los que están a una distancia de un arco del nodo de
salida, después los que están a dos arcos de distancia, y así sucesivamente hasta
alcanzar todos los nodos a los que se pudiese llegar desde el nodo de salida.
Naturalmente, necesitamos seguir la pista de los vecinos de un nodo y tenemos
que garantizar que ningún nodo se procesa más de una vez. Esto se hace usando
una cola para mantener los nodos que estén esperando para ser procesados y
usando un campo ESTADO que nos diga el estado actual de los nodos.
La diferencia a la hora de implementar el algoritmo general para cada una de

las implementaciones de la estructura de datos grafo, residirá en la manera de
averiguar los diferentes nodos adyacentes a uno dado. En el caso de las matrices
de adyacencia se tendrán que comprobar si los enlaces entre los nodos existen
en la matriz. En los casos de las listas de adyacencia y de las matrices dispersas
sólo habrá que recorrer las listas de enlaces que parten del nodo en cuestión para
averiguar qué nodos son adyacentes al estudiado.
A continuación podemos revisar en la figura 24, la implementación en

Java del algoritmo de Recorrido en Anchura, para lo cual el autor del
programa, realiza la creación de una clase “Grafos” la cual es
llamada desde un programa principal.

Figura 24. Recorrido en Anchura de un grafo.
5.3.2. Recorrido en profundidad O DFS (Depth First Search)
A diferencia del algoritmo anterior, el recorrido en profundidad trata de buscar los

caminos que parten desde el nodo de salida hasta que ya no sea posible avanzar
más. Su funcionamiento consiste en ir expandiendo todos y cada uno de los
nodos que va localizando, de forma recurrente, en un camino concreto. Cuando
ya no puede avanzar más sobre el camino elegido, se vuelve atrás (Backtracking)
en busca de caminos alternativos, de modo que repite el mismo proceso con cada
uno de los hermanos del nodo ya procesado.

A continuación podemos revisar en la figura 25, la implementación en

Java del algoritmo de Recorrido en Profundidad.
Figura 25. Recorrido en profundidad de un grafo.
Para poder ver el funcionamiento de estos algoritmos, debemos crear un

programa principal como el que podrá ver en la figura 26.
Es recomendable que realice la codificación de los programas

presentados. Para obtener una mayor información de ellos, así como
de los diferentes comentarios adjuntados por el autor, debe dirigirse
al enlace proporcionado en la siguiente cita bibliográfica. (@
JuanSet19, 2013)

Figura 26. Programa principal para la ejecución de recorridos en grafos.
Muy bien estimados estudiantes, hemos llegado a la finalización del estudio de la

asignatura en este segundo bimestre y por ende del presente ciclo, esperamos
que los conocimientos adquiridos sean los básicos y necesarios para iniciar en
el desarrollo de aplicaciones que tengan eficiencia y eficacia, es por ello que le
invitamos a desarrollar la última autoevaluación esperando que todo le vaya de lo
mejor. Adelante y éxitos!

Autoevaluación 5
Lea detenidamente cada una de las siguientes afirmaciones y determine si es

verdadero o falso.
1. ( ) En el ámbito computacional, un grafo está compuesto por un

conjunto de nodos y arcos relacionados entre sí.
2. ( ) Formalmente, un grafo se define como G = (n, c), siendo n un

nodo dado del grafo y, c los caminos asociados al nodo.
3. ( ) Los grafos dirigidos, gráficamente son representados con aristas

carentes de una dirección específica.
4. ( ) Se conoce al grado de entrada como al número de arcos que

inciden sobre un nodo.
5. ( ) Se conoce como orden del grafo, a la secuencia de arcos y

vértices necesarios para alcanzar un nodo destino.
6. ( ) Las matrices de adyacencia, requieren la utilización de n2

espacios de memoria para la información de los grafos.
7. ( ) La implementación de listas de adyacencia, al igual que con las

matrices de adyacencia, pueden requerir que haya una utilización
innecesaria de memoria para el almacenamiento de información.
8. ( ) Los recorridos en listas de adyacencia trabajan solamente sobre

los vértices existentes en el grafo.

9. ( ) Las matrices dispersas, pueden contener tanta información como

las matrices de adyacencia pero no ocupan tanta memoria como
ellas.
10. ( ) Las matrices dispersas se apoyan en arreglos alternativos para

poder representar solamente los enlaces existentes en el grafo.

Guía didáctica: Estructura de Datos SOLUCIONARIO
7. Solucionario
Primer bimestre
Autoevaluación 1
Número Respuesta Retroalimentación
correcta
1 c La característica principal de los tipos de datos estáticos,
es que el usuario previamente define su tamaño y este no
podrá ser cambiado en la ejecución del programa.
2 c Los tipos de datos String, me sirven para manipular
cadenas de texto, y entre ese tipo de manipulación está la
de extracción de partes de esa cadena.
3 c Homogeneidad es un sinónimo de igualdad, por lo cual
todos sus elementos deben ser del mismo tipo.
4 c Aunque con fines didácticos se utilicen datos de tipo entero
en los ejemplos para el estudio, los datos a almacenarse
pueden ser registros que brinden información más
completa.
5 c Entre las formas de ingreso de datos a un arreglo están:
durante la definición, por medio del teclado, desde una
fuente externa, etc.
6 b Aunque existen muchas operaciones que se pueden
aplicar sobre arreglos, las principales son: lectura,
modificación, búsqueda, ordenación y eliminación.
7 c Un requerimiento de este tipo de búsqueda es que sus
datos estén previamente ordenados; la ordenación
también puede darse alfabéticamente.
8 b Para declarar un arreglo, los corchetes deben ir ya sea en
el tipo de datos o en el nombre del arreglo, previamente al
signo “=”.
9 a En todos los lenguajes de programación se utiliza la
nomenclatura en ese orden: filas y columnas.

Autoevaluación 1
correcta
10 a La expresión <nombre del arreglo>.lenght permite conocer
el número de elementos de un arreglo.

Autoevaluación 2
correcta
1 V Un TAD tiene un conjunto de valores y operaciones.
Cumple con los principios de abstracción, ocultación de la
información.
2 F La Pila es una estructura LIFO “Last In First Out”.
3 V Se conoce con el nombre de Push a la operación de
inserción de elementos, tanto en pilas como en colas.
4 F Los procesos de inserción y extracción de elementos de
pilas y colas son de forma ordenada.
5 V Se conoce con el nombre de Pop a la operación de
extracción de elementos, tanto en pilas como en colas;
en este caso es correcto ya que en las colas se extrae
siempre el primer objeto que ha ingresado.
6 V Las Colas son estructuras FIFO “First In First Out”.
7 V El concepto se apega a la definición de “conjunto”.
8 F Esa es la definición de Intersección de conjuntos.
9 F Esa es la definición de Diferencia simétrica
10 V Es imprescindible la utilización de un nuevo parámetro que
permita obtener un nuevo criterio de evaluación.

Autoevaluación 3
correcta
1 V Las estructuras dinámicas por su naturaleza requieren que
sus elementos sean creados o eliminados de acuerdo a sus
necesidades.
2 F Este tipo de variables son utilizadas para estructuras dinámicas.
3 V Las variables de tipo puntero son imprescindibles en la
estructura de los nodos, ya que permiten referir al siguiente
elemento.
4 F Las listas enlazadas son estructuras dinámicas por cuanto no
es necesario especificar previamente su tamaño.
5 F Lo doblemente enlazada se refiere a que posee dos variables
de tipo puntero para direccionar hacia otros nodos.
6 V El nodo raíz o cabeza es la única forma de poder llegar hacia
cualquiera de los nodos.
7 V Las listas enlazadas no cuentan con elementos que no posean
información.
8 F Si cambiamos el orden de entrada de elementos a la ya
establecida en los TAD cola, ya se pierde el concepto y
simplemente no sería una cola.
9 V La pérdida de la dirección de un nodo significa que no hay
forma de acceso a él.
10 V Las variables de tipo puntero siempre deben apuntar hacia
algún lugar, en el caso último nodo al no existir más datos debe
ser apuntado hacia null.

Segundo bimestre
Autoevaluación 4
correcta
1 c El concepto de árbol está basado en un único nodo raíz.
2 c Es el nombre proporcionado en la nomenclatura de elementos
de los árboles.
3 a Es el máximo número de descendientes directos que puede
tener un nodo.
4 b La raíz siempre tiene nivel 0. Sus hijos nivel 1 y así
sucesivamente.
5 a Es el nivel del nodo hoja más alejado de la raíz.
6 b Los tres tipos de recorridos son: preorden, inorden y postorden.
7 c Esa es su definición.
8 b La definición de “Binario” quiere decir que tiene dos variables
de enlace.
9 a Esta puede tender a desequilibrase de acuerdo al orden de
ingreso de elementos.
10 b Los árboles AVL adaptan su forma para mantener el equilibrio
de sus ramas.

Autoevaluación 5
correcta
1 V Es parte de la definición de Grafos.
2 F La definición es G(V, E), donde V representa los vértices del
grafo y E el conjunto de aristas.
3 F Los grafos dirigidos contienen un direccionamiento o flechas que
indican la relación entre sus nodos.
4 V Es el número de arcos que tienen un direccionamiento hacia un
determinado nodo.
5 F Orden del grafo es el número de nodos vértices del grafo.
6 V Hay que representar la relación de cada nodo con los demás
nodos del grafo, por lo cual se requiere de n2 espacios de
memoria.
7 F En las listas de adyacencia se intenta evitar justamente el
reservar espacio para aquellos arcos que no contienen ningún
tipo de información
8 V Por cuanto no existen espacios no utilizados, se trabaja
únicamente sobre vértices existentes.
9 V Ocupan menos espacio de memoria debido a que se optimiza la
organización de la información.
10 V Utilizan arreglos para almacenar: valores numéricos de la
relación, índices de las columnas y punteros a inicios de fila.

Guía didáctica: Estructura de Datos REFERENCIAS BIBLIOGRÁFICAS
8. Referencias bibliográficas
@JuanSet19. (2013). Recorrido en anchura y en profundidad de un grafo

representado por una matriz. Retrieved November 7, 2017, from https://
juanset19.wordpress.com/2013/08/10/recorrido-en-anchura-y-en-
profundidad-de-un-grafo-representado-por-una-matriz/
Gonzalez, H. (2012). Aplicaciones de los árboles y grafos. Retrieved from https://

es.slideshare.net/FENIXHBKHAGM/aplicaciones-de-los-rboles-y-grafos
Guardati, S. (2015). Estructuras de Datos Básicas (Primera). México: Alfaomega.
Titiosky, R. (2008). Slideshare: Unidad 7 Árboles Binarios. Retrieved from https://

es.slideshare.net/elcapo2008/5-arboles-binarios

Estructura de Datos - Guía

Cargado por

Copyright:

Formatos disponibles

Estructura de Datos - Guía

Cargado por

Información del documento

Descripción 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

Estructura de Datos - Guía

Cargado por

Copyright:

Formatos disponibles

Informática

Modalidad Abierta y a Distancia

La Universidad Católica de Loja

Departamento de Ciencias de la Computación y Electrónica

La Universidad Católica de Loja

UNIVERSIDAD TÉCNICA PARTICULAR DE LOJA

Diagramación y diseño digital:

5. Orientaciones generales para el estudio 10

6. Proceso de enseñanza-aprendizaje para el logro de competencias 14

UNIDAD 1. ESTRUCTURAS LINEALES ESTÁTICAS 14

1.1. Cadenas (Strings) 15

1.2. Arreglos Unidimensionales 18

1.3. Operaciones con Arreglos 21

1.4. Arreglos Multidimensionales 30

UNIDAD 2. TIPOS DE DATOS ABSTRACTOS 40

2.1. Pilas y Colas 40

2.3. Colas de prioridad 46

UNIDAD 3. ESTRUCTURAS LINEALES DINÁMICAS 50

3.2. Listas Enlazadas 52

3.3. Implementación de pilas y colas con listas enlazadas 57

UNIDAD 4. ESTRUCTURAS JERÁRQUICAS 62

4.2. Árboles Binarios 66

4.3. Recorridos en Árboles Binarios 67

4.4. Árboles de Búsqueda Binaria 68

4.5. Árboles AVL 70

4.6. Tablas Hash 74

5.1. Conceptos y definiciones 81

5.3. Recorridos de grafos 86

Las Estructuras de Datos son un medio para manejar grandes cantidades de

Esta asignatura tiene el propósito de estudiar las diferentes y particulares formas

El estudio de la asignatura de Estructura de Datos es muy importante en el

La asignatura se desarrolla en cinco unidades distribuidas en tres para el primer

6 MODALIDAD ABIERTA Y A DISTANCIA

Felicitaciones por su decisión de participar en este proceso de formación, le

7 MODALIDAD ABIERTA Y A DISTANCIA

Allen, M. (2013). Estructuras de datos en Java. (Cuarta edición). España:

Este texto proporciona una introducción práctica a las estructuras de

Guamán, F. (2018). Guía didáctica de Estructuras de Datos. Loja – Ecuador:

Esta guía didáctica es un instrumento complementario del texto básico,

Guardati, S. (2015). Estructuras de Datos Básicas (Primera edición). México:

En esta obra se presentan los principales conceptos de la programación

8 MODALIDAD ABIERTA Y A DISTANCIA

diseño implementación de soluciones basadas en la programación y a la

Joyanes, L. Martinez, I. (2005): Metodología, Algoritmos y Estructuras de Datos,

9 MODALIDAD ABIERTA Y A DISTANCIA

5. Orientaciones generales para el estudio

El reto de estudiar a distancia requiere de mucho esfuerzo, entrega, dedicación

Para el estudio de la presente asignatura le damos a conocer algunos materiales

▪▪ El texto básico: ha sido seleccionado cuidadosamente del mercado,

▪▪ La guía didáctica: diseñada para orientar al estudiante sobre temas y textos

▪▪ El Entorno Virtual de Aprendizaje: donde podrá interactuar con sus

▪▪ La tutoría personal: para reforzar el proceso de aprendizaje usted dispone

10 MODALIDAD ABIERTA Y A DISTANCIA

▪▪ La tarea: es una actividad teórica y práctica que acompaña a la guía

Damos algunos lineamientos que le ayudarán a aprovechar su tiempo y lograr

▪▪ Disponga de un lugar limpio y ordenado. Cuide de las condiciones

▪▪ El tiempo que dedique a la lectura y desarrollo de los ejercicios es

▪▪ Hay que trabajar conjuntamente con el texto básico y la guía didáctica,

▪▪ No siempre vamos a realizar nuestras tareas de la mejor forma, por eso no