Estructura de Datos. Examen Ordinario de Práctica

Estructura de Datos[pic 1]

 Examen Ordinario de Práctica

Nombre del alumno(a): ________________________________________________________

Instrucciones: Responda correctamente.

1. Sabemos que, para construir un árbol binario, utilizamos nodos parecidos a los de una lista doblemente enlazada (ver Figura 1). Explique por qué se dice que un árbol binario es una estructura no lineal a diferencia de la lista doblemente enlazada. (2 puntos)

[pic 2]

Figura 1. Representación de un nodo de un árbol. I y D son las referencias o apuntadores izquierdo y derecho del nodo.

1. Determine cuál es el peso de los siguientes árboles (2 puntos)

[pic 3]

[pic 4][pic 5]

1. De acuerdo con la teoría general de árboles, indique los grados de los siguientes árboles (2 puntos)

[pic 6]

1. ¿Cuál es la característica de un nodo raíz? (1 punto)

1. ¿Cuál es la condición de que un nodo sea una hoja? (1 punto)

1. ¿En qué difiere un nodo padre del nodo raíz? (1 punto)

1. Del siguiente árbol binario, indique sus recorridos in-orden, pre-orden y post-orden (3 puntos)

[pic 7]

1. Con los siguientes recorridos forme la estructura del árbol correspondiente (4 puntos)

In-Orden: [0][2][14][50][56][64][74]

Pre-Orden: [50][2][0][14][56][64][74]

Post-Orden: [0][14][2][74][64][56][50]

1. Construir los árboles binarios de búsqueda correspondiente a las listas de números: (4 puntos)

Lista A: 57, 25, 4, 30, 64, 47, 2

Lista B: 2, 23, 33, 7, 26, 21, 64, 58, 39

1. Cómo quedaría el siguiente árbol binario de búsqueda después de insertar los siguientes elementos: 43 y 85 (3 puntos)

[pic 8]

1. Indique cómo quedaría el siguiente árbol binario de búsqueda después de eliminar el nodo 16. (3 puntos)

[pic 9]

1. Indique cómo quedaría el siguiente árbol binario de búsqueda después de eliminar el nodo 68. (3 puntos)

[pic 10]

1. De acuerdo con la conceptualización de la teoría general de grafos determine las formas más comunes para representar los grafos en el campo de la computación e indique sus ventajas y desventajas. (2 puntos)

1. Según la teoría de grafos, para implementar de forma iterativa los recorridos en profundidad y anchura de un grafo utilizaremos como estructura de datos auxiliar respectivamente: (1 puntos)

1. Un vendedor de libros que vive en Basin debe visitar una vez al mes a cuatro clientes localizados en Wald, Bon, Mena y Kiln antes de regresar a su casa en Basin. La siguiente tabla muestra las distancias en millas entre las diferentes ciudades

1. Ayude al vendedor a encontrar una ruta utilizando el algoritmo de primero profundidad y amplitud (6 puntos)
2. indique cuál sería la ruta obtenida con el algoritmo del vecino más cercano (3 puntos)
3. determine, cuál es la ruta más corta utilizando el árbol de costos mínimo (6 puntos)

...