Evaluacion Programacion
15 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

¿Qué es un árbol binario de búsqueda?

  • Un árbol en el que el subárbol izquierdo tiene datos mayores que el nodo raíz.
  • Un árbol en el que el subárbol derecho tiene datos menores que el nodo raíz.
  • Un árbol en el que todos los datos del subárbol izquierdo son menores que los del nodo raíz, y los del subárbol derecho son mayores. (correct)
  • Un árbol en el que el subárbol izquierdo tiene datos menores que el nodo raíz, y el subárbol derecho tiene datos mayores.
  • ¿Qué operación del recorrido de árboles procesa el nodo raíz al final?

    Recorrido Post-Orden

    El recorrido preorden implica recorrer el subárbol izquierdo en ___ primero.

    preorden

    Relaciona los métodos de exploración con su descripción: Exploración lineal, Exploración cuadrática, Doble dirección dispersa

    <p>Exploración lineal = Se busca la siguiente posición si la actual está ocupada Exploración cuadrática = Se exploran posiciones siguiendo una secuencia cuadrática Doble dirección dispersa = Se busca una nueva posición basada en una segunda función hash</p> Signup and view all the answers

    Una colisión en una tabla hash se produce cuando dos claves distintas generan el mismo índice.

    <p>True</p> Signup and view all the answers

    ¿Qué es un árbol binario?

    <p>Un árbol binario es un árbol cuyos nodos no pueden tener más de dos subárboles.</p> Signup and view all the answers

    ¿Qué operaciones se pueden realizar en árboles binarios? (Selecciona todas las respuestas correctas)

    <p>Eliminar el árbol</p> Signup and view all the answers

    El _________________ de un árbol binario es la diferencia en altura entre los subárboles derecho e izquierdo.

    <p>factor de equilibrio</p> Signup and view all the answers

    Un árbol binario de búsqueda es aquel en el que los datos del subárbol izquierdo de un nodo son mayores que los datos del nodo actual.

    <p>False</p> Signup and view all the answers

    ¿Cómo se llama el recorrido que implica procesar primero el subárbol izquierdo, luego la raíz y finalmente el subárbol derecho?

    <p>Recorrido inorden</p> Signup and view all the answers

    ¿Qué significa AVL en la estructura de datos de árboles y por qué se llama así?

    <p>Es en honor a Adelson-Velskii-Landis, los primeros científicos en estudiar sus propiedades.</p> Signup and view all the answers

    ¿Qué es el Factor de Equilibrio en árboles AVL?

    <p>La fórmula que indica si un árbol está balanceado.</p> Signup and view all the answers

    Un árbol AVL puede perder su balance al insertar o eliminar nodos, ¿verdadero o falso?

    <p>False</p> Signup and view all the answers

    ¿Qué métodos se utilizan para el balanceo de un árbol AVL?

    <p>Rotación Simple a la Derecha, Rotación Simple a la Izquierda, Rotación Doble a la Derecha, Rotación Doble a la Izquierda.</p> Signup and view all the answers

    Relaciona el tipo de grafo con su descripción: ¿Dirigido o No dirigido?

    <p>Grafo No Dirigido = Existe un camino entre cualquier par de nodos que forman el grafo. Grafo Dirigido = Se acostumbra a denominar GDA (Grafo Dirigido Acíclico).</p> Signup and view all the answers

    Study Notes

    Here are the study notes for the text:

    Introducción a Árboles

    • Un árbol es una estructura de datos no lineal que se utiliza para representar fórmulas algebraicas, organizar objetos de manera eficiente, y en aplicaciones como inteligencia artificial y algoritmos de cifrado.
    • Los árboles se utilizan comúnmente en sistemas operativos para almacenar archivos y en compiladores, procesamiento de texto y algoritmos de búsqueda.

    Definiciones de Árbol

    • Un nodo es una parte del árbol que contiene un valor y puede tener hijos (subárboles).
    • La raíz es el nodo superior del árbol.
    • Un árbol binario es un árbol en el que cada nodo puede tener como máximo dos hijos (izquierdo y derecho).

    Operaciones en Árboles Binarios

    • CrearÁrbol: crea un nuevo árbol vacío.
    • Construir: crea un árbol con un elemento raíz y dos ramas izquierda y derecha.
    • EsVacio: comprueba si el árbol no tiene nodos.
    • Raíz: devuelve el nodo raíz del árbol.
    • Izquierdo/Derecho: devuelve la rama izquierda/derecha del árbol.
    • Borrar: elimina un nodo del árbol.
    • Pertenece: verifica si un elemento está en el árbol.

    Recorridos en Árboles Binarios

    • Recorrido Preorden:
      • Visita la raíz del árbol.
      • Recorre el subárbol izquierdo en preorden.
      • Recorre el subárbol derecho en preorden.
    • Recorrido Inorden:
      • Recorre el subárbol izquierdo en orden.
      • Visita la raíz del árbol.
      • Recorre el subárbol derecho en orden.
    • Recorrido Postorden:
      • Recorre el subárbol izquierdo en postorden.
      • Recorre el subárbol derecho en postorden.
      • Visita la raíz del árbol.

    Árbol Binario de Búsqueda

    • Un árbol binario de búsqueda es un árbol en el que todos los datos del subárbol izquierdo son menores que los datos de la raíz, y todos los datos del subárbol derecho son mayores que los datos de la raíz.
    • Se utiliza para buscar un término en el árbol utilizando un algoritmo de búsqueda binaria.

    Tablas Hash

    • Una tabla hash es una estructura de datos que asocia una clave única con un valor.
    • Se utiliza una función hash para asignar una clave a una posición en la tabla.
    • Se utilizan métodos de exploración, como la exploración lineal o la exploración cuadrática, para resolver colisiones.

    Operaciones en Tablas Hash

    • Buscar: devuelve el valor asociado a una clave.
    • Insertar: agrega un nuevo par clave-valor a la tabla.
    • Eliminar: elimina un par clave-valor de la tabla.

    Biblioteca Hashtable

    • La clase Hashtable de Java es una implementación de una tabla hash.
    • Se utilizan métodos como put() para insertar, get() para buscar y remove() para eliminar.### Clase Hash
    • Atributos de la clase Hash: int dato y int estado (0: vacío, 1: eliminado, 2: ocupado)
    • Función hash: (n + 1) % m
    • Ejemplo de ingreso de datos: tabla con tamaño 10, datos de 1980 a 1989

    Tabla Hash con Librería

    • Importancia de las tablas hash en el desarrollo de aplicaciones
    • Elementos básicos:
      • Una tabla de un tamaño razonable para almacenar pares clave-valor
      • Una función hash que recibe la clave y devuelve un índice
      • Un procedimiento para tratar colisiones
    • Ejemplo de menú: ingreso de datos, búsqueda de datos, eliminación de datos, visualización de datos y salir

    Árboles AVL

    • Definición: árboles totalmente equilibrados, ideal pero no siempre alcanzable
    • Estructura de datos de árbol AVL: árboles ordenados con balanceo para cada nodo
    • Niveles y Altura de un árbol:
      • Nivel de un nodo: distancia desde el nodo raíz
      • Altura de un árbol: nivel de la hoja del camino más largo desde el raíz más uno
    • Factor de Equilibrio (FE): Altura SubArbol Derecho – Altura SubArbol Izquierdo
    • Ejemplos de árboles equilibrados y no equilibrados
    • Operaciones en árboles AVL: ingreso, eliminación, búsqueda, visualización

    Balanceo de Árboles

    • Rotaciones para balancear árboles:
      • Rotación Simple a la Derecha
      • Rotación Simple a la Izquierda
      • Rotación Doble a la Derecha
      • Rotación Doble a la Izquierda
    • Balanceo en la inserción y eliminación de nodos

    Grafos

    • Definición: un grafo G = (V, A) es un conjunto de vértices o nodos V y un conjunto de arcos A
    • Relación entre dos nodos: un arco o arista representa una relación entre dos nodos
    • Tipos de grafos: no dirigido y dirigido (dígromo)
    • Magnitud: factor de peso asociado a una relación entre dos nodos
    • Caminos en grafos:
      • Un camino P de longitud N desde el vértice V0 a VN en un grafo G
      • Ejemplos de caminos
    • Ciclos en grafos dirigidos: un camino simple cerrado que empieza y termina en el mismo nodo
    • Matriz de adyacencia:
      • Representación de un grafo mediante una matriz
      • Ejemplos de matrices de adyacencia dirigida y no dirigida con y sin factor de peso

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    More Like This

    Use Quizgecko on...
    Browser
    Browser