3er Parcial

3er Parcial

1. Colas Simples

   • Es una lista lineal de elementos en la que las operaciones de insertar y eliminar se realizan en diferentes extremos de la cola. Las colas trabajan con filosofía FIFO ( First In - First out), el primer elemento en entrar es el primer elemento en salir.
     • Tipos
       • Cola simple: Estructura lineal donde los elementos salen en el mismo orden en que llegan.
       • Cola circular: Representación lógica de una cola simple en un arreglo.
       • Cola de Prioridades: Estructura lineal en la cual los elementos se insertan en cualquier posición de la cola y se remueven solamente por el frente.
       • Cola Doble (Bicola): Estructura lineal en la que los elementos se pueden añadir o quitar por cualquier extremo de la cola (cola bidireccional).
     • Ejemplos: Cola de automóviles esperando servicio en una gasolinera. Cola de programas en espera de ser ejecutados por una computadora.
     • Operaciones Basicas
       • Insertar.- Almacena al final de la cola el elemento que se recibe como paramétro.
       • Eliminar.- Saca de la cola el elemento que se encuentra al frente.
       • Vacía.- Regresa un valor booleano indicando si la cola tiene o no elementos (true – si la cola esta vacia, false – si la cola tiene al menos un elemento).
       • Llena.- Regresa un valor booleano indicando si la cola tiene espacio disponible para insertar nuevos elementos ( true – si esta llena y false si existen espacios disponibles).

2. Arboles

   • Se define como una colección de nodos organizados en forma recursiva. Cuando hay 0 nodos se dice que el árbol esta vacío, en caso contrario el árbol consiste en un nodo raíz, el cual tiene 0 o más referencias a otros árboles, conocidos como subárboles. Las raíces de los subárboles se denominan hijos de la raíz, y consecuentemente la raíz se denomina padre de las raíces de sus subárboles.
     • Árboles binarios
       • Un árbol binario es un árbol en donde cada nodo posee 2 referencias a subárboles (ni más, ni menos). En general, dichas referencias se denominan izquierda y derecha, y consecuentemente se define el subárbol izquierdo y subárbol derecho del arbol.
     • Árboles AVL
       • Un árbol AVL es un árbol binario de búsqueda que cumple con la condición de que la diferencia entre las alturas de los subárboles de cada uno de sus nodos es, como mucho 1. La denominación de árbol AVL viene dada por los creadores de tal estructura (Adelson-Velskii y Landis).
     • Operaciones
       • Insertar. Vacio. InOrden. PreOrden. PostOrden. Eliminar. Buscar

3. Grafos

   • Un Grafo no es mas que un conjunto de nodos o vértices que se encuentran relacionados con unas aristas. Ademas los vértices tienen un valor y en ocasiones las aristas también y se le conoce como el costo.
     • Operaciones
       • Insertar vértice. Insertar arista. Eliminar vértice. Eliminar arista. Busqueda. Recorrido. Camino mas corto. Entre otros
     • Recorridos
       • Cadena. Largo de una cadena. Cadena elemental. Cadena simple. Camino. Sendero. Vía
         • (Las definiciones de largo de un camino, camino elemental y camino simple son análogas a las de cadenas, con la salvedad de la orientación.)